Belman Ford Algorithm

The Bellman-Ford algorithm is used to find the shortest path from a starting vertex to all others in a directed graph with potentially negative edge weights. It works by repeatedly relaxing all edges, updating the shortest known distance if a shorter path is found. The algorithm starts by setting the distance to the source as 0 and others as infinity, then performs V - 1 iterations (where V is the number of vertices). This ensures that the shortest paths are found, as the longest possible path has at most V - 1 edges.
Bellman-Ford is especially effective on directed graphs and can handle negative edge weights, unlike Dijkstra's algorithm. A key feature is its ability to detect negative weight cycles. If, after V - 1 iterations, any edge can still be relaxed, the algorithm identifies a negative cycle, as the path length can keep decreasing indefinitely. If no further changes occur, the shortest paths are confirmed.

function BellmanFord(Graph, source):
    Initialize distances[source] = 0, all other distances = ∞
    for i = 1 to V-1:
        for each edge (u, v, weight) in Graph:
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
    
    for each edge (u, v, weight) in Graph:
        if distances[u] + weight < distances[v]:
            print("Graph contains a negative weight cycle")
            return
    
    print("Shortest distances:", distances)