किनारों के बाद सबसे कम पथों पर प्रभाव हटा दिया गया है - एल्गोरिदम, ग्राफ, सबसे छोटा रास्ता, बेलमैन-फोर्ड

निर्देशित ग्राफ का एक इनपुट प्रदान किया गया है औरमुझे एक विशेष नोड "टी" के लिए सबसे छोटा रास्ता मिला है - अतुल्यकालिक और तुल्यकालिक बेलमैन-फोर्ड एल्गोरिथ्म। मैं कुछ किनारों को हटाने के बाद सबसे छोटे रास्तों पर प्रभाव का पता लगाने की कोशिश कर रहा था। मेरे दृष्टिकोण में, मैंने हटाए गए किनारों के शुरू नोडों पर अनंत के रूप में दूरी को चिह्नित करने की कोशिश की और अतुल्यकालिक बेलमैन-फोर्ड को लागू करने की कोशिश कर रहा था, लेकिन मैं इस बिंदु पर फंस गया क्योंकि अन्य नोड्स उनके मूल्य को अपडेट नहीं करेंगे क्योंकि उनके पास पहले से ही सबसे कम है पथ न्यूनतम मूल्य।

क्या कोई मुझे नए ग्राफ पर फिर से पूर्ण एल्गोरिथ्म चलाने के बिना नए सबसे छोटे रास्तों को खोजने का एक तरीका निकालने में मदद कर सकता है?

उत्तर:

आप नहीं कर सकते। और एक सरल स्पष्टीकरण बेलमैन-फोर्ड एल्गोरिथम में ही पाया जा सकता है:

यदि V नोड्स का सेट है। नोड शुरू करने से किसी भी अन्य नोड के लिए एक न्यूनतम पथ अधिकतम गुजर जाएगा | V | नोड्स (| V | -1 किनारों)। यही कारण है कि आप किनारों के लिए आराम करते हैं। वी -1 -1, ताकि सभी नोड्स से "सूचना" स्रोत तक फैल जाए।

क्या आपने पहले से ही बेलमैन-फोर्ड लागू किया हैएक ग्राफ पर एल्गोरिथ्म, आप सभी हटाए गए नोड के पड़ोसियों को आराम देना शुरू कर सकते हैं और अपने पड़ोसियों को परिवर्तनों का प्रचार कर सकते हैं जब तक कि एक मार्ग जो हटाए गए नोड का उपयोग नहीं कर रहा है (जब तक कोई अपडेट नहीं किया जा रहा है)। नकारात्मक चक्र से सावधान।