ग्राफ

Question

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

मुझे एक सरल नमूना

तो ग्राफ भारित किनारों के साथ एक निर्देशित ग्राफ है साथ समझाने की कोशिश करते हैं, और यह चक्रीय हो सकता है। उच्चतम क्षमता वाला पथ एस-> बी-> टी होगा और 250 की क्षमता होगी, क्योंकि वह किनारा सीमा निर्धारित कर रहा है।

मैंने कुछ पढ़ा है और पाया है कि इस प्रकार की समस्या "Widest path problem" है या मैं इसे अधिकतम न्यूनतम क्षमता वाले पथ की तरह कुछ कहूंगा, लेकिन मुझे कोई उदाहरण या कोई छद्म कोड नहीं मिला है इससे निपटने के लिए।

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

Answer 1

मैं Dijkstra's के कुछ संस्करण का उपयोग करूंगा। मैं छद्म कोड के नीचे विकिपीडिया से लिया और केवल 5 छोटे चीजें बदल:

प्रारंभ

1. (पर लाइन 3 से) नाम बदलकर distwidth करने के लिए प्रत्येक width-infinity (पंक्ति 3) को
2. चौड़ाई प्रारंभ infinity के स्रोत (लाइन 8) की
3. -infinity (लाइन 14)
4. संशोधित अद्यतन समारोह और हस्ताक्षर करने के लिए खत्म कसौटी सेट (लाइन 20 + 21)
01,235,

1 function Dijkstra(Graph, source): 
2  for each vertex v in Graph:         // Initializations 
3   width[v] := -infinity ;        // Unknown width function from 
4                 // source to v 
5   previous[v] := undefined ;        // Previous node in optimal path 
6  end for              // from source 
7  
8  width[source] := infinity ;         // Width from source to source 
9  Q := the set of all nodes in Graph ;      // All nodes in the graph are 
10                 // unoptimized – thus are in Q 
11  while Q is not empty:          // The main loop 
12   u := vertex in Q with largest width in width[] ;  // Source node in first case 
13   remove u from Q ; 
14   if width[u] = -infinity: 
15    break ;           // all remaining vertices are 
16   end if             // inaccessible from source 
17   
18   for each neighbor v of u:        // where v has not yet been 
19                 // removed from Q. 
20    alt := max(width[v], min(width[u], width_between(u, v))) ; 
21    if alt > width[v]:         // Relax (u,v,a) 
22     width[v] := alt ; 
23     previous[v] := u ; 
24     decrease-key v in Q;       // Reorder v in the Queue 
25    end if 
26   end for 
27  end while 
28  return width; 
29 endfunction 

कुछ (handwaving) स्पष्टीकरण क्यों यह काम करता है: आप स्रोत के साथ शुरू करते हैं। वहां से, आपके पास अनंत क्षमता है। अब आप स्रोत के सभी पड़ोसियों की जांच करें। मान लें कि किनारों में सभी की समान क्षमता नहीं है (आपके उदाहरण में, (s, a) = 300 कहें)। फिर, b तक पहुंचने के लिए (s, b) तक पहुंचने का कोई बेहतर तरीका नहीं है, इसलिए आप b की सर्वोत्तम केस क्षमता जानते हैं। जब तक आप सभी शीर्षकों तक नहीं पहुंच जाते, तब तक आप ज्ञात सेट के सर्वश्रेष्ठ पड़ोसियों के पास जाते रहेंगे।

Answer 2

उपर्युक्त उत्तर बहुत अच्छी तरह से समझाया गया है। शायद ज़रुरत पड़े किसी एल्गोरिथ्म की सत्यता का एक विवरण की जरूरत है, ये रहा:

सबूत:

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

अपरिवर्तनीय हाइपोथिसिस: किसी भी चरण में, सेट ए में सभी शीर्षकों में अधिकतम न्यूनतम क्षमता पथ के सही मान होते हैं। यानी, सभी पिछले पुनरावृत्तियों सही हैं।

बेस केस की शुद्धता: जब सेट ए में केवल वर्टेक्स एस होता है। फिर एस के लिए मूल्य अनंत है, जो सही है।

वर्तमान यात्रा में, हम

सेट

वैल [W] = अधिकतम (वैल [W], मिनट (वैल [V], width_between (VW)))

प्रेरक कदम: मान लीजिए, डब्ल्यू सेट बी में सबसे बड़ा वैल [डब्ल्यू] के साथ वर्टेक्स है। और डब्ल्यू कतार से हटा दिया गया है और डब्ल्यू उत्तर वाल [डब्ल्यू] सेट किया गया है।

अब, हमें यह दिखाने की ज़रूरत है कि हर दूसरे एस-डब्ल्यू पथ की चौड़ाई < = वैल [डब्ल्यू] है। यह हमेशा सत्य होगा क्योंकि डब्ल्यू तक पहुंचने के अन्य सभी तरीके सेट बी

और सेट बी में सभी अन्य शीर्षकों एक्स के लिए, एक्स [एक्स] < = वैल [ डब्ल्यू]

इस प्रकार डब्ल्यू के किसी अन्य पथ को वैल [एक्स] द्वारा बाधित किया जाएगा, जो कभी वैल [डब्ल्यू] से अधिक नहीं होता है।

इस प्रकार वैल [डब्ल्यू] का वर्तमान अनुमान इष्टतम है और इसलिए एल्गोरिदम सभी शीर्षकों के लिए सही मानों की गणना करता है।