DAA - सबसे छोटा पथ
डीजकस्ट्रा का एल्गोरिथम
दिज्कस्ट्रा का एल्गोरिथ्म एक निर्देशित भारित ग्राफ G = (V, E) पर एकल-स्रोत लघु-पथ समस्या को हल करता है , जहां सभी किनारे गैर-नकारात्मक हैं (यानी, w (u, v) ( 0 प्रत्येक किनारे के लिए (u, v) )) ई )।
निम्नलिखित एल्गोरिथ्म में, हम एक फ़ंक्शन का उपयोग करेंगे Extract-Min(), जो सबसे छोटी कुंजी के साथ नोड को निकालता है।
Algorithm: Dijkstra’s-Algorithm (G, w, s)
for each vertex v Є G.V
v.d := ∞
v.∏ := NIL
s.d := 0
S := Ф
Q := G.V
while Q ≠ Ф
u := Extract-Min (Q)
S := S U {u}
for each vertex v Є G.adj[u]
if v.d > u.d + w(u, v)
v.d := u.d + w(u, v)
v.∏ := uविश्लेषण
इस एल्गोरिथ्म की जटिलता पूरी तरह से एक्सट्रैक्ट-मिन फ़ंक्शन के कार्यान्वयन पर निर्भर है। यदि अर्क मिनिमल फ़ंक्शन को रैखिक खोज का उपयोग करके कार्यान्वित किया जाता है, तो इस एल्गोरिथ्म की जटिलता हैO(V2 + E)।
इस एल्गोरिथ्म में, अगर हम मिन-हीप का उपयोग करते हैं Extract-Min() फ़ंक्शन नोड को वापस करने के लिए कार्य करता है Q सबसे छोटी कुंजी के साथ, इस एल्गोरिथ्म की जटिलता को और कम किया जा सकता है।
उदाहरण
आइए हम शीर्ष पर विचार करें 1 तथा 9क्रमशः शुरुआत और गंतव्य शीर्ष के रूप में। प्रारंभ में, प्रारंभ शीर्ष को छोड़कर सभी कोने ly द्वारा चिह्नित किए गए हैं और प्रारंभ शीर्ष को चिह्नित किया गया है0।
| शिखर | प्रारंभिक | चरण १ वी १ | चरण 2 वी 3 | चरण 3 वी 2 | चरण 4 वी 4 | चरण 5 वी 5 | चरण 6 वी 7 | चरण 7 वी 8 | चरण 8 वी 6 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | ∞ | 5 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 3 | ∞ | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 4 | ∞ | ∞ | ∞ | 7 | 7 | 7 | 7 | 7 | 7 |
| 5 | ∞ | ∞ | ∞ | 1 1 | 9 | 9 | 9 | 9 | 9 |
| 6 | ∞ | ∞ | ∞ | ∞ | ∞ | 17 | 17 | 16 | 16 |
| 7 | ∞ | ∞ | 1 1 | 1 1 | 1 1 | 1 1 | 1 1 | 1 1 | 1 1 |
| 8 | ∞ | ∞ | ∞ | ∞ | ∞ | 16 | 13 | 13 | 13 |
| 9 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 20 |
इसलिए, वर्टेक्स की न्यूनतम दूरी 9 शीर्ष से 1 है 20। और रास्ता है
1 → 3 → 7 → 8 → 6 → 9
यह पथ पूर्व सूचना के आधार पर निर्धारित किया जाता है।
बेलमैन फोर्ड एल्गोरिथम
यह एल्गोरिथ्म एक निर्देशित ग्राफ के एकल स्रोत सबसे छोटी पथ समस्या को हल करता है G = (V, E)जिसमें किनारे का वजन ऋणात्मक हो सकता है। इसके अलावा, यह एल्गोरिथ्म सबसे छोटा रास्ता खोजने के लिए लागू किया जा सकता है, अगर कोई नकारात्मक भारित चक्र मौजूद नहीं है।
Algorithm: Bellman-Ford-Algorithm (G, w, s)
for each vertex v Є G.V
v.d := ∞
v.∏ := NIL
s.d := 0
for i = 1 to |G.V| - 1
for each edge (u, v) Є G.E
if v.d > u.d + w(u, v)
v.d := u.d +w(u, v)
v.∏ := u
for each edge (u, v) Є G.E
if v.d > u.d + w(u, v)
return FALSE
return TRUEविश्लेषण
सबसे पहला for लूप का उपयोग आरंभीकरण के लिए किया जाता है, जो अंदर चलता है O(V)बार। अगलाfor लूप रन |V - 1| किनारों पर गुजरता है, जो लेता हैO(E) बार।
इसलिए, बेलमैन-फोर्ड एल्गोरिथ्म में चलता है O(V, E) समय।
उदाहरण
निम्न उदाहरण से पता चलता है कि बेलमैन-फोर्ड एल्गोरिदम कैसे कदम से कदम काम करता है। इस ग्राफ में एक नकारात्मक बढ़त है लेकिन इसका कोई नकारात्मक चक्र नहीं है, इसलिए इस तकनीक का उपयोग करके समस्या को हल किया जा सकता है।
आरंभीकरण के समय, स्रोत को छोड़कर सभी कोने the द्वारा चिह्नित किए जाते हैं और स्रोत द्वारा चिह्नित किया जाता है 0।
पहले चरण में, स्रोत से आने वाले सभी कोने न्यूनतम लागत द्वारा अद्यतन किए जाते हैं। इसलिए, कोनेa तथा h अपडेट किए जाते हैं।
अगले चरण में, कोने a, b, f तथा e अपडेट किए जाते हैं।
इसी तर्क के बाद, इस चरण में वर्टिकल b, f, c तथा g अपडेट किए जाते हैं।
यहाँ, कोने c तथा d अपडेट किए जाते हैं।
इसलिए, वर्टेक्स के बीच न्यूनतम दूरी s और शीर्ष d है 20।
पूर्ववर्ती जानकारी के आधार पर, पथ s → h → e → g → c → d है