0.7 Graphs  (Page 14/21)

If a graph contains a cycle of total negative weight then arbitrarily low weights are achievable and so there's no solution; Bellman-Ford detects this case.

Bellman-Ford is in its basic structure very similar to Dijkstra's algorithm, but instead of greedily selecting the minimum-weight node not yet processed to relax, it simply relaxes all the edges, and does this |V| − 1 times, where |V| is the number of vertices in the graph. The repetitions allow minimum distances to accurately propagate throughout the graph, since, in the absence of negative cycles, the shortest path can only visit each node at most once. Unlike the greedy approach, which depends on certain structural assumptions derived from positive weights, this straightforward approach extends to the general case.

Bellman–Ford runs in O(V·E) time, where V and E are the number of vertices and edges respectively.

procedure BellmanFord(list vertices, list edges, vertex source)

// This implementation takes in a graph, represented as lists of vertices

// and edges, and modifies the vertices so that their distance and

// predecessor attributes store the shortest paths.

// Step 1: Initialize graph

for each vertex v in vertices:

if v is source then v.distance := 0

else v.distance := infinity

v.predecessor := null

// Step 2: relax edges repeatedly

for i from 1 to size(vertices)-1:

for each edge uv in edges:

u := uv.source

v := uv.destination // uv is the edge from u to v

if v.distance>u.distance + uv.weight:

v.distance := u.distance + uv.weight

v.predecessor := u

// Step 3: check for negative-weight cycles

for each edge uv in edges:

u := uv.source

v := uv.destination

if v.distance>u.distance + uv.weight:

error "Graph contains a negative-weight cycle"

Proof of correctness

The correctness of the algorithm can be shown by induction. The precise statement shown by induction is:

Lemma. After i repetitions of for cycle:

• If Distance(u) is not infinity, it is equal to the length of some path from s to u;
• If there is a path from s to u with at most i edges, then Distance(u) is at most the length of the shortest path from s to u with at most i edges.

Proof. For the base case of induction, consider i=0 and the moment before for cycle is executed for the first time. Then, for the source vertex, source.distance = 0, which is correct. For other vertices u, u.distance = infinity, which is also correct because there is no path from source to u with 0 edges.

For the inductive case, we first prove the first part. Consider a moment when a vertex's distance is updated by v.distance := u.distance + uv.weight. By inductive assumption, u.distance is the length of some path from source to u. Then u.distance + uv.weight is the length of the path from source to v that follows the path from source to u and then goes to v.

For the second part, consider the shortest path from source to u with at most i edges. Let v be the last vertex before u on this path. Then, the part of the path from source to v is the shortest path from source to v with at most i-1 edges. By inductive assumption, v.distance after i-1 cycles is at most the length of this path. Therefore, uv.weight + v.distance is at most the length of the path from s to u. In the ith cycle, u.distance gets compared with uv.weight + v.distance, and is set equal to it if uv.weight + v.distance was smaller. Therefore, after i cycles, u.distance is at most the length of the shortest path from source to u that uses at most i edges.