Skip to content

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

1
2
3
4
5
6
7
8
9
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