Merge pull request geekquad#39 from ashneg/master

geekquad · web-flow · commit 2fdd42ffa53c · 2020-10-01T03:38:04.000+05:30
Added bellman-ford-algorithm
diff --git a/python/graph_algorithms/bellman_ford_algorithm.py b/python/graph_algorithms/bellman_ford_algorithm.py
@@ -0,0 +1,42 @@
+# Python3 program for Bellman-Ford's single source 
+
+class Graph: 
+
+	def __init__(self, vertices): 
+		self.V = vertices 
+		self.graph = [] 
+
+	def addEdge(self, u, v, w): 
+		self.graph.append([u, v, w]) 
+	def printArr(self, dist): 
+		print("Vertex Distance from Source") 
+		for i in range(self.V): 
+			print("{0}\t\t{1}".format(i, dist[i]))
+	def BellmanFord(self, src): 
+		dist = [float("Inf")] * self.V 
+		dist[src] = 0
+
+		for _ in range(self.V - 1): 
+			for u, v, w in self.graph: 
+				if dist[u] != float("Inf") and dist[u] + w < dist[v]: 
+						dist[v] = dist[u] + w 
+
+		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
+		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) 
+
