कंप्यूटर नेटवर्क में शॉर्टेस्ट पाथ एल्गोरिदम

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

व्याख्या

मान लें कि एक नेटवर्क में N वर्टेक्स (नोड्स या नेटवर्क डिवाइस) हैं जो M एजेस (ट्रांसमिशन लाइन्स) द्वारा जुड़े हुए हैं। प्रत्येक एज एक वजन से जुड़ी होती है, जो ट्रांसमिशन लाइन की भौतिक दूरी या ट्रांसमिशन देरी को दर्शाती है। शॉर्टेस्ट पाथ एल्गोरिदम का लक्ष्य किन्हीं दो वर्टेक्स के बीच एजेस के साथ एक रूट ढूंढना है, ताकि एजेस के वजन का योग न्यूनतम हो। यदि एजेस समान वजन की हैं, तो शॉर्टेस्ट पाथ एल्गोरिदम न्यूनतम हॉप्स वाले रूट को ढूंढने का लक्ष्य रखता है।

सामान्य शॉर्टेस्ट पाथ एल्गोरिदम

कुछ सामान्य शॉर्टेस्ट पाथ एल्गोरिदम हैं –

• बेलमैन-फोर्ड एल्गोरिदम

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

• फ्लॉयड-वार्शल एल्गोरिदम

निम्न खंड इनमें से प्रत्येक एल्गोरिदम का वर्णन करते हैं।

बेलमैन-फोर्ड एल्गोरिदम

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

आउटपुट – s से अन्य सभी नोड्स तक सबसे छोटा पथ।

• s से सभी नोड्स की दूरियों को अनंत (∞) के रूप में इनिशियलाइज़ करें; स्वयं से दूरी 0; आकार |V| (नोड्स की संख्या) का एक ऐरे dist[] जहां सभी मान ∞ हैं सिवाय dist[s] के।

• सबसे छोटी दूरियों की गणना पुनरावृत्ति से करें। |V|- 1 बार प्रत्येक नोड के लिए s को छोड़कर दोहराएं –

  • वर्टेक्स u और v को जोड़ने वाले प्रत्येक एज के लिए दोहराएं –

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

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

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

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

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

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

आरंभीकरण –

• दूरियों का एक ऐरे dist[] आकार |V| (नोड्स की संख्या) का, जहां 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 से हर दूसरे नोड तक सबसे छोटा पथ होता है।

फ्लॉयड-वार्शल एल्गोरिदम

इनपुट – एक कॉस्ट एडजेसेंसी मैट्रिक्स, adj[][], जो नेटवर्क में नोड्स के बीच पथों को दर्शाता है।

आउटपुट – एक शॉर्टेस्ट पाथ कॉस्ट मैट्रिक्स, cost[][], जो ग्राफ में नोड्स के प्रत्येक जोड़े के बीच कॉस्ट के संदर्भ में सबसे छोटे पथ दिखाता है।

• cost[][] को निम्नानुसार भरें:

  • यदि adj[][] खाली है तो cost[][] = ∞ (अनंत)

  • अन्यथा cost[][] = adj[][]

• N = |V|, जहां V नेटवर्क में नोड्स का सेट दर्शाता है।

• k = 1 से N तक दोहराएं –

  • i = 1 से N तक दोहराएं –

    • j = 1 से N तक दोहराएं –

      • यदि cost[i][k] + cost[k][j] < cost[i][j], तो

        • cost[i][j] := cost[i][k] + cost[k][j] अपडेट करें

• मैट्रिक्स cost[][] में प्रत्येक नोड i से हर दूसरे नोड j तक सबसे छोटी कॉस्ट होती है।