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

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

स्पष्टीकरण

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

सामान्य लघुतम पथ एल्गोरिथम

कुछ सामान्य लघुतम पथ एल्गोरिथम हैं -

• बेलमैन फोर्ड का एल्गोरिथम

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

• फ़्लॉइड वारशॉल का एल्गोरिथम

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

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

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

आउटपुट - s से अन्य सभी नोड्स के लिए सबसे छोटा रास्ता।

• s से सभी नोड्स की दूरी को अनंत (∞) के रूप में प्रारंभ करें; खुद से दूरी 0 के रूप में; एक सरणी dist[] आकार का |V| (नोड्स की संख्या) dist[s] . को छोड़कर के रूप में सभी मानों के साथ ।

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

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

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

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

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

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

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

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

आरंभीकरण -

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

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

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

• प्रश्न . के दौरान दोहराएं खाली नहीं है -

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

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

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

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

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

• सरणी dist[] s . से सबसे छोटा पथ शामिल है हर दूसरे नोड के लिए।

फ़्लॉइड वॉरशैल एल्गोरिथम

इनपुट - एक लागत आसन्नता मैट्रिक्स, adj[][] , नेटवर्क में नोड्स के बीच पथ का प्रतिनिधित्व करता है।

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

• लागत [] [] पॉप्युलेट करें इस प्रकार है:

  • अगर adj[][] खाली है तो लागत[][] =(अनंत)

  • वरना लागत[][] =adj[][]

• एन =|वी| , जहां V नेटवर्क में नोड्स के सेट का प्रतिनिधित्व करता है।

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

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

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

      • अगर लागत[i][k] + लागत[k][j] <लागत[i][j] , फिर

        • अपडेट करें लागत[i][j] :=लागत[i][k] + लागत[k][j]

• मैट्रिक्स लागत[][] प्रत्येक नोड से न्यूनतम लागत शामिल है, i , हर दूसरे नोड के लिए, j ।