- मौजूदा
- दूरी मिली
- इस्तेमाल हुआ एज
- रास्ता
- नेगेटिव साइकिल
बेलमैन–फ़ोर्ड एल्गोरिदम
जब किसी एज की लंबाई नेगेटिव हो, तो डाइक्स्ट्रा एल्गोरिदम गड़बड़ा जाता है, जैसे कोई सड़क टोल लेने की जगह आपको पैसे दे। बेलमैन–फ़ोर्ड एल्गोरिदम नहीं गड़बड़ाता: यह बस हर एज को बार-बार जाँचता है, जब तक कुछ भी बेहतर न हो, और यह भी पहचान लेता है कि कब कोई साइकिल दूरियों को हमेशा घटाती रहती है। किसी नोड पर क्लिक करके वहीं से शुरू करें और पास-दर-पास देखें। सर्च देखने के लिए “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। हर एज एकतरफ़ा है, जैसा उसका तीर दिखाता है, और उस पर लिखी संख्या उसकी लंबाई है, जो नेगेटिव भी हो सकती है। किसी नोड को शुरुआत बनाने के लिए उस पर क्लिक करें; क्लिक को “लक्ष्य” पर बदलें और किसी दूसरे नोड पर क्लिक करें, ताकि आखिर में उस तक का सबसे छोटा रास्ता दिखे। हर नोड पर लिखी संख्या अब तक की उसकी दूरी है। बेलमैन–फ़ोर्ड नेगेटिव साइकिल कैसे ढूँढता है, यह देखने के लिए “नेगेटिव साइकिल जोड़ें” पर टिक करें। “नया ग्राफ़” दूसरा ग्राफ़ बनाता है; उसमें कितने नोड और एज हों, यह चुनें। बोर्ड चुना होने पर, ऐरो कुंजियाँ एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।
यह कैसे काम करता है
- किसी नोड को शुरुआत बनाने के लिए उस पर क्लिक करें। आखिर में रास्ता देखने के लिए क्लिक को “लक्ष्य” पर बदलें और किसी दूसरे नोड पर क्लिक करें।
- “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” का इस्तेमाल करें। कहीं भी जाने के लिए चरण स्लाइडर खींचें।
- बेलमैन–फ़ोर्ड को नेगेटिव साइकिल ढूँढते देखने के लिए “नेगेटिव साइकिल जोड़ें” पर टिक करें। “नया ग्राफ़” आज़माने के लिए दूसरा ग्राफ़ बनाता है।
बेलमैन–फ़ोर्ड कैसे काम करता है
शुरुआत को दूरी 0 दें और बाकी हर नोड को अनंत। फिर पास चलाएँ: हर पास में हर एज u → v को एक बार जाँचें। अगर u के पास दूरी है और dist(u) में एज की लंबाई जोड़ने पर वह dist(v) से छोटी है, तो dist(v) घटाएँ और वहाँ तक के रास्ते के रूप में u याद रखें। पास k के बाद, ज़्यादा से ज़्यादा k एज वाला हर सबसे छोटा रास्ता पता होता है। सबसे छोटा रास्ता हर नोड पर ज़्यादा से ज़्यादा एक बार जाता है, इसलिए उसमें ज़्यादा से ज़्यादा n − 1 एज होते हैं, और n − 1 पास हमेशा काफ़ी हैं। अगर पूरे एक पास में कुछ न बदले, तो सर्च जल्दी रुक सकती है।
नेगेटिव साइकिल ढूँढना
अगर किसी साइकिल के एज का जोड़ शून्य से कम हो, तो उसका एक और चक्कर रास्ते को हमेशा छोटा कर देता है, इसलिए कोई सबसे छोटा रास्ता होता ही नहीं। बेलमैन–फ़ोर्ड इसे पकड़ लेता है: n − 1 पास के बाद एक और पास में कुछ नहीं बदलना चाहिए। अगर कोई एज अब भी रिलैक्स हो सके, तो शुरुआत से एक नेगेटिव साइकिल तक पहुँचा जा सकता है, और उस एज से याद रखे गए नोड के सहारे पीछे चलने पर आप उस साइकिल में पहुँचते हैं। ऐप में साइकिल लाल रंग से बनी है।
अक्सर पूछे जाने वाले प्रश्न
बेलमैन–फ़ोर्ड एल्गोरिदम क्या है?
एक एल्गोरिदम जो ऐसे ग्राफ़ में एक शुरुआत से बाकी हर नोड तक के सबसे छोटे रास्ते ढूँढता है जिसके एज की लंबाई नेगेटिव हो सकती है। यह बार-बार के पास में हर एज को रिलैक्स करता है, और अगर शुरुआत से कोई नेगेटिव साइकिल तक पहुँचा जा सके, तो उसकी सूचना देता है।
नेगेटिव एज के साथ डाइक्स्ट्रा एल्गोरिदम क्यों नाकाम होता है?
डाइक्स्ट्रा किसी नोड की दूरी तभी तय कर देता है जब वह क्यू में सबसे पास होता है। बाद में मिला कोई नेगेटिव एज अब भी किसी छोटे रास्ते से उस नोड पर वापस ला सकता है, इसलिए तय दूरी गलत हो सकती है। बेलमैन–फ़ोर्ड कभी कोई दूरी जल्दी तय नहीं करता; यह हर एज को जाँचता रहता है।
n − 1 पास ही क्यों?
सबसे छोटे रास्ते को किसी नोड पर दो बार जाने की ज़रूरत नहीं पड़ती, इसलिए उसमें ज़्यादा से ज़्यादा n − 1 एज होते हैं। हर पास पता चले सबसे छोटे रास्तों को कम से कम एक एज आगे बढ़ाता है, इसलिए n − 1 पास के बाद सब मिल जाते हैं।
बेलमैन–फ़ोर्ड कितना तेज़ है?
हर पास सभी E एज जाँचता है और ज़्यादा से ज़्यादा V − 1 पास होते हैं, इसलिए काम V × E के साथ बढ़ता है। यह डाइक्स्ट्रा एल्गोरिदम से धीमा है, इसीलिए बेलमैन–फ़ोर्ड तब इस्तेमाल होता है जब एज नेगेटिव हो सकते हैं।
क्या मेरा ग्राफ़ कहीं भेजा जाता है?
नहीं। ग्राफ़ आपके ब्राउज़र में ही बनता और खोजा जाता है, और आपकी पिछली सेटिंग इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ