एक निर्देशित चक्रीय ग्राफ में दो कोने के बीच अधिकतम भारित पथ

इस समस्या पर कुछ मार्गदर्शन प्यार करें:

जी एक निर्देशित चक्रीय ग्राफ है। आप वर्टिकल c से वर्टेक्स z में जाना चाहते हैं। कुछ किनारे आपके लाभ को कम करते हैं और कुछ आपके लाभ को बढ़ाते हैं। अपने लाभ को अधिकतम करते हुए आप c से z तक कैसे पहुँचते हैं। समय जटिलता क्या है?

धन्यवाद!

उत्तर:

उत्तर № 1 के लिए 1

समस्या का एक इष्टतम उपस्ट्रक्चर है। शीर्ष से सबसे लंबा रास्ता खोजने के लिए c कशेरुक करने के लिए z, हम पहले से सबसे लंबा रास्ता खोजने की जरूरत है c के सभी पूर्ववर्तियों के लिए z। इनमें से प्रत्येक समस्या एक और छोटी सबप्रॉब्लम (सबसे लंबा रास्ता) है c एक विशिष्ट पूर्ववर्ती के लिए)।

के पूर्ववर्तियों को दर्शाता है z जैसा u1,u2,...,uk तथा dist[z] से सबसे लंबा रास्ता है c सेवा मेरे z फिर dist[z]=max(dist[ui]+w(ui,z))..

यहाँ 3 पूर्ववर्तियों के साथ एक दृष्टांत दिया गया है जो कि किनारे के भार को छोड़ते हैं:

तो सबसे लंबा रास्ता खोजने के लिए z हमें सबसे पहले अपने पूर्ववर्तियों के लिए सबसे लंबा रास्ता खोजने की जरूरत है और अधिक से अधिक (उनके मूल्यों के साथ-साथ उनके किनारों का वजन) लेना है z)।

जब भी हम किसी शीर्ष पर जाते हैं तो इसकी आवश्यकता होती है u, के सभी u"पूर्ववर्तियों का विश्लेषण और गणना की जानी चाहिए थी।

तो सवाल यह है: किसी भी शीर्ष के लिए u, कैसे सुनिश्चित करें कि एक बार हम सेट करें dist[u], dist[u] बाद में कभी नहीं बदला जाएगा? इसे दूसरे तरीके से रखें: यह सुनिश्चित करने के लिए कि हमने सभी रास्तों पर विचार किया है c सेवा मेरे u किसी भी बढ़त पर विचार करने से पहले u?

चूंकि ग्राफ चक्रीय है, हम इसकी गारंटी दे सकते हैंग्राफ पर एक टोपोलॉजिकल प्रकार खोजने से स्थिति। टोपोलॉजिकल सॉर्ट वर्टिकल की एक श्रृंखला की तरह होता है, जहां सभी किनारे बाएं से दाएं होते हैं। तो अगर हम शीर्ष पर हैं vi तब हमने सभी मार्गों पर विचार किया है vi और का अंतिम मूल्य है dist[vi].

समय जटिलता: सामयिक प्रकार लेता है O(V+E)। सबसे बुरे मामले में जहां z एक पत्ता है और अन्य सभी कोने इस ओर इशारा करते हैं, हम सभी ग्राफ किनारों पर जाएँगे जो देता है O(V+E).

---

जवाब के लिए 0 № 2

चलो च (यू) अधिकतम लाभ प्राप्त करें जिससे आप जा सकते हैं सी सेवा मेरे यू आपके DAG में। फिर आप गणना करना चाहते हैं च (z)। यह गतिशील प्रोग्रामिंग / टोपोलॉजिकल सॉर्टिंग का उपयोग करके रैखिक समय में आसानी से गणना की जा सकती है।

हस्ताक्षर करना f (u) = -इनफिनिटी फॉर एवरीवन यू के अलावा अन्य सी, तथा f (c) = 0। फिर, के मानों की गणना करें च आपके DAG के कुछ सामयिक क्रम में।इस प्रकार, जैसा कि ऑर्डर टोपोलॉजिकल है, नोड के प्रत्येक आने वाले किनारे के लिए गणना की जा रही है, अन्य समापन बिंदुओं की गणना की जाती है, इसलिए इस नोड के लिए अधिकतम संभव मान चुनें, अर्थात्। f (u) = अधिकतम (च (v) + लागत (v, u)) प्रत्येक आने वाले किनारे के लिए (v, u).

---

जवाब के लिए 0 № 3

इसका उपयोग करने के लिए बेहतर है सामयिक छँटाई के बजाय बेलमैन फोर्ड जब से इसकी डी.ए.जी.

स्रोत: - http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf

संपादित करें: -

G नकारात्मक किनारों वाला एक DAG है।

कुछ किनारे आपके लाभ को कम करते हैं और कुछ आपके लाभ को बढ़ाते हैं

• किनारों - लाभ में वृद्धि - सकारात्मक मूल्य
• किनारों - लाभ में कमी - नकारात्मक मूल्य

टीएस के बाद, टीएस क्रम में प्रत्येक शीर्ष यू के लिए - प्रत्येक आउटगोइंग एज को आराम दें।

dist[] = {-INF, -INF, ….}
dist[c] = 0 // source

for every vertex u in topological order
if (u == z) break; // dest vertex
for every adjacent vertex v of u
if (dist[v] < (dist[u] + weight(u, v))) // < for longest path = max profit
dist[v] = dist[u] + weight(u, v)

ans = dist[z];

---