जॉनसन का एल्गोरिदम नकारात्मक किनारों - दूरी मैट्रिक्स

जॉनसन के एल्गोरिदम को वास्तव में उसी पथ को वापस देना चाहिए जो आपको फ़्लॉइड-वॉर्शल के साथ वापस मिलेगा - यदि आप इसे नहीं देख रहे हैं, तो इसका मतलब है कि कहीं न कहीं आपके कार्यान्वयन में एक बग है।

आप सही हैं कि जॉनसन का एल्गोरिदम ग्राफ के किनारों को फिर से वजन करता है, लेकिन यह एक चतुर तरीके से ऐसा करता है। विशेष रूप से, नए ग्राफ़ में, जबकि प्रत्येक पथ की लागत नए ग्राफ़ में मूल ग्राफ़ की तुलना में भिन्न हो सकती है, नए ग्राफ़ में पथों की सापेक्ष लागत हैं मूल ग्राफ के समान। इस अर्थ में, नए ग्राफ़ में सबसे छोटे पथ के रूप में जो भी पथ वापस आते हैं, वे आवश्यक रूप से आपके मूल ग्राफ़ से सबसे छोटे पथ भी होंगे। नए ग्राफ़ में उन पथों की लागत आपके मूल ग्राफ़ से मेल नहीं खाने वाली हैं, और इसलिए जॉनसन के एल्गोरिथम में पोस्टप्रोसेसिंग चरण के रूप में आपको प्रभाव को उलटने के लिए उत्पादित लागतों में बदलाव करना चाहिए वजन बदलने से।

आप जिस कोड को चला रहे हैं उसे देखे बिना यह कहना मुश्किल है कि विशेष रूप से क्या गलत हुआ, हालांकि। आपको कुछ विशिष्ट कोड, आपके द्वारा चलाए जा रहे विशिष्ट परीक्षण केस, आपके द्वारा प्राप्त किए जा रहे विशिष्ट आउटपुट, और आप क्यों मानते हैं कि वे गलत हैं, के साथ अनुवर्ती प्रश्न पोस्ट करने में आपको अधिक भाग्य मिल सकता है।