# Bellman-Ford

Here’s an example implementation of Bellman-Ford algorithm:

Python

class Graph:

def __init__(self, vertices):
self.V = vertices # Vertices in the graph
self.graph = [] # Array of edges

self.graph.append([s, d, w])

# Printing the solution
def print_solution(self, dist):
print("Vertex Distance from Source")
for i in range(self.V):
print("{0}\t\t{1}".format(i, dist[i]))

def bellman_ford(self, src):

# Filling the distance array and predecessor array
dist = [float("Inf")] * self.V
# Marking the source vertex
dist[src] = 0

# Relaxing edges |V| - 1 times
for _ in range(self.V - 1):
for s, d, w in self.graph:
if dist[s] != float("Inf") and dist[s] + w < dist[d]:
dist[d] = dist[s] + w

# Step 3: Detecting negative cycle in a graph
for s, d, w in self.graph:
if dist[s] != float("Inf") and dist[s] + w < dist[d]:
print("Graph contains negative weight cycle")
return

# No negative weight cycle found!
# Printing the distance and predecessor array

self.print_solution(dist)

g = Graph(5)