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

परिभाषा

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

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

इनपुट – नेटवर्क को दर्शाता एक ग्राफ; और एक सोर्स नोड, s

आउटपुट – एक शॉर्टेस्ट पाथ ट्री, spt[], जिसमें s रूट नोड है।

आरंभीकरण –

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

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

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

• Q खाली नहीं है तब तक दोहराएं –

  • Q से, नोड u को हटाएं जिसका सबसे छोटा dist[u] है और जो S में नहीं है। पहले रन में, dist[s] हटाया जाता है।

  • u को S में जोड़ें, u को विजिटेड मार्क करें।

  • प्रत्येक नोड v के लिए जो u से सटा हुआ है, dist[v] को अपडेट करें –

    • यदि (dist[u] + u-v एज का वजन) < dist[v], तो

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

• ऐरे dist[] में s से हर दूसरे नोड तक सबसे छोटा पथ होता है।

उदाहरण

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

आरंभीकरण निम्न होंगे –

• dist[7]={0,∞,∞,∞,∞,∞,∞}

• Q={A,B,C,D,E,F,G}

• S=∅

पास 1 – हम Q से नोड A चुनते हैं क्योंकि इसका सबसे कम dist[] मान 0 है और इसे S में डालते हैं। A के पड़ोसी नोड्स B और C हैं। हम एल्गोरिदम के अनुसार B और C के अनुरूप dist[] मान अपडेट करते हैं। तो डेटा स्ट्रक्चर्स के मान बन जाते हैं –

• dist[7]={0,5,6,∞,∞,∞,∞}

• Q={B,C,D,E,F,G}

• S={A}

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

पास 2 – हम Q से नोड B चुनते हैं क्योंकि इसका सबसे कम dist[] मान 5 है और इसे S में डालते हैं। B के पड़ोसी नोड्स C, D और E हैं। हम एल्गोरिदम के अनुसार C, D और E के अनुरूप dist[] मान अपडेट करते हैं। तो डेटा स्ट्रक्चर्स के मान बन जाते हैं –

• dist[7]={0,5,6,12,13,∞,∞}

• Q={C,D,E,F,G}

• S={A,B}

इस पास के बाद दूरियां और सबसे छोटे पथ हैं –

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

• dist[7]={0,5,6,8,13,10,∞}

• Q={D,E,F,G}

• S={A,B,C}

इस पास के बाद दूरियां और सबसे छोटे पथ हैं –

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

• dist[7]={0,5,6,8,10,10,18}

• Q={E,F,G}

• S={A,B,C,D}

इस पास के बाद दूरियां और सबसे छोटे पथ हैं –

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

• dist[7]={0,5,6,8,10,10,13}

• Q={F,G}

• S={A,B,C,D,E}

इस पास के बाद दूरियां और सबसे छोटे पथ हैं –

पास 6 – हम Q से नोड F चुनते हैं क्योंकि इसका सबसे कम dist[] मान 10 है और इसे S में डालते हैं। F का पड़ोसी नोड G है। G के अनुरूप dist[] मान F के माध्यम से उससे कम है। इसलिए यह वही रहता है। डेटा स्ट्रक्चर्स के मान बन जाते हैं –

• dist[7]={0,5,6,8,10,10,13}

• Q={G}

• S={A,B,C,D,E,F}

इस पास के बाद दूरियां और सबसे छोटे पथ हैं –

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