बेलमैन–फ़ोर्ड एल्गोरिदम
कुछ सबसे छोटे रास्ते वाले सवालों में ऐसे एज होते हैं जो रास्ते को सस्ता बनाते हैं: कोई रिफ़ंड, ढलान वाला हिस्सा, आपके फ़ायदे की विनिमय दर। डाइक्स्ट्रा एल्गोरिदम इन्हें नहीं संभाल पाता। बेलमैन–फ़ोर्ड एल्गोरिदम संभाल लेता है, चतुराई की जगह धीरज से।
मूल विचार
हर सबसे छोटे रास्ते वाला एल्गोरिदम एक ही चाल पर टिका है, एज को रिलैक्स करना: अगर u तक जाकर फिर एज u → v पर चलना v तक के अब तक के सबसे अच्छे रास्ते से छोटा है, तो उसे अपनाएँ। डाइक्स्ट्रा एल्गोरिदम हर एज को एक बार रिलैक्स करता है, एक चतुर क्रम में जो तभी काम करता है जब कोई एज नेगेटिव न हो। बेलमैन–फ़ोर्ड ऐसी कोई मान्यता नहीं रखता। यह हर एज को किसी भी तय क्रम में बार-बार रिलैक्स करता है, जब तक दूरियाँ बदलना बंद न कर दें।
चरण-दर-चरण
शुरुआत को दूरी 0 दें और बाकी हर नोड को अनंत। n नोड के लिए n − 1 बार दोहराएँ: हर एज u → v पर जाएँ और अगर u के पास दूरी है तो उसे रिलैक्स करें। अगर पूरे एक पास में कुछ न बदले, तो जल्दी रुकें। फिर एक और पास चलाएँ। अगर कोई एज अब भी रिलैक्स हो सके, तो शुरुआत से नेगेटिव कुल वाली किसी साइकिल तक पहुँचा जा सकता है; वरना हर दूरी सबसे छोटी है, और याद रखे गए नोड रास्ते बताते हैं।
एक उदाहरण
ये एकतरफ़ा एज लें: A → B लंबाई 4, A → C 5, B → D 2 और C → B −3, इसी क्रम में जाँचे गए, A से। पास 1 से B को 4, C को 5 और D को 6 मिलता है, और फिर C → B, B को घटाकर 5 − 3 = 2 कर देता है। पास 2, D को घटाकर 2 + 2 = 4 कर देता है। पास 3 में कुछ नहीं बदलता, इसलिए जवाब है B 2, C 5, D 4। डाइक्स्ट्रा एल्गोरिदम नेगेटिव एज देखने से पहले ही B को 4 और D को 6 पर तय कर देता। लंबाई −4 का एज D → C जोड़ें, तो साइकिल C → B → D → C का कुल −5 हो जाता है: हर पास दूरियों को फिर घटाता है, और जाँच वाला पास इसकी सूचना देता है।
n − 1 पास काफ़ी क्यों हैं
सबसे छोटा रास्ता, अगर हो, तो कभी किसी नोड को दोहराता नहीं, इसलिए उसमें ज़्यादा से ज़्यादा n − 1 एज होते हैं। एक पास में हर एज को रिलैक्स करने से हर सही-सही पता सबसे छोटा रास्ता एक एज और आगे बढ़ जाता है, एज का क्रम चाहे जो हो। इसलिए पास k के बाद k एज तक वाले सभी सबसे छोटे रास्ते सही होते हैं, और n − 1 पास के बाद सभी। फिर भी क्रम रफ़्तार पर असर डालता है: अच्छा क्रम एक-दो पास में ही खत्म हो सकता है।
इतिहास और उपयोग
अल्फ़ोंसो शिम्बेल (Alfonso Shimbel) ने यह तरीका 1955 में बताया, लेस्टर फ़ोर्ड जूनियर (Lester Ford Jr.) ने 1956 में, एडवर्ड एफ़. मूर (Edward F. Moore) ने 1957 में और रिचर्ड बेलमैन (Richard Bellman) ने 1958 में; इसका नाम इनमें से दो, बेलमैन और फ़ोर्ड, के नाम पर है। इसके पास हर राउटर खुद अकेले चला सकता है, इसलिए यह RIP जैसे डिस्टेंस-वेक्टर राउटिंग प्रोटोकॉल का आधार बना। फ़ाइनेंस में विनिमय दरों का नेगेटिव लॉगरिदम लेने से मुनाफ़े वाला मुद्रा सौदों का एक चक्कर (आर्बिट्राज) एक नेगेटिव साइकिल बन जाता है, जिसे बेलमैन–फ़ोर्ड ढूँढ सकता है।
खुद आज़माएँ
ऐप खोलें और “आगे” दबाएँ। हर एज एकतरफ़ा है, और कुछ लंबाइयाँ नेगेटिव हैं। हर चरण एक तय क्रम में एक एज जाँचता है, और टाइलें पास और उसमें बदली दूरियों की संख्या दिखाती हैं। आम तौर पर जल्द ही किसी पास में कुछ नहीं बदलता और सर्च जल्दी रुक जाती है। “नेगेटिव साइकिल जोड़ें” पर टिक करें और देखें कि दूरियाँ पास-दर-पास घटती जाती हैं, जब तक जाँच वाला पास साइकिल ढूँढकर उसे लाल रंग से न बना दे।
अक्सर पूछे जाने वाले प्रश्न
बेलमैन–फ़ोर्ड की टाइम कॉम्प्लेक्सिटी क्या है?
V नोड और E एज के लिए O(V · E): ज़्यादा से ज़्यादा V − 1 पास, हर एक में हर एज की जाँच। जल्दी रुकने की वजह से असल में यह अक्सर बहुत तेज़ होता है, और सबसे अच्छी स्थिति में एक ही पास काफ़ी है।
नेगेटिव साइकिल क्या है?
ऐसी साइकिल जिसके एज की लंबाइयों का जोड़ शून्य से कम हो। इसके बार-बार चक्कर लगाने से रास्ता जितना चाहें उतना छोटा हो जाता है, इसलिए इससे होकर पहुँचे जा सकने वाले हर नोड की सबसे छोटी दूरी तय नहीं होती।
क्या बेलमैन–फ़ोर्ड अनडायरेक्टेड ग्राफ़ पर काम करता है?
तभी जब कोई एज नेगेटिव न हो: अनडायरेक्टेड नेगेटिव एज पर आगे-पीछे जाया जा सकता है, जो खुद दो एज की एक नेगेटिव साइकिल है। नॉन-नेगेटिव एज के साथ यह काम करता है, पर डाइक्स्ट्रा एल्गोरिदम तेज़ है।
SPFA क्या है?
Shortest Path Faster Algorithm, बेलमैन–फ़ोर्ड का एक रूप जो क्यू की मदद से सिर्फ़ उन नोड से निकलने वाले एज दोबारा जाँचता है जिनकी दूरी अभी बदली है। यह अक्सर बहुत तेज़ होता है, हालाँकि इसकी सबसे बुरी स्थिति वही है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
बेलमैन–फ़ोर्ड आज़माएँ