दीजकस्ट्रा का एल्गोरिदम। ग्राफ़ पर इष्टतम मार्गों की खोज करें

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



उदाहरण के लिए, उन्मुख ग्राफ G को लें:











हम मैट्रिक्स C के रूप में इस ग्राफ का प्रतिनिधित्व कर सकते हैं:







वर्टेक्स 1 को एक स्रोत के रूप में लें। इसका मतलब है कि हम शीर्ष 1 से लेकर कोने 2, 3, 4 और 5 तक के सबसे छोटे मार्गों की खोज करेंगे।

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



1 वर्टेक्स को 0 के बराबर लेबल असाइन करें, क्योंकि यह वर्टेक्स स्रोत है। शेष कोने को अनंत के बराबर लेबल सौंपा जाएगा।







अगला, हम एक वर्टेक्स डब्ल्यू चुनते हैं जिसमें एक न्यूनतम लेबल होता है (अब यह वर्टेक्स 1 है) और सभी शीर्षों पर विचार करें जिसमें से वर्टेक्स डब्ल्यू एक रास्ता है जिसमें मध्यस्थ कोने शामिल नहीं हैं। हम विचाराधीन लेबल W के योग और W से शीर्ष तक मार्ग की लंबाई के बराबर माने जाने वाले प्रत्येक कोने पर एक लेबल लगाते हैं, लेकिन केवल तभी प्राप्त होता है जब प्राप्त राशि पिछले लेबल मान से कम होती है। यदि राशि कम नहीं है, तो पिछले लेबल को अपरिवर्तित छोड़ दें।







हमने उन सभी छोरों की जांच की है, जिनमें W से एक सीधा रास्ता है, हम विज़ेट को W के रूप में चिह्नित करते हैं, और उन लोगों में से चुनते हैं, जिन्होंने अभी तक विज़िट नहीं की है, जिसमें न्यूनतम लेबल मान है, यह अगला शीर्ष W होगा। इस मामले में, यह शीर्ष 2 है या 5. यदि एक ही लेबल के साथ कई कोने हैं, तो इससे कोई फर्क नहीं पड़ता कि हम डब्ल्यू के रूप में किसे चुनते हैं।



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







तस्वीर के आधार पर, हम देख सकते हैं कि तीसरी और चौथी चोटियों के लेबल छोटे हो गए हैं, अर्थात इन चोटियों का एक छोटा मार्ग स्रोत के ऊपर से पाया गया था। अगला, 5 वें शीर्ष पर जाएँ के रूप में चिह्नित करें और अगले लेबल का चयन करें जिसमें न्यूनतम लेबल हो। हम उपरोक्त सभी कार्रवाइयों को तब तक दोहराते हैं जब तक कि अप्रकाशित चोटियाँ न हों।



सभी कार्यों को पूरा करने के बाद हमें निम्नलिखित परिणाम मिलते हैं:







एक वेक्टर पी भी है, जिसमें से सबसे छोटे मार्गों का निर्माण संभव है। तत्वों की संख्या से, यह वेक्टर ग्राफ में कोने की संख्या के बराबर है। प्रत्येक तत्व में स्रोत शीर्ष और अंतिम शीर्ष के बीच कम से कम पथ पर अंतिम मध्यवर्ती शीर्ष होता है। एल्गोरिथ्म की शुरुआत में, वेक्टर पी के सभी तत्व स्रोत के शीर्ष के बराबर होते हैं (हमारे मामले में, पी = {1, 1, 1, 1, 1})। अगला, विचाराधीन शीर्ष के लिए लेबल मान को पुन: परिकलित करने के चरण में, यदि विचाराधीन लेबल शीर्ष पर एक छोटे से बदल जाता है, तो हम सरणी P के लिए वर्तमान वर्टेक्स W का मान लिखते हैं। उदाहरण के लिए: 3rd वर्टेक्स का मान W के साथ "30", के लिए एक लेबल था W = 1। इसके अलावा, डब्ल्यू = 5 पर, 3 वर्टेक्स का लेबल "20" में बदल गया, इसलिए हम वेक्टर पी - पी [3] = 5 में मान लिखेंगे। इसके अलावा, W = 5 पर, 4 वें शीर्ष पर लेबल मान बदल गया (यह "50" था, यह "40") बन गया, इसलिए आपको वेक्टर P के 4 तत्व को W - P [4] = 5 पर सेट करने की आवश्यकता है। नतीजतन, हम वेक्टर पी = {1, 1, 5, 5, 1} प्राप्त करते हैं।



यह जानते हुए कि वेक्टर पी के प्रत्येक तत्व में स्रोत और अंतिम शीर्ष के बीच के मार्ग पर अंतिम मध्यवर्ती शीर्ष रिकॉर्ड किया जाता है, हम स्वयं सबसे छोटा मार्ग प्राप्त कर सकते हैं।