भारित रेखांकन

Question

के लिए BFS का उपयोग

मैं ही स्रोत कम से कम पथ एल्गोरिदम में संशोधन किया गया था और इस वीडियो में, शिक्षक कहा गया है कि BFS/डीएफएस एक भारित ग्राफ (मैं में कम से कम पथ को खोजने के लिए सीधे इस्तेमाल नहीं किया जा सकता अनुमान है कि हर कोई इसे पहले से जानता है) और खुद को कारण बताते हुए कहा।

मैं सटीक कारण/स्पष्टीकरण के बारे में सोच रहा था कि इसका भार भारित ग्राफ के लिए क्यों नहीं किया जा सकता है। क्या यह किनारों के वजन या किसी और चीज के कारण है? क्या कोई मुझे समझा सकता है क्योंकि मुझे थोड़ा उलझन लगता है।

पीएस: मैं this प्रश्न और this प्रश्न के माध्यम से चला गया।

A---(3)-----B 
|   | 
\-(1)-C--(1)/ 

बी करने के लिए एक से कम से कम पथ सी के माध्यम से है (2 के कुल वजन के साथ):

Answer 1

इस तरह एक ग्राफ पर विचार करें। एक सामान्य बीएफएस सीधे ए से बी तक पथ लेगा, बी को चिह्नित के रूप में चिह्नित करेगा, और ए से सी को चिह्नित करेगा, जैसा सी देखा गया है।

अगले चरण में, सी, बी से प्रचारित पहले से ही चिह्नित किया गया है, इसलिए सी से बी के पथ को संभावित छोटे पथ के रूप में नहीं माना जाएगा, और बीएफएस आपको बताएगा कि ए से सबसे छोटा रास्ता बी का वजन 3.

आप भारित ग्राफ पर सबसे कम पथ खोजने के लिए बीएफएस के बजाय Dijkstra's algorithm का उपयोग कर सकते हैं। कार्यात्मक रूप से, एल्गोरिदम बीएफएस के समान ही है, और बीएफएस के समान तरीके से लिखा जा सकता है। एकमात्र चीज जो बदलती है वह वह क्रम है जिसमें आप नोड्स पर विचार करते हैं।

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

दूसरी ओर, डिज्कस्ट्रा एल्गोरिथ्म के रूप में काम करेगा इस प्रकार है:

1. पर विचार करें A -> सी
2. पर विचार सी (चूंकि यह एक से सबसे कम बढ़त वजन है) -> बी (चूंकि यह अब तक पहुंचने वाले किसी भी नोड से सबसे कम वजन वाला किनारा है, जिसे हमने अभी तक नहीं माना है)
3. ए -> बी पर विचार करें और अनदेखा करें क्योंकि बी पहले से ही देखा जा चुका है।

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

create a heap or priority queue 
place the starting node in the heap 
dist[2...n] = {∞} 
dist[1] = 0 
while the heap contains items: 
    vertex v = top of heap 
    pop top of heap 
    for each vertex u connected to v: 
     if dist[u] > dist[v] + weight of v-->u: 
      dist[u] = dist[v] + weight of edge v-->u 
      place u on the heap with weight dist[u] 

विकिपीडिया से यह GIF क्या होता है का एक अच्छा दृश्य प्रदान करता है:

सूचना है कि यह बहुत ही BFS कोड के समान दिखता है, एकमात्र वास्तविक अंतर नियमित कतार डेटा संरचना की बजाय, नोड से दूरी से क्रमबद्ध एक ढेर का उपयोग होता है।

Answer 2

हालांकि यह सच है, लेकिन आप भारित रेखांकन में BFS/DFS इस्तेमाल कर सकते हैं, ग्राफ में एक छोटे से बदलाव के साथ, यदि आपका ग्राफ के वजन धनात्मक पूर्णांक होते हैं आप वजन n साथ एक बढ़त n किनारों के साथ वजन 1 के साथ n-1 बीच से बदल सकते हैं नोड्स। कुछ इस तरह:

A-(4)-B 

हो जाएगा:

A-(1)-M1-(1)-M2-(1)-M3-(1)-B 

और अपने अंतिम BFS/डीएफएस परिणामों में इन मध्यम नोड्स (एम 1, M2, एम 3) की तरह विचार नहीं करते।

---

इस एल्गोरिथ्म जटिलता हे (वी * एम) है और अगर हम जानते हैं कि हमारे विशेष रेखांकन M<log V में इस एल्गोरिथ्म माना जा सकता है एम, हमारे किनारों का अधिकतम वजन है, लेकिन सामान्य रूप में इस एल्गोरिथ्म नहीं हो सकता है ऐसा एक अच्छा प्रदर्शन।