from __future__ import annotations


def printDist(dist, V):
    print("Vertex Distance")
    distances = ("INF" if d == float("inf") else d for d in dist)
    print("\t".join(f"{i}\t{d}" for i, d in enumerate(distances)))


def BellmanFord(graph: list[dict[str, int]], V: int, E: int, src: int) -> int:
    """
    Returns shortest paths from a vertex src to all
    other vertices.
    """
    mdist = [float("inf") for i in range(V)]
    mdist[src] = 0.0

    for i in range(V - 1):
        for j in range(E):
            u = graph[j]["src"]
            v = graph[j]["dst"]
            w = graph[j]["weight"]

            if mdist[u] != float("inf") and mdist[u] + w < mdist[v]:
                mdist[v] = mdist[u] + w
    for j in range(E):
        u = graph[j]["src"]
        v = graph[j]["dst"]
        w = graph[j]["weight"]

        if mdist[u] != float("inf") and mdist[u] + w < mdist[v]:
            print("Negative cycle found. Solution not possible.")
            return

    printDist(mdist, V)
    return src


if __name__ == "__main__":
    V = int(input("Enter number of vertices: ").strip())
    E = int(input("Enter number of edges: ").strip())

    graph = [dict() for j in range(E)]

    for i in range(E):
        graph[i][i] = 0.0

    for i in range(E):
        print("\nEdge ", i + 1)
        src = int(input("Enter source:").strip())
        dst = int(input("Enter destination:").strip())
        weight = float(input("Enter weight:").strip())
        graph[i] = {"src": src, "dst": dst, "weight": weight}

    gsrc = int(input("\nEnter shortest path source:").strip())
    BellmanFord(graph, V, E, gsrc)

Problem Statement

Given a weighted directed graph G(V,E) and a source vertex s ∈ V, determine for each vertex v ∈ V the shortest path between s and v.

Approach

• Initialize the distance from the source to all vertices as infinite.
• Initialize the distance to itself as 0.
• Create an array dist[] of size |V| with all values as infinite except dist[s].
• Repeat the following |V| - 1 times. Where |V| is number of vertices.
• Create another loop to go through each edge (u, v) in E and do the following:
  1. dist[v] = minimum(dist[v], dist[u] + weight of edge).
• Lastly iterate through all edges on last time to make sure there are no negatively weighted cycles.

Time Complexity

O(VE)

Space Complexity

O(V^2)

Founder's Name

• Richard Bellman & Lester Ford, Jr.

Example

    # of vertices in graph = 5 [A, B, C, D, E]
    # of edges in graph = 8 

    edges  [A->B, A->C, B->C, B->D, B->E, D->C, D->B, E->D]
    weight [ -1,    4,    3,    2,    2,    5,    1,   -4 ]
    source [  A,    A,    B,    B,    B,    D,    D,    E ]



    // edge A->B 
    graph->edge[0].src = A 
    graph->edge[0].dest = B 
    graph->edge[0].weight = -1 
  
    // edge A->C 
    graph->edge[1].src = A 
    graph->edge[1].dest = C 
    graph->edge[1].weight = 4 
  
    // edge B->C 
    graph->edge[2].src = B 
    graph->edge[2].dest = C 
    graph->edge[2].weight = 3 
  
    // edge B->D 
    graph->edge[3].src = B 
    graph->edge[3].dest = D 
    graph->edge[3].weight = 2 
  
    // edge B->E 
    graph->edge[4].src = B 
    graph->edge[4].dest = E 
    graph->edge[4].weight = 2 
  
    // edge D->C 
    graph->edge[5].src = D
    graph->edge[5].dest = C 
    graph->edge[5].weight = 5 
  
    // edge D->B 
    graph->edge[6].src = D
    graph->edge[6].dest = B 
    graph->edge[6].weight = 1 
  
    // edge E->D 
    graph->edge[7].src = E
    graph->edge[7].dest = D 
    graph->edge[7].weight = -3

    for source = A

    Vertex   Distance from Source
	A                0				A->A
	B                -1				A->B
	C                2 				A->B->C = -1 + 3
	D                -2				A->B->E->D = -1 + 2 + -3
	E                1				A->B->E = -1 + 2

Code Implementation Links

• Java
• C++
• Python
• C

Video Explanation

A video explaining the Bellman-Ford Algorithm

Others

Sources Used:

• https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
• https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm