डाइक्स्ट्रा एल्गोरिदम

आपका रूट प्लानर आपके दरवाज़े से लगभग कहीं भी जाने का सबसे तेज़ रास्ता जानता है। इस विचार के केंद्र में एक एल्गोरिदम है, जिसे Edsger Dijkstra ने 1956 में लगभग बीस मिनट में सोचा था: शुरुआत से बाहर की ओर फैलें, और हमेशा सबसे पास वाली जगह पहले पूरी करें।

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

मूल विचार

सोचिए कि कुछ कस्बे अलग-अलग लंबाई की सड़कों से जुड़े हैं। सवाल यह है: मेरे कस्बे से हर दूसरे कस्बे तक का सबसे छोटा रास्ता कौन-सा है? जब हर सड़क बराबर गिनी जाए, तो ब्रेड्थ-फ़र्स्ट सर्च इसका जवाब देता है, लेकिन यहाँ ज़्यादा सड़कों वाला रास्ता भी छोटा हो सकता है। डाइक्स्ट्रा एल्गोरिदम हर कस्बे के लिए अब तक मिली सबसे छोटी दूरी रखता है, और उन कस्बों का एक इलाका बढ़ाता है जिनकी दूरी पक्की है, हमेशा उस सबसे पास के कस्बे को जोड़ते हुए जो अभी पक्का नहीं है।

चरण दर चरण

शुरुआत को दूरी 0 दें और बाकी हर नोड को अनंत। शुरुआत को प्रायोरिटी क्यू में रखें, यानी ऐसी क्यू जो हमेशा सबसे कम दूरी वाला नोड देती है। वह नोड लें; उसकी दूरी अब तय है। हर उस पड़ोसी के लिए जो तय नहीं है, इस नोड से होकर दूरी निकालें: इसकी दूरी और एज की लंबाई का जोड़। अगर यह पड़ोसी की अब तक की दूरी से छोटा है, तो दूरी घटाएँ, इस नोड को वहाँ तक के रास्ते के रूप में याद रखें, और पड़ोसी को क्यू में रखें। इसे एज को रिलैक्स करना कहते हैं। क्यू खाली होने तक, या लक्ष्य के क्यू से लिए जाने तक दोहराएँ।

एक उदाहरण

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

यह सही क्यों है

मान लीजिए नोड X क्यू में सबसे पास है, दूरी d पर। शुरुआत से X तक का कोई भी दूसरा रास्ता कहीं न कहीं तय नोडों के इलाके से बाहर निकलेगा, और उस इलाके के बाहर पहुँचने वाला उसका पहला नोड क्यू में है, इसलिए वह पहले से ही कम से कम d दूर है। बाकी रास्ता इसे छोटा नहीं कर सकता, क्योंकि कोई एज नेगेटिव नहीं है। इसलिए d ही X तक की सबसे छोटी दूरी है। नेगेटिव एज होने पर यह तर्क टूट जाता है; तब बेलमैन–फ़ोर्ड एल्गोरिदम इस्तेमाल होता है, जो हर एज को बार-बार रिलैक्स करता है।

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

Edsger W. Dijkstra ने यह एल्गोरिदम 1956 में एक नए कंप्यूटर, एम्स्टर्डम के ARMAC, को दिखाने के लिए बनाया, जिसमें डच शहरों के बीच रास्ते खोजे गए, और इसे 1959 में प्रकाशित किया। यही विचार, एक ज़्यादा समझदार क्यू के साथ, रूट प्लानर में चलता है और OSPF और IS-IS जैसे इंटरनेट राउटिंग प्रोटोकॉल में भी, जो राउटरों के बीच डेटा के जाने का सबसे छोटा रास्ता निकालते हैं। A* सर्च बची हुई दूरी का एक अनुमान जोड़ता है, ताकि वह लक्ष्य की ओर बढ़ सके और कम नोड देखे।

श्यामपट्ट के पास एड्स्गर डब्ल्यू. डिज्क्स्ट्रा
श्यामपट्ट के पास एड्स्गर डब्ल्यू. डिज्क्स्ट्रा

इसे आज़माएँ

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

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

डाइक्स्ट्रा एल्गोरिदम की टाइम कॉम्प्लेक्सिटी क्या है?

यह प्रायोरिटी क्यू पर निर्भर करती है। साधारण सूची के साथ V नोड के लिए O(V²); बाइनरी हीप के साथ E एज के लिए O((V + E) log V); फ़िबोनाची हीप के साथ O(E + V log V), जैसा Michael Fredman और Robert Tarjan ने 1984 में दिखाया।

क्या डाइक्स्ट्रा एल्गोरिदम नेगेटिव एज वेट संभाल सकता है?

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

क्या डाइक्स्ट्रा एल्गोरिदम हर नोड तक का रास्ता खोजता है?

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

डाइक्स्ट्रा एल्गोरिदम का A* से क्या संबंध है?

A* सर्च एक संकेत के साथ डाइक्स्ट्रा एल्गोरिदम है: यह क्यू को अब तक की दूरी और बची हुई दूरी के अनुमान के जोड़ से क्रम में लगाता है, जैसे नक्शे पर सीधी रेखा की दूरी। अच्छे अनुमान के साथ यह बहुत कम नोड देखकर वही सबसे छोटा रास्ता खोज लेता है।

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

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

डाइक्स्ट्रा एल्गोरिदम आज़माएँ