BellmanFord.py

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

    # Add edges
    def add_edge(self, s, d, w):
        self.graph.append([s, d, w])

    # Print 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):
        # Step 1: fill the distance array and predecessor array
        dist = [float("Inf")] * self.V
        dist[src] = 0

        # Step 2: relax 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: detect negative cycle
        for s, d, w in self.graph:
            if dist[s] != float("Inf") and dist[s] + w < dist[d]:
                print("Graph contains negative weight cycle. Cannot find shortest path.")
                return

        # If no negative cycle, print shortest path
        self.print_solution(dist)