Bellman-Ford

class Graph:
 
    def __init__(self, vertices):
        self.V = vertices # Vertices in the graph
        self.graph = [] # Array of edges
 
# Adding edges
    def add_edge(self, s, d, w):
        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)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 4)
g.add_edge(1, 3, 3)
g.add_edge(2, 1, 6)
g.add_edge(3, 2, 2)
 
g.bellman_ford(0)