Bellman-Ford Algorithm

Summarized notes on Introduction to Algorithms, Chapter 24

• input is weighted, directed graph
• edge weights may be negative
• returns a boolean to indicate if there is a negative weight cycle reachable from source
  • when negative weight cycle exists → no solution exists
  • otherwise → returns true and produces shortest paths and their weighs
• progressively relaxes edges until achieving actual $\delta (s,v)$
  → converges in at most $V-1$ passes if no negative weight cycles

Pseudo code implementation

Bellman-Ford(G, w, s)
    Initialize-single-source(G,s)
    for i = 1 to |G.V| - 1
        for each edge (u, v) in G.E
            Relax(u, v, w)
    for each edge (u, v) in G.E
        if v.d > u.d + w(u, v)
            return False
    return True

Complexity

Running Time
$O(VE)$	Bellman-Ford