दिज्क्स्ट्रा का एल्गोरिथ्म एक ग्राफ के माध्यम से सबसे छोटे पथ की गणना करने के लिए

परिभाषा

दिज्क्स्ट्रा का एल्गोरिथ्म एक विशेष नोड से सबसे छोटा रास्ता खोजता है, जिसे स्रोत नोड कहा जाता है जो एक जुड़े हुए ग्राफ में हर दूसरे नोड के लिए होता है। यह स्रोत नोड के साथ रूट के रूप में सबसे छोटा पथ वृक्ष उत्पन्न करता है। रूटिंग लागत को कम करने के उद्देश्य से इष्टतम मार्ग उत्पन्न करने के लिए कंप्यूटर नेटवर्क में इसका गहराई से उपयोग किया जाता है।

डिजस्ट्रा का एल्गोरिथम

इनपुट - नेटवर्क का प्रतिनिधित्व करने वाला एक ग्राफ; और एक स्रोत नोड, एस

आउटपुट - एक सबसे छोटा पथ वृक्ष, एसपीटी [], एस के साथ रूट नोड के रूप में।

आरंभीकरण -

• दूरियों की एक सरणी dist[] आकार का |V| (नोड्स की संख्या), जहां जिला[s] =0 और जिला[यू] =∞ (अनंत), जहां आप s को छोड़कर ग्राफ में एक नोड का प्रतिनिधित्व करते हैं।

• एक सरणी, प्रश्न , ग्राफ में सभी नोड्स युक्त। जब एल्गोरिथम पूरा हो जाता है, Q खाली हो जाएगा।

• एक खाली सेट, एस , जिसमें विज़िट किए गए नोड्स जोड़े जाएंगे। जब एल्गोरिथम पूरा हो जाता है, S ग्राफ़ में सभी नोड शामिल होंगे।

• दोहराते समय प्रश्न खाली नहीं है -

  • प्रश्न . से निकालें , नोड, आपका सबसे छोटा dist[u] . है और जो एस में नहीं है। पहले रन में, dist[s] हटा दिया गया है।

  • आपको S में जोड़ें, आपको विज़िट किया गया के रूप में चिह्नित करें।

  • प्रत्येक नोड v के लिए, जो u के निकट है, dist[v] को -

    . के रूप में अपडेट करें

    • अगर (जिला[यू] + किनारे का वजन u-v ) <जिला[v], फिर

      • अपडेट dist[v] =dist[u] + किनारे का वजन u-v

• सरणी जिला[] इसमें s से हर दूसरे नोड तक का सबसे छोटा रास्ता होता है।

उदाहरण

एल्गोरिथम की कार्यप्रणाली को एक उदाहरण का उपयोग करके सबसे अच्छी तरह से समझा जा सकता है। निम्नलिखित ग्राफ पर विचार करें जिसमें ए से जी तक चिह्नित नोड्स हैं, जो भारित किनारों से जुड़े हुए हैं -

इनिशियलाइज़ेशन इस प्रकार होगा -

• जिला[7]={0,∞,∞,∞,∞,∞,∞}

• क्यू={ए,बी,सी,डी,ई,एफ,जी}

• एस𝑆=

पास 1 - हम नोड A . चुनते हैं प्रश्न . से चूंकि इसका सबसे कम जिला[] . है 0 . का मान और इसे एस में रखें। ए के पड़ोसी नोड्स बी और सी हैं। हम एल्गोरिदम के अनुसार बी और सी के अनुरूप डिस्ट [] मानों को अपडेट करते हैं। तो डेटा संरचनाओं के मान बन जाते हैं -

• जिला[7]={0,5,6,∞,∞,∞,∞}

• क्यू={बी,सी,डी,ई,एफ,जी}

• एस={ए}

इस दर्रे के बाद की दूरी और सबसे छोटा रास्ता निम्नलिखित ग्राफ में दिखाया गया है। हरा नोड पहले से ही S में जोड़े गए नोड को दर्शाता है -

2 पास करें - हम नोड B . चुनते हैं प्रश्न . से चूंकि इसका सबसे कम जिला[] . है 5 . का मान और इसे S. . में डालें B के पड़ोसी नोड C, D . हैं और ई . हम C, D . के अनुरूप dist[] मान अपडेट करते हैं और ई एल्गोरिथम के अनुसार। तो डेटा संरचनाओं के मान बन जाते हैं -

• जिला[7]={0,5,6,12,13,∞,∞}

• क्यू={सी,डी,ई,एफ,जी}

• एस={ए,बी}

इस दर्रे के बाद की दूरी और सबसे छोटे रास्ते हैं -

3 पास करें - हम नोड C . चुनते हैं प्रश्न . से चूंकि इसका सबसे कम dist[] 6 का मान है और इसे S में रखें। C के पड़ोसी नोड D और F हैं। हम D और F के अनुरूप dist[] मानों को अपडेट करते हैं। इसलिए डेटा संरचनाओं के मान बन जाते हैं -

• जिला[7]={0,5,6,8,13,10,∞}

• क्यू={डी,ई,एफ,जी}

• एस={ए,बी,सी}

इस दर्रे के बाद की दूरी और सबसे छोटे रास्ते हैं -

4 पास करें - हम नोड चुनते हैं D प्रश्न . से चूंकि इसका सबसे कम जिला[ . है ] 8 का मान और इसे S में डालें। D के पड़ोसी नोड E, F और G हैं। हम dist[] को अपडेट करते हैं E, F . से संबंधित मान और जी . तो डेटा संरचनाओं के मान बन जाते हैं -

• जिला[7]={0,5,6,8,10,10,18}

• क्यू={ई,एफ,जी}

• एस={ए,बी,सी,डी}

इस दर्रे के बाद की दूरी और सबसे छोटे रास्ते हैं -

पांच पास करें - हम या तो नोड E या नोड F . चुन सकते हैं प्रश्न . से चूंकि दोनों में सबसे कम जिला[] . है 10 . का मान . हम उनमें से किसी एक का चयन करते हैं, जैसे E , और इसे S . में डालें . D . के पड़ोसी नोड जी . है . हम अपडेट करते हैं जिला[] जी के अनुरूप मान। तो डेटा संरचनाओं के मूल्य बन जाते हैं -

• जिला[7]={0,5,6,8,10,10,13}

• क्यू={एफ,जी}

• एस={ए,बी,सी,डी,ई}

इस दर्रे के बाद की दूरी और सबसे छोटे रास्ते हैं -

6 पास करें - हम नोड F . चुनते हैं प्रश्न . से चूंकि इसका सबसे कम जिला[] . है 10 . का मान और इसे S . में डालें . F . के पड़ोसी नोड जी . है . जिला[] G के संगत मान F . से कम है . तो यह वही रहता है। डेटा संरचनाओं के मान बन जाते हैं -

• जिला[7]={0,5,6,8,10,10,13}

• क्यू={जी}

• एस={ए,बी,सी,डी,ई,एफ}

इस दर्रे के बाद की दूरी और सबसे छोटे रास्ते हैं -

7 पास करें − Q . में सिर्फ एक नोड होता है . हम इसे प्रश्न . से हटा देते हैं इसे एस में रखें। डिस्ट [] सरणी को किसी बदलाव की आवश्यकता नहीं है। अब, प्रश्न खाली हो जाता है, S सभी नोड्स शामिल हैं और इसलिए हम एल्गोरिथम के अंत में आते हैं। हम उन सभी किनारों या मार्गों को समाप्त कर देते हैं जो किसी मार्ग के मार्ग में नहीं हैं। तो स्रोत नोड A से अन्य सभी नोड्स के लिए सबसे छोटा पथ ट्री इस प्रकार है -