algorithm
फ्लोयड-वारशॉल एल्गोरिथम

सभी जोड़ी सबसे कम पथ एल्गोरिथम

फ्लोयड-वारशॉ का एल्गोरिथ्म सकारात्मक या नकारात्मक बढ़त भार के साथ एक भारित ग्राफ में सबसे छोटा रास्ता खोजने के लिए है। एल्गोरिथ्म के एक एकल निष्पादन में सभी जोड़े कोने के बीच सबसे छोटे रास्तों की लंबाई (सममित भार) मिलेगी। थोड़े बदलाव के साथ, यह सबसे छोटे रास्ते को प्रिंट कर सकता है और एक ग्राफ में नकारात्मक चक्रों का पता लगा सकता है। फ्लॉयड-वारशॉल एक डायनेमिक-प्रोग्रामिंग एल्गोरिथम है।

आइए एक उदाहरण देखें। हम इस ग्राफ पर फ्लोयड-वारशॉ का एल्गोरिथ्म लागू करने जा रहे हैं:

पहली बात हम करते हैं, हम दो 2D मैट्रीस लेते हैं। ये आसन्न मैट्रिक्स हैं । मेट्रिसेस का आकार कुल संख्याओं का होने वाला है। हमारे ग्राफ के लिए, हम 4 * 4 मैट्रिसेस लेंगे। डिस्टेंस मैट्रिक्स दो वर्टिकल के बीच अब तक मिली न्यूनतम दूरी को स्टोर करने वाला है। : सबसे पहले, किनारों के लिए, अगर वहाँ यूवी और दूरी / वजन डब्ल्यू, हम संग्रहीत करेंगे है के बीच एक बढ़त है distance[u][v] = w । सभी किनारों के लिए जो मौजूद नहीं है, हम अनंत डाल रहे हैं। पाथ मैट्रिक्स दो कोने के बीच न्यूनतम दूरी पथ को पुनर्जीवित करने के लिए है। इसलिए शुरू में, अगर u और v के बीच कोई रास्ता है, तो हम path[u][v] = u । इसका मतलब है कि वर्टेक्स-यू से वर्टेक्स- वी में आने का सबसे अच्छा तरीका उस किनारे का उपयोग करना है जो वी को यू से जोड़ता है। यदि दो चक्करों के बीच कोई रास्ता नहीं है, तो हम N को वहां पर रखने जा रहे हैं, जिससे यह संकेत मिलता है कि अब कोई रास्ता उपलब्ध नहीं है। हमारे ग्राफ के लिए दो तालिकाओं की तरह दिखेगा:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

चूंकि कोई लूप नहीं है, विकर्णों को एन सेट किया जाता है । और स्वयं शीर्ष से दूरी 0 है ।

फ्लोयड-वार्शाल एल्गोरिथ्म को लागू करने के लिए, हम एक मध्य शीर्ष k का चयन करने जा रहे हैं। फिर प्रत्येक वर्टेक्स i के लिए , हम यह जाँचने जा रहे हैं कि क्या हम i से k और फिर k से j तक जा सकते हैं, जहाँ j एक और शीर्ष है और i से j तक जाने की लागत को कम करता है। यदि वर्तमान दूरी [i] [j] दूरी की तुलना में अधिक है [i] [k] + दूरी [k] [j] , हम दूरी डालने जा रहे हैं [i] [j] उन दो दूरी के योग के बराबर है । और पथ [i] [j] को पथ [k] [j] पर सेट किया जाएगा, क्योंकि i से k तक जाना बेहतर है, और फिर k से j तक । सभी कोने को k के रूप में चुना जाएगा। हमारे पास 3 नेस्टेड लूप होंगे: k के लिए 1 से 4 तक, मैं 1 से 4 तक जा रहा हूं और j से 1 से 4. तक जा रहा हूं ।

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

तो क्या हम मूल रूप से जाँच कर रहे हैं, हर जोड़ी के लिए, क्या हम किसी अन्य शीर्ष से होकर गुजरते हैं? हमारे ग्राफ के लिए संचालन की कुल संख्या 4 * 4 * 4 = 64 होगी । इसका मतलब है कि हम 64 बार यह जाँच करने जा रहे हैं। आइए उनमें से कुछ को देखें:

जब k = 1 , i = 2 और j = 3 , दूरी [i] [j] -2 है , जो दूरी [i] [k] + दूरी [k] [j] = -2 + 0 = से अधिक नहीं है -2 तो यह अपरिवर्तित रहेगा। फिर, जब k = 1 , i = 4 और j = 2 , दूरी [i] [j] = अनंत , जो दूरी से अधिक है [i] [k] + दूरी [k] [j] = 1 + 3 = 4 । इसलिए हमने दूरी [i] [j] = ४ रखी है, और हमने पथ [i] [j] = पथ [k] [j] = १ रख दिया है। इसका मतलब क्या है, वर्टेक्स -4 से वर्टेक्स -2 तक जाने के लिए , रास्ता 4-> 1-> 2 मौजूदा मार्ग से छोटा है। इस तरह हम दोनों मैट्रिसेस को पॉप्युलेट करते हैं। प्रत्येक चरण के लिए गणना यहां दिखाई गई है । आवश्यक परिवर्तन करने के बाद, हमारे मैट्रीस जैसे दिखेंगे:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

यह हमारी सबसे छोटी दूरी की मैट्रिक्स है। उदाहरण के लिए, 1 से 4 तक की सबसे छोटी दूरी 3 है और 4 से 3 के बीच की सबसे छोटी दूरी 2 है । हमारा छद्म कोड होगा:

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

पथ मुद्रण:

पथ मुद्रित करने के लिए, हम पथ मैट्रिक्स की जाँच करेंगे। U से v तक का मार्ग प्रिंट करने के लिए , हम पथ से शुरू करेंगे [u] [v] । हम बदलते रहेंगे v = path [u] [v] जब तक हम रास्ता नहीं ढूंढते [u] [v] = u और एक स्टैक में पथ के प्रत्येक मूल्यों [u] [v] को धक्का देते हैं। यू खोजने के बाद, हम यू प्रिंट करेंगे और स्टैक से आइटम पॉपिंग शुरू करेंगे और उन्हें प्रिंट करेंगे। यह काम करता है क्योंकि पथ मैट्रिक्स वर्टेक्स के मूल्य को संग्रहीत करता है जो किसी अन्य नोड से वी के लिए सबसे छोटा रास्ता साझा करता है। छद्म कोड होगा:

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

नकारात्मक बढ़त चक्र ढूँढना:

यह पता लगाने के लिए कि क्या कोई नकारात्मक बढ़त चक्र है, हमें दूरी मैट्रिक्स के मुख्य विकर्ण की जांच करने की आवश्यकता होगी। यदि विकर्ण पर कोई मान ऋणात्मक है, तो इसका मतलब है कि ग्राफ में एक नकारात्मक चक्र है।

जटिलता:

फ्लोयड-वारशॉ एल्गोरिथ्म की जटिलता हे (V and) और अंतरिक्ष जटिलता है: O (V²) ।