एल्गोरिदम ग्राफ में शीर्ष के पथ खोजने के लिए, कोई सामान्य शिखर, नकारात्मक वजन के साथ?

Question

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

जोड़ा गया: टिप्पणियों के लिए धन्यवाद। स्पष्ट होने के लिए, मैं एक निर्दिष्ट प्रारंभ नोड से निर्दिष्ट अंत नोड तक प्राप्त करने के शीर्ष के तरीकों की तलाश में हूं, जिसमें कोई अन्य नोड सामान्य नहीं है। मुझे वैश्विक इष्टतम की आवश्यकता है; अनुक्रमिक रूप से सर्वोत्तम और हटाने वाले नोड्स को खोजने से संतोषजनक परिणाम नहीं मिलता है। यह एक: https://en.wikipedia.org/wiki/Yen%27s_algorithm, जो मैं बात कर रहा हूं उसका स्वाद देता है, लेकिन इस मामले में इसे गैर-ऋणात्मक किनारे की लागत की आवश्यकता होती है और यह नोड्स को साझा करने की अनुमति भी देती है।

Answer 1

मुझे लगता है कि समस्या को न्यूनतम लागत प्रवाह खोजने में हल किया जा सकता है।

1. प्रत्येक नोड वी स्रोत के अलावा अन्य बदलें और दो नोड्स v1 और v2 वजन 0 के एक किनारे से से जुड़े के साथ सिंक:

   के निम्नलिखित तरीके से ग्राफ को बदलने चलो v1 से v2। पूर्व वी की भेजे किनारों से v2v1 और बाहर जाने वाले छुट्टी करने के लिए दर्ज करें। इसके साथ ही समस्या का उपयोग न करने के बराबर है जो एक से अधिक बार किनारों पर है।

2. सभी किनारों पर क्षमता 1 सेट करें।

मूल्य का एक प्रवाह कश्मीर आप कश्मीर रास्तों कि एक नोड (क्योंकि उन नए किनारों में 1 करने के लिए क्षमता डालने की) का हिस्सा नहीं है दे देंगे ढूँढना। तो यदि यह प्रवाह न्यूनतम लागत प्रवाह है, तो आपके पास यह होगा कि के पथों में भी न्यूनतम संभव लागत है।

यह माना जा रहा है कि आपके पास स्रोत और सिंक को सीधे जोड़ने वाला किनारा नहीं है। उस कोने मामले को अलग से जांचें।