bellman ford algorithm is used to find the single source shortest path in a weighted directed graph example find the shortest path from node a to f advantages of this algorithm over djikstra s 1 bellman ford also works for negative weight edges 2 also finds negative weight cycles in a graph disvantage 1 slower than dijsktra s idea https www youtube comwatch vmoed3gtk0t 0 shortest path can be found as if distancev distanceu weightu v then the right side is the shorter path 1 mark parent and the new weight each time this is run 2 do this v1 times in the first iteration the algorithm will find the shortest path between the source and source s neighbours 3 in the second between source and source s neighbours neighbours and so on v 1 times 4 do this again if in this vth iteration the weights of path decrease then there is a negative cycle in the graph time complexity ov e space complexity ov now for the vth iteration check for the negative cycle printing the shortest path from source to destination doing v 1 times to find shortest distance now for the vth iteration check for the negative cycle printing the shortest path from source to destination
from collections import defaultdict

class Edge:

    def __init__(self, source, dest, weight):
        self.source = source
        self.dest = dest
        self.weight = weight


class Graph:


    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.vertices = vertices
        self.edges = {}


    def add_edge(self, u, v, weight):
        self.graph[u].append(v)
        self.edges[(u, v)] = Edge(u, v, weight)


    def bellman_ford(self, source, destination):
        parent = [-1] * self.vertices
        distance = [float("inf")] * self.vertices

        parent[source] = source
        distance[source] = source

        for i in range(self.vertices - 1):  

            for (u, v) in self.edges:
                wt = self.edges[(u, v)].weight

                if distance[v] > distance[u] + wt:
                    distance[v] = distance[u] + wt
                    parent[v] = u

        

        negative_cycle_present = False
        
        for (u, v) in self.edges:
            wt = self.edges[(u, v)].weight
            if distance[v] > distance[u] + wt:
                negative_cycle_present = True
                break

        if negative_cycle_present:
            print('Contains negative cycle')
        else:
            print('No negative cycle')

        

        while True:
            print(f'{destination}', end=' ')
            destination = parent[destination]

            if destination == source:
                break         


g = Graph(5)

g.add_edge(0, 1, 4)
g.add_edge(0, 2, 5)
g.add_edge(0, 3, 8)
g.add_edge(1, 2, -3)
g.add_edge(2, 4, 4)
g.add_edge(3, 4, 2)
g.add_edge(4, 3, 1)

g.bellman_ford(0, 3)