fork download
copy 
  1. class Graph:
  2.  
  3. 	def __init__(self, vertices):
  4. 		self.V = vertices
  5. 		self.graph = []
  6.  
  7. 	def addEdge(self, u, v, w):
  8. 		self.graph.append([u, v, w])
  9.  
  10. 	def printArr(self, dist):
  11. 		print("Vertex Distance from Source")
  12. 		for i in range(self.V):
  13. 			print("{0}\t\t{1}".format(i, dist[i]))
  14.  
  15. 	def BellmanFord(self, src):
  16.  
  17. 		dist = [float("Inf")] * self.V
  18. 		dist[src] = 0
  19.  
  20. 		for _ in range(self.V - 1):
  21. 			for u, v, w in self.graph:
  22. 				if dist[u] != float("Inf") and dist[u] + w < dist[v]:
  23. 					dist[v] = dist[u] + w
  24.  
  25. 		for u, v, w in self.graph:
  26. 			if dist[u] != float("Inf") and dist[u] + w < dist[v]:
  27. 				print("Graph contains negative weight cycle")
  28. 				return
  29.  
  30. 		self.printArr(dist)
  31.  
  32. if __name__ == '__main__':
  33. 	g = Graph(5)
  34. 	g.addEdge(0, 1, -1)
  35. 	g.addEdge(0, 2, 4)
  36. 	g.addEdge(1, 2, 3)
  37. 	g.addEdge(1, 3, 2)
  38. 	g.addEdge(1, 4, 2)
  39. 	g.addEdge(3, 2, 5)
  40. 	g.addEdge(3, 1, 1)
  41. 	g.addEdge(4, 3, -3)
  42.  
  43. 	g.BellmanFord(0)
Success #stdin #stdout 0.02s 7000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Vertex Distance from Source
0		0
1		-1
2		2
3		-2
4		1
https://ideone.com/9EtDKY
language:
Python (cpython 2.7.16)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!