फ़्लॉयड–वॉर्शल एल्गोरिदम

पुराने रोड एटलस के आखिर में एक टेबल होती थी: हर दो शहरों के बीच की दूरी। फ़्लॉयड–वॉर्शल ऐसी टेबल निकालने का तरीका है, और यह अब तक लिखे गए सबसे छोटे एल्गोरिदम में से एक है: तीन लूप, एक तुलना, और हर सबसे छोटी दूरी अपनी जगह पर आ जाती है।

एक छोटा ग्राफ़ जिसके एज की लंबाई है, उसके बगल में हर नोड-जोड़ी के बीच की दूरियों की टेबल, जिसकी एक पंक्ति और एक कॉलम हाइलाइट हैं
एक छोटा ग्राफ़ जिसके एज की लंबाई है, उसके बगल में हर नोड-जोड़ी के बीच की दूरियों की टेबल, जिसकी एक पंक्ति और एक कॉलम हाइलाइट हैं

मूल विचार

डाइक्स्ट्रा एल्गोरिदम और बेलमैन–फ़ोर्ड एक शुरुआत से सबसे छोटी दूरियाँ खोजते हैं। फ़्लॉयड–वॉर्शल उन्हें हर नोड से हर दूसरे नोड तक एक साथ खोजता है, एक टेबल में जिसमें हर नोड की एक पंक्ति और एक कॉलम है। यह उससे शुरू करता है जो एज सीधे बताते हैं, और फिर रास्ते में ज़्यादा से ज़्यादा नोड को पड़ाव बनने देकर पूरी टेबल को सुधारता है।

चरण दर चरण

टेबल भरें: हर नोड से खुद तक 0, पड़ोसियों के बीच एज की लंबाई, और बाकी जगह अनंत। फिर हर नोड k के लिए, और हर जोड़ी i, j के लिए: अगर i से k की दूरी और k से j की दूरी का जोड़ i से j की दूरी से कम है, तो छोटी संख्या लिख दें। पूरा एल्गोरिदम बस इतना ही है। कोड में यह तीन लूप हैं, जिनमें k सबसे बाहर है।

एक उदाहरण

चार नोड लें जिनके एज हैं: A–B लंबाई 3, B–C 1, A–C 5 और C–D 2। टेबल इन्हीं से शुरू होती है, और A–D और B–D के लिए अनंत। राउंड A कुछ नहीं बदलता, क्योंकि A से होकर हर रास्ता लंबा है। राउंड B, B से होकर A से C पाता है: 3 + 1 = 4, जो 5 से छोटा है। राउंड C, C से होकर A से D पाता है: 4 + 2 = 6, और B से D: 1 + 2 = 3, दोनों पहली बार मिले रास्ते। राउंड D कुछ नहीं बदलता। अंतिम टेबल: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2।

लूप का क्रम क्यों मायने रखता है

पड़ाव k सबसे बाहरी लूप होना चाहिए। k के राउंड के बाद, हर प्रविष्टि सिर्फ़ पहले k नोड को पड़ाव मानकर मिली सबसे छोटी दूरी होती है, और अगला राउंड उसी पर आगे बढ़ता है: नए पड़ाव से होकर सबसे अच्छा रास्ता, उस तक के सबसे अच्छे रास्ते और उससे आगे के सबसे अच्छे रास्ते का जोड़ है, और दोनों पहले से सही हैं। k को अंदरूनी लूप में रखने से यह गारंटी टूट जाती है और गलत दूरियाँ रह सकती हैं। राउंड के दौरान टेबल को वहीं अपडेट करना सुरक्षित है, क्योंकि उस राउंड में k की अपनी पंक्ति और कॉलम नहीं बदलते।

इतिहास और उपयोग

Bernard Roy ने 1959 में इस तरीके का वर्णन किया। 1962 में Stephen Warshall ने इसे ट्रांज़िटिव क्लोज़र के लिए प्रकाशित किया, जो सिर्फ़ यह पूछता है कि कोई नोड दूसरे तक पहुँच सकता है या नहीं, और Robert Floyd ने इसे सबसे छोटे रास्तों के लिए प्रकाशित किया। यह दूरी टेबल और रूटिंग टेबल बनाता है, किसी नेटवर्क का व्यास निकालता है, बताता है कि कौन-से नोड किन तक पहुँच सकते हैं, और विकर्ण पर नेगेटिव प्रविष्टि से नेगेटिव साइकिल का पता देता है।

खुद आज़माएँ

ऐप खोलें और “आगे” दबाएँ। एक तरफ़ ग्राफ़ है और दूसरी तरफ़ टेबल। हर राउंड मौजूदा पड़ाव की पंक्ति और कॉलम को हाइलाइट करता है; हर चरण एक जोड़ी की छोटी दूरी लिखता है और जोड़ी गई दोनों प्रविष्टियों के चारों ओर रेखा बनाता है। इस राउंड में बदले खाने रंगे होते हैं। टेबल पूरी होने पर दोनों के बीच का सबसे छोटा रास्ता देखने के लिए शुरुआत और लक्ष्य चुनें।

अक्सर पूछे जाने वाले प्रश्न

फ़्लॉयड–वॉर्शल की टाइम कॉम्प्लेक्सिटी क्या है?

n नोड के लिए O(n³), एज कितने भी हों, और टेबल के लिए O(n²) मेमोरी। छोटे या घने ग्राफ़ के लिए यही पहली पसंद है, जहाँ इसका सरल लूप बहुत तेज़ चलता है।

फ़्लॉयड–वॉर्शल या हर नोड से डाइक्स्ट्रा?

घने ग्राफ़ के लिए, या जब एज नेगेटिव हो सकते हैं, फ़्लॉयड–वॉर्शल ज़्यादा सरल है और लगभग उतना ही तेज़। नॉन-नेगेटिव एज वाले बड़े विरल ग्राफ़ के लिए हर नोड से डाइक्स्ट्रा एल्गोरिदम चलाना तेज़ है।

क्या फ़्लॉयड–वॉर्शल डायनेमिक प्रोग्रामिंग है?

हाँ। यह पहले k − 1 नोड के जवाबों से उन रास्तों की समस्या हल करता है जिनके पड़ाव पहले k नोड में से हैं, और सिर्फ़ एक टेबल रखता है, जिसे चलते-चलते बदलता जाता है।

ट्रांज़िटिव क्लोज़र क्या है?

यह बताने वाली टेबल कि कौन-से नोड किन तक पहुँच सकते हैं, दूरियों को छोड़कर। एल्गोरिदम का Warshall वाला रूप इसे "min" और "+" की जगह "or" और "and" से निकालता है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

फ़्लॉयड–वॉर्शल आज़माएँ