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

"डेवलपर्स के लिए एल्गोरिदम" पाठ्यक्रम की शुरुआत की प्रत्याशा में , उन्होंने एक दिलचस्प लेख का एक और अनुवाद तैयार किया।

---

समस्या : एक ग्राफ और एक ग्राफ में एक प्रारंभिक शीर्ष src को देखते हुए, दिए गए ग्राफ़ में src से सभी कोने तक के सबसे छोटे रास्तों को खोजना आवश्यक है। ग्राफ में नकारात्मक भार के साथ किनारे हो सकते हैं।

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

सिफारिश : समाधान को देखने के लिए आगे बढ़ने से पहले, अपने आप को अभ्यास करने का प्रयास करें।

एल्गोरिथ्म

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

इनपुट : ग्राफ और प्रारंभिक शीर्ष src ।
आउटपुट : src से सभी कोने के लिए सबसे कम दूरी। यदि नकारात्मक वजन का एक चक्र होता है, तो सबसे छोटी दूरी की गणना नहीं की जाती है, इस तरह के चक्र की उपस्थिति का संकेत देते हुए एक संदेश प्रदर्शित किया जाता है।

1. इस चरण में, प्रारंभिक शीर्ष से अन्य सभी शीर्षों की दूरी को अनंत के रूप में आरंभीकृत किया जाता है, और स्वयं src के लिए दूरी को 0. मान लिया जाता है। आकार dist[] एक सरणी dist[] |V| dist[] |V| अनंत dist[src] तत्व के अपवाद के साथ, अनंत के बराबर सभी मूल्यों के साथ, जहाँ src मूल शीर्ष है।
2. दूसरा चरण सबसे छोटी दूरी की गणना करता है। निम्नलिखित चरणों का पालन किया जाना चाहिए |V| -1 बार, कहां |V| - इस ग्राफ में कोने की संख्या।
   
   • प्रत्येक uv बढ़त के लिए निम्नलिखित क्रिया करें:
     अगर dist[v] > dist[u] + uv , तो dist[v] अपडेट करें
     dist [v] = dist [u] + uv
     
3. इस चरण में, यह बताया गया है कि क्या ग्राफ़ में एक नकारात्मक भार चक्र मौजूद है। प्रत्येक किनारे के लिए, निम्न कार्य करें:
   
   
   • यदि dist[v] > dist[u] + uv , तो ग्राफ में नकारात्मक भार का एक चक्र होता है।
     

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

यह कैसे काम करता है? अन्य गतिशील प्रोग्रामिंग कार्यों की तरह, एल्गोरिथ्म नीचे से सबसे छोटे रास्तों की गणना करता है। सबसे पहले, यह सबसे छोटी दूरी की गणना करता है, अर्थात्, एक किनारे से अधिक नहीं की लंबाई के साथ पथ। फिर यह दो किनारों और इतने पर नहीं की लंबाई के साथ सबसे छोटे रास्तों की गणना करता है। बाहरी लूप के ith पुनरावृत्ति के बाद, मैं किनारों से अधिक नहीं की लंबाई के साथ सबसे छोटे रास्तों की गणना की जाती है। किसी भी सरल पथ में, अधिकतम वी। -1 किनारे हो सकते हैं, इसलिए बाहरी लूप बिल्कुल चलता है । वी -1 -1 बार। विचार यह है कि यदि हम सबसे छोटे पथ की गणना करते हैं, जिसमें मैं किनारों से अधिक नहीं हूं , तो सभी किनारों पर पुनरावृत्ति करना, सबसे कम पथ को i + 1 किनारों के साथ प्राप्त करना है (प्रमाण काफी सरल है, आप MIT के इस व्याख्यान या वीडियो व्याख्यान का उल्लेख कर सकते हैं) )

उदाहरण

आइए एल्गोरिथ्म को निम्नलिखित ग्राफ उदाहरण में देखें। यहां से ली गई छवियां।
आरंभिक शीर्ष को 0. आज्ञा दें। सभी दूरी को अनंत मानें, केवल दूरी के अलावा src । ग्राफ़ में कुल संख्या 5 हैं, इसलिए सभी किनारों को 4 बार जाने की आवश्यकता है।



निम्नलिखित क्रम में पसलियों को काम करने दें: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), ( ई, डी)। हम निम्नलिखित दूरी प्राप्त करते हैं जब पसलियों के साथ मार्ग पहली बार पूरा हो गया था। पहली पंक्ति प्रारंभिक दूरियों को दिखाती है, दूसरी पंक्ति दूरियों को दिखाती है जब किनारों (बी, ई), (डी, बी), (बी, डी) और (ए, बी) को संसाधित किया जाता है। तीसरी पंक्ति प्रसंस्करण दूरी (ए, सी) दिखाती है। चौथी पंक्ति से पता चलता है कि क्या होता है जब (डी, सी), (बी, सी) और (ई, डी) संसाधित होते हैं।



पहला पुनरावृत्ति यह सुनिश्चित करता है कि सभी छोटे रास्ते 1 किनारे के मार्ग से अधिक नहीं हैं। जब सभी किनारों पर दूसरा पास पूरा हो जाता है (अंतिम पंक्ति अंतिम मान दिखाती है) तो हमें निम्न दूरी मिल जाती है।



दूसरा पुनरावृत्ति सुनिश्चित करता है कि सभी सबसे छोटे रास्तों की लंबाई अधिकतम 2 किनारों पर है। एल्गोरिथ्म सभी किनारों के साथ 2 और बार चलता है। दूसरी पुनरावृत्ति के बाद दूरियां कम से कम हो जाती हैं, इसलिए तीसरे और चौथे पुनरावृत्तियों दूरी के मूल्यों को अद्यतन नहीं करते हैं।

कार्यान्वयन:

 # Python program for Bellman-Ford's single source # shortest path algorithm. from collections import defaultdict # Class to represent a graph class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = [] # default dictionary to store graph # function to add an edge to graph def addEdge(self, u, v, w): self.graph.append([u, v, w]) # utility function used to print the solution def printArr(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("% d \t\t % d" % (i, dist[i])) # The main function that finds shortest distances from src to # all other vertices using Bellman-Ford algorithm. The function # also detects negative weight cycle def BellmanFord(self, src): # Step 1: Initialize distances from src to all other vertices # as INFINITE dist = [float("Inf")] * self.V dist[src] = 0 # Step 2: Relax all edges |V| - 1 times. A simple shortest # path from src to any other vertex can have at-most |V| - 1 # edges for i in range(self.V - 1): # Update dist value and parent index of the adjacent vertices of # the picked vertex. Consider only those vertices which are still in # queue for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: dist[v] = dist[u] + w # Step 3: check for negative-weight cycles. The above step # guarantees shortest distances if graph doesn't contain # negative weight cycle. If we get a shorter path, then there # is a cycle. for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: print "Graph contains negative weight cycle" return # print all distance self.printArr(dist) g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3) # Print the solution g.BellmanFord(0) # This code is contributed by Neelam Yadav 

आउटपुट मान:



टिप्पणी:

1. विभिन्न ग्राफ अनुप्रयोगों में नकारात्मक भार पाए जाते हैं। उदाहरण के लिए, एक पथ की लागत में वृद्धि के बजाय, हम एक विशिष्ट मार्ग का अनुसरण करके लाभ उठा सकते हैं।
2. बेलमैन-फोर्ड एल्गोरिथम वितरित प्रणालियों के लिए बेहतर काम करता है (डीजकस्ट्रा के एल्गोरिदम से बेहतर)। दिज्क्स्त्र के विपरीत, जहां हमें बेलमैन फोर्ड में सभी वर्टिकल का न्यूनतम मूल्य खोजने की आवश्यकता होती है, किनारों को एक समय में एक माना जाता है।

अभ्यास:

1. मानक बेलमैन-फोर्ड एल्गोरिदम केवल सबसे छोटे रास्तों की रिपोर्ट करता है, अगर उसमें नकारात्मक भार के चक्र न हों। इसे संशोधित करें ताकि इस तरह के एक चक्र होने पर भी यह सबसे छोटे रास्तों की रिपोर्ट करे।
2. क्या हम नकारात्मक वजन के साथ एक ग्राफ में सबसे छोटे रास्तों को खोजने के लिए डीजकस्ट्रा के एल्गोरिदम का उपयोग कर सकते हैं? इस तरह का एक विचार है: न्यूनतम वजन मूल्य की गणना करें, सभी भारों के लिए एक सकारात्मक मान (न्यूनतम वजन मूल्य के निरपेक्ष मूल्य के बराबर) जोड़ें और संशोधित ग्राफ के लिए डीजकस्ट्रा एल्गोरिदम को चलाएं। क्या ऐसा एल्गोरिथम काम करेगा?

बेलमैन-फोर्ड एल्गोरिथ्म का सरल कार्यान्वयन

सूत्रों का कहना है:

www.youtube.com/watch?v=Ttezuzs39nk
en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
www.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf