- मौजूदा पड़ाव
- पहले से पड़ाव
- छोटी हुई जोड़ी
- रास्ता
फ़्लॉयड–वॉर्शल एल्गोरिदम
हर शहर से हर दूसरे शहर तक कितनी दूरी है? फ़्लॉयड–वॉर्शल इसका जवाब एक ही बार में देता है, एक टेबल और तीन नेस्टेड लूप से। हर राउंड रास्ते में एक और नोड को पड़ाव बनने देता है और हर जोड़ी के लिए पूछता है कि क्या उससे होकर घूमकर जाना छोटा है। चरण दर चरण चलाकर देखें कि टेबल कैसे भरती है और दूरियाँ कैसे घटती हैं। टेबल को भरते देखने के लिए “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। टेबल में हर नोड-जोड़ी के बीच अब तक मिली सबसे छोटी दूरी है; हर एज पर लिखी संख्या उसकी लंबाई है। हर राउंड रास्ते में एक और नोड को पड़ाव बनने देता है, और हर चरण वह जोड़ी दिखाता है जो उससे होकर छोटी होती है। किसी नोड को शुरुआत बनाने के लिए उस पर क्लिक करें; क्लिक को “लक्ष्य” पर बदलें और किसी दूसरे नोड पर क्लिक करें, ताकि अंत में दोनों के बीच का सबसे छोटा रास्ता दिखे। “नया ग्राफ़” दूसरा ग्राफ़ बनाता है; उसमें कितने नोड और एज हों, यह चुनें। बोर्ड चुना होने पर, ऐरो कुंजियाँ एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।
यह कैसे काम करता है
- “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” का इस्तेमाल करें। कहीं भी जाने के लिए चरण स्लाइडर खींचें।
- टेबल देखें: मौजूदा पड़ाव की पंक्ति और कॉलम रंगे होते हैं, और हर चरण एक छोटी दूरी लिखता है।
- अंत में दोनों के बीच का सबसे छोटा रास्ता देखने के लिए शुरुआत और लक्ष्य चुनें। “नया ग्राफ़” आज़माने के लिए दूसरा ग्राफ़ बनाता है।
फ़्लॉयड–वॉर्शल कैसे काम करता है
हर नोड के लिए एक पंक्ति और एक कॉलम वाली टेबल बनाएँ। विकर्ण पर 0 भरें, जहाँ दो नोड जुड़े हैं वहाँ एज की लंबाई, और बाकी हर जगह अनंत। फिर हर नोड k को बारी-बारी से संभावित पड़ाव मानें। हर जोड़ी i, j के लिए, टेबल में i से j की दूरी की तुलना i से k की दूरी और k से j की दूरी के जोड़ से करें, और छोटी वाली रखें। आखिरी नोड के बाद, हर प्रविष्टि अपने दोनों नोड के बीच की सबसे छोटी दूरी होती है।
यह क्यों काम करता है
k के राउंड के बाद, टेबल में हर जोड़ी के लिए वह सबसे छोटा रास्ता होता है जिसके सभी पड़ाव अब तक निपटाए गए नोड में से हैं। अगले नोड के राउंड को बस यह तय करना होता है कि वह नोड मदद करता है या नहीं: उससे होकर जाने वाला सबसे छोटा रास्ता, उस तक के सबसे छोटे रास्ते और उससे आगे के सबसे छोटे रास्ते का जोड़ है, और दोनों पहले से टेबल में हैं। पहले मिले छोटे जवाबों से बड़ा जवाब बनाने के इस तरीके को डायनेमिक प्रोग्रामिंग कहते हैं। नेगेटिव एज होने पर भी यह काम करता है, और विकर्ण पर नेगेटिव संख्या नेगेटिव साइकिल का पता देती है।
अक्सर पूछे जाने वाले प्रश्न
फ़्लॉयड–वॉर्शल एल्गोरिदम क्या है?
एक एल्गोरिदम जो वेटेड ग्राफ़ में हर नोड-जोड़ी के बीच की सबसे छोटी दूरी खोजता है। यह दूरियों की एक टेबल रखता है और बारी-बारी से हर नोड के लिए जाँचता है कि क्या उस नोड से होकर जाने पर कोई जोड़ी छोटी होती है।
फ़्लॉयड–वॉर्शल कितना तेज़ है?
इसमें n नोड पर तीन नेस्टेड लूप हैं, इसलिए काम n³ के साथ बढ़ता है, और टेबल को n² प्रविष्टियाँ चाहिए। कुछ सौ नोड वाले ग्राफ़ के लिए यह ठीक है। बड़े विरल ग्राफ़ के लिए हर नोड से डाइक्स्ट्रा एल्गोरिदम चलाना तेज़ है।
क्या फ़्लॉयड–वॉर्शल नेगेटिव एज संभाल सकता है?
हाँ, जब तक कोई नेगेटिव साइकिल न हो। अगर हो, तो विकर्ण की कोई प्रविष्टि नेगेटिव हो जाती है, और फ़्लॉयड–वॉर्शल इसी तरह उसका पता लगाता है।
सिर्फ़ दूरियाँ नहीं, रास्ते कैसे पाऊँ?
एक दूसरी टेबल रखें जिसमें i से j के रास्ते का अगला नोड हो। जब भी कोई जोड़ी k से होकर छोटी हो, तो i से k की ओर का अगला नोड कॉपी करें। उस टेबल के सहारे i से j तक चलने पर पूरा रास्ता मिल जाता है।
क्या मेरा ग्राफ़ कहीं भेजा जाता है?
नहीं। ग्राफ़ आपके ब्राउज़र में ही बनता है और टेबल वहीं भरी जाती है, और आपकी पिछली सेटिंग इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ