लघुतम पथ एल्गोरिदम

लघुतम पथ एल्गोरिदम भारित ग्राफ में शीर्षों के बीच न्यूनतम-भार वाले मार्गों की गणना करते हैं, जिसमें विभिन्न एल्गोरिदम गैर-ऋणात्मक भार, ऋणात्मक भार, और सभी-जोड़ी बनाम एकल-स्रोत प्रश्नों के लिए उपयुक्त होते हैं।

Definition

एक भारित ग्राफ में दो शीर्षों के बीच एक लघुतम पथ वह पथ होता है जिसका कुल किनारा भार न्यूनतम होता है; लघुतम पथ एल्गोरिदम ऐसे पथों और उनकी दूरियों की गणना करते हैं, या तो एक स्रोत से सभी शीर्षों तक या शीर्षों के सभी जोड़ों के बीच।

Scope

यह विषय एकल-स्रोत लघुतम पथों (गैर-ऋणात्मक भार के लिए डाइकस्ट्रा का एल्गोरिदम, ऋणात्मक भार वाले ग्राफ के लिए और ऋणात्मक चक्रों का पता लगाने के लिए बेलमैन-फोर्ड), सभी-जोड़ी लघुतम पथों (फ्लॉइड-वॉर्शल, जॉनसन का एल्गोरिदम), और निर्देशित चक्रीय ग्राफ में लघुतम पथों को शामिल करता है। यह इन विधियों के लिए सामान्य शिथिलीकरण सिद्धांत (relaxation principle) और कुशल कार्यान्वयन में प्राथमिकता कतारों (priority queues) की भूमिका पर विचार करता है। यह ब्रेड्थ-फर्स्ट सर्च (breadth-first search) द्वारा प्राप्त अभारित लघुतम पथों को बाहर करता है, जिन्हें ग्राफ ट्रैवर्सल (graph traversal) के तहत कवर किया गया है।

Core questions

• किनारे का शिथिलीकरण (edge relaxation) दूरी के अनुमानों को वास्तविक लघुतम दूरियों की ओर उत्तरोत्तर कैसे कसता है?
• डाइकस्ट्रा के एल्गोरिदम को सही होने के लिए गैर-ऋणात्मक किनारे के भार की आवश्यकता क्यों होती है?
• बेलमैन-फोर्ड ऋणात्मक भार को कैसे संभालता है और ऋणात्मक चक्रों का पता कैसे लगाता है?
• एकल-स्रोत विधि को दोहराने की तुलना में सभी-जोड़ी लघुतम पथों की गणना कब अधिक कुशल होती है?
• प्राथमिकता-कतार के विकल्प डाइकस्ट्रा के एल्गोरिदम के चलने के समय को कैसे प्रभावित करते हैं?

Key concepts

• किनारे का शिथिलीकरण (edge relaxation)
• एकल-स्रोत लघुतम पथ
• डाइकस्ट्रा का एल्गोरिदम
• बेलमैन-फोर्ड एल्गोरिदम
• ऋणात्मक-भार चक्र
• सभी-जोड़ी लघुतम पथ
• फ्लॉइड-वॉर्शल एल्गोरिदम
• प्राथमिकता-कतार कार्यान्वयन

Key theories

किनारे का शिथिलीकरण और लालची चयन (greedy selection)

लघुतम-पथ एल्गोरिदम बार-बार किनारों को शिथिल करते हैं, जब एक छोटा मार्ग मिलता है तो दूरी के अनुमान को बदलते हैं; डाइकस्ट्रा का एल्गोरिदम लालची तरीके से निकटतम अनसुलझे शीर्ष को अंतिम रूप देता है, जो सटीक रूप से सही होता है क्योंकि किनारे के भार गैर-ऋणात्मक होते हैं।

सभी-जोड़ी पथों के लिए गतिशील प्रोग्रामिंग

फ्लॉइड-वॉर्शल एल्गोरिदम मध्यवर्ती शीर्षों पर एक गतिशील प्रोग्राम द्वारा सभी-जोड़ी लघुतम पथों की गणना करता है, जो क्यूबिक समय में चलता है और स्वाभाविक रूप से ऋणात्मक किनारे के भार (ऋणात्मक चक्रों के बिना) को संभालता है।

Clinical relevance

लघुतम-पथ एल्गोरिदम नेविगेशन और मैपिंग सेवाओं, नेटवर्क में पैकेट रूटिंग प्रोटोकॉल, लॉजिस्टिक्स में मार्ग योजना, और किसी भी प्रणाली को शक्ति प्रदान करते हैं जो एक भारित नेटवर्क के माध्यम से न्यूनतम-लागत वाले पथों को ढूंढती है, जिसमें गेम पाथफाइंडिंग और स्थानिक विश्लेषण में संसाधन-दूरी गणना शामिल है।

History

डाइकस्ट्रा ने 1959 में अपना एकल-स्रोत लघुतम-पथ एल्गोरिदम प्रकाशित किया। बेलमैन-फोर्ड एल्गोरिदम, जो ऋणात्मक भार को संभालता है, 1950 के दशक के अंत में बेलमैन, फोर्ड और मूर के काम से उभरा। वॉर्शल की ट्रांजिटिव-क्लोजर विधि (transitive-closure method) पर आधारित फ्लॉइड का 1962 का एल्गोरिदम, एक कॉम्पैक्ट सभी-जोड़ी समाधान प्रदान करता है जो एक मानक बना हुआ है।

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford
• Robert W. Floyd

Seminal works

• dijkstra1959
• floyd1962
• cormen2009

Frequently asked questions

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

डाइकस्ट्रा का एल्गोरिदम निकटतम अनसुलझे शीर्ष को अंतिम रूप देता है और इसे कभी भी दोबारा नहीं देखता है, यह मानते हुए कि कोई भी बाद का पथ छोटा नहीं हो सकता है। एक ऋणात्मक किनारा एक शीर्ष के तय होने के बाद ऐसा एक छोटा पथ बना सकता है, जिससे यह धारणा टूट जाती है। इसके बजाय बेलमैन-फोर्ड का उपयोग किया जाता है, जो सभी किनारों को बार-बार शिथिल करता है।

मुझे प्रत्येक शीर्ष से डाइकस्ट्रा को चलाने के बजाय सभी-जोड़ी एल्गोरिदम का उपयोग कब करना चाहिए?

घने ग्राफ के लिए या जब कई या सभी स्रोत-गंतव्य दूरियों की आवश्यकता होती है, तो फ्लॉइड-वॉर्शल की सरल क्यूबिक-टाइम सभी-जोड़ी गणना अक्सर बेहतर होती है। विरल ग्राफ के लिए, प्रत्येक स्रोत से डाइकस्ट्रा (या ऋणात्मक भार के लिए जॉनसन का एल्गोरिदम) चलाना स्पर्शोन्मुख रूप से तेज हो सकता है।