/* ............... START ............... */
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def bellman_ford(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
for i in range(self.V):
print("Vertex distance from source", i, "is:", dist[i])
# Example usage:
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)
g.bellman_ford(0)
/* ............... END ............... */
Vertex distance from source 0 is: 0
Vertex distance from source 1 is: -1
Vertex distance from source 2 is: 2
Vertex distance from source 3 is: -2
Vertex distance from source 4 is: 1
This output indicates the shortest distances from the source node 0 to all other nodes in the graph.
For example, the shortest distance from node 0 to node 2 is 2, and the shortest distance from
node 0 to node 3 is -2. Note that the algorithm correctly identifies that the graph does not
contain a negative-weight cycle.