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

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

Class	Single-source shortest path problem (for weighted directed graphs)
Data Structure	Graph
Best-Case Time Complexity	${\displaystyle \Theta (|E|)}$
Worst-Case Time Complexity	${\displaystyle \Theta (|V||E|)}$
Space Complexity	${\displaystyle \Theta (|V|)}$

बेलमैन-फोर्ड एल्गोरिथ्म एक एल्गोरिथ्म है जो एक भारित डिग्राफ(weighted Digraph) में एक एकल स्रोत के शीर्ष से अन्य सभी कोने के लिए सबसे छोटे पथों की गणना करता है। यह एक ही समस्या के लिए दिज्क्स्ट्रा के एल्गोरिथ्म की तुलना में धीमी है, लेकिन अधिक बहुमुखी है, क्योंकि यह उन ग्राफ़ को संभालने में सक्षम है जिनमें से कुछ में वजन नकारात्मक संख्याएं हैं। अल्फोंसो शिम्बेल (1955) द्वारा एल्गोरिथ्म को पहली बार प्रस्तावित किया गया था, लेकिन इसके बजाय इसका नाम रिचर्ड बेलमैन और लेस्टर फोर्ड जूनियर के नाम पर रखा गया, जिन्होंने क्रमशः 1958 और 1956 में इसे प्रकाशित किया। एडवर्ड एफ. मूर^[1] ने भी 1957 में एक ही एल्गोरिथ्म प्रकाशित किया था, और इस कारण से इसे कभी-कभी बेलमैन-फोर्ड-मूर एल्गोरिथम(Bellman–Ford–Moore algorithm)^[2] भी कहा जाता है।^[3]

कलन विधि:

निम्नलिखित विस्तृत चरण हैं।

इनपुट: ग्राफ और एक स्रोत शीर्ष (source)

आउटपुट: (source) से सभी कोने के लिए सबसे कम दूरी। यदि एक नकारात्मक वजन चक्र है, तो सबसे छोटी दूरी की गणना नहीं की जाती है, नकारात्मक वजन चक्र की सूचना दी जाती है।

• सबसे पहले source से अन्य शीर्षो की दूरी infinite  दे और source से source की दूरी 0 दे। एक सरणी सूची dist [] बनाये जिसका आकार |V| है, और सबमे INFINITE दूरी दे सिवाए source के
• यह step सबसे छोटी दूरी की गणना करता है। | V | -1 बार निम्नलिखित करें ,जहाँ | V | दिए गए ग्राफ में कोने की संख्या है।प्रत्येक किनारे (u-v) के लिए निम्नलिखित करें
  • यदि dist [v]> dist [u] + wt(uv) , तो dist[v] अपडेट करें
    • dist [v] = dist [u] + wt(uv)
• यह कदम बताता है कि क्या ग्राफ में कोई नकारात्मक भार चक्र है। प्रत्येक किनारे (u-v) के लिए निम्नलिखित करें
  • यदि dist [v]> dist [u] +wt(u v), तो "ग्राफ में निगेटिव वेट साइकल है"

(चरण 3) का विचार है, चरण 2 सबसे कम दूरी की गारंटी देता है यदि ग्राफ में नकारात्मक भार चक्र नहीं है। यदि हम सभी किनारों के माध्यम से एक और बार पुनरावृत्ति करते हैं और किसी भी शीर्ष के लिए एक छोटा रास्ता प्राप्त करते हैं, तो यहां एक नकारात्मक वजन चक्र है।

function  Bellman-Ford(list vertices, list edges, vertex s)
   do for each vertex v∈V
   d[v]← ∞
   p[v]←nil
   end do for each
   d[s]←0
   for k = 1 to the number of vertices minus 1 // |V|−1 (जो हमने चरण -2 में किया है)
        do for each edges(i,j)∈E
            if d[j] > d[i] + w(i,j) then
                d[j] := d[i] + w(i,j)
                p[j] := i
            end if
        end do for each
   end for
       
    for each edge(i,j) with weight w(i,j) in edges do  //  (जो हमने चरण -3 में किया है)
        if d[j] > d[i] + w(i,j) then
            error "Graph contains a negative-weight cycle"

    return d[], p[]

बेलमैन फोर्ड एल्गोरिथ्म मार्ग की लंबाई को शुरुआती शीर्ष से अन्य सभी शीर्षों तक कम करके काम करता है।

यह एल्गोरिथम कैसे काम करता है?

अन्य डायनामिक प्रोग्रामिंग समस्याओं की तरह, एल्गोरिथ्म एक bottom-up तरीके से सबसे छोटे रास्तों की गणना करता है। यह सबसे कम दूरी की गणना करता है, जो कि मार्ग में सबसे अधिक एक किनारे है। फिर, यह सबसे कम 2 किनारों के साथ सबसे छोटे रास्तों की गणना करता है, और इसी तरह। बाहरी लूप के ith पुनरावृत्ति के बाद, सबसे अधिक किनारों के साथ सबसे छोटे रास्तों की गणना की जाती है। अधिकतम | V | - 1   किसी भी सरल पथ में किनारे  हो सकते है, यही कारण है कि बाहरी लूप | v | - 1 बार चलता है । यह विचार है कि कोई नकारात्मक भार चक्र नहीं है, अगर हमने सबसे कम किनारों पर सबसे छोटे रास्तों की गणना की है, तो सभी किनारों पर एक पुनरावृत्ति सबसे कम (i + 1) किनारों के साथ सबसे छोटा रास्ता देने की गारंटी देता है।^[4]

बेलमैन फोर्ड एल्गोरिथम के अनुप्रयोग:

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

संदर्भ सूची:

1. "Edward F. Moore", Wikipedia (अंग्रेज़ी में), 2020-07-25, अभिगमन तिथि 2020-08-24
2. "Digraphs, theory, algorithms, applications". www.cs.rhul.ac.uk. अभिगमन तिथि 2020-08-24.
3. "Bellman–Ford algorithm", Wikipedia (अंग्रेज़ी में), 2020-08-22, अभिगमन तिथि 2020-08-24
4. "Lec 18 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005 - YouTube". www.youtube.com. अभिगमन तिथि 2020-08-24.