परिणामी मैट्रिक्स = एक मैट्रिक्स जिस पर चटाई [i] [j] सबसे छोटा पथ है जिसमें शीर्ष i स्रोत के रूप में और शीर्ष j गंतव्य के रूप में है।

मैंने जॉनसन के एल्गोरिदम का अपना कार्यान्वयन लिखा है और मैं सोच रहा था कि यह नकारात्मक किनारों को कैसे संभालता है? अंत में, मुझे प्राप्त होने वाली दूरियों का मैट्रिक्स वैसा नहीं है जैसा मुझे फ़्लॉइड-वॉर्शल चलाने से मिलता है। यह स्पष्ट है क्योंकि हम ग्राफ को फिर से भारित करते हैं। क्या इसका मतलब यह है कि जॉनसन का एल्गोरिदम हमें सबसे छोटे पथ की लागत खोजने में मदद नहीं करता है, लेकिन केवल कौन सा पथ सबसे छोटा है? इसके अलावा, यदि परिणामी मैट्रिक्स में लागत 0 के शीर्ष A और शीर्ष B के बीच एक पथ है और शीर्ष A और शीर्ष C के बीच लागत 0 है, तो क्या इसका मतलब यह है कि B और C समान रूप से A से दूर हैं?

0
Lin Spark 1 पद 2018, 22:19

1 उत्तर

सबसे बढ़िया उत्तर

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

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

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

0
templatetypedef 2 पद 2018, 05:14