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