Bellman–Ford algorithm: Difference between revisions

Revision as of 14:24, 1 May 2005

Revision as of 17:25, 1 May 2005

Line 1:

{{wikify}}

The '''Bellman-Ford algorithm''' computes single-source shortest paths in a [[weighted graph]] (where some of the [[edge (graph theory)|edge]] weights may be negative). [[Dijkstra's algorithm]] accomplishes the same problem with a lower running time, but requires edges to be non-negative. Thus, Bellman-Ford is usually used only when there are negative edge weights.

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

{{wikicode}}

Here is a sample algorithm of Bellman-Ford

''// Define datatypes for a graph''

BF(G,w,s) // G = Graph, w = weight, s=source

'''record''' vertex {

Determine Single Source(G,s);

''list'' edges

set Distance(s) = 0; Predecessor(s) = nil;

''real'' distance

for each vertex v in G other than s,

''vertex'' predecessor

set Distance(v) = infinity, Predecessor(v) = nil;

}

for i = 1 to |V(G)| - 1 do //|V(G)| Number of vertices in the graph

'''record''' edge {

for each edge (u,v) in G do

''node'' source

if Distance(v) > Distance(u) + w(u,v) then

''node'' dest

set Distance(v) = Distance(u) + w(u,v), Predecessor(v) = u;

''real'' weight

for each edge (u,r) in G do

}

if Distance(r) > Distance(u) + w(u,r);

return false; //This means that the graph contains a cycle of negative weight

'''function''' BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source)

//and the shortest paths are not well defined

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

return true; //Lengths of shortest paths are in Distance array

''// 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 G other than s, vertices:

'''if''' v '''is''' source '''then''' v.distance = 0

'''else''' v.distance = '''infinity'''

vertex.predecessor = '''null'''

''// Step 2: relax edges repeatedly

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

'''for each''' edge (u,r)uv in G doedges:

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 (u,v)uv in G dou.edges:

u := uv.source

v := uv.destination

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

'''error''' "Graph contains a negative-weight cycle"

== Proof of correctness ==

Line 30 ⟶ 52:

* 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 ''<code>i=0''</code> and the moment before ''for'' cycle is executed for the first time. Then, for the source vertex ''s'', ''Distance(s)<code>source.distance = 0''</code>, which is correct. For other vertices, ''Distance(u)'', <code>u.distance = '''infinity'''</code>, which is also correct because there is no path from ''ssource'' to ''u'' with 0 edges.

For the inductive case, we first prove the first part. Consider a moment when Distancea is updated by ''Distance(v) = Distance(u) + w(u,v)'' step. By inductive assumption, ''Distance(u)'' is the length of some path from 'vertex's'' to ''u''. Then, ''Distance(u) + w(u,v)''distance is theupdated lengthby of the path from ''s'' to ''v'' that first goes from ''s'' to ''u'' and then from ''u'' to ''v''.

<code>v.distance := u.distance + uv.weight</code>. By inductive assumption, <code>u.distance</code> is the length of some path from ''source'' to ''u''. Then <code>u.distance + uv.weight</code> 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 ''ssource'' 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 ''ssource'' to ''v'' is the shortest path between ''ssource'' to ''v'' with ''i-1'' edges. By inductive assumption, ''Distance(<code>v)''.distance</code> after ''i-1'' cycles is at most the length of this path. Therefore, ''Distance(v)<code>uv.weight +w(u, v)''.distance</code> is at most the length of the path from ''s'' to ''u''. In the ''i^th'' cycle, ''Distance(<code>u)''.distance</code> gets compared with ''Distance(v)<code>uv.weight +w(u, v)''.distance</code>, and is set equal to it, if ''Distance(v)<code>uv.weight +w(u, v)''.distance</code> was smaller. Therefore, after ''i'' cycles, ''Distance(<code>u)''.distance</code> is at most the length of the shortest path from ''ssource'' to ''u'' that uses at most ''i'' edges.

When ''i'' equals the number of vertices in the graph, each path will be the shortest path overall, unless there are negative-weight cycles. If a negative-weight cycle exists and is accessible from the source, then given any path, a shorter one exists, so there is no shortest path. Otherwise, the shortest path will not include any cycles (because going around a cycle would not make the path shorter), so each shortest path visits each vertex at most once, and its number of edges is less than the number of vertices in the graph. Therefore, each path stored in the graph by this point is the shortest path.

'''End of proof.'''

'''End of proof.'''

The correctness of the algorithm follows from the lemma together with the observation that shortest path between any two vertices must contain at most ''V(G)-1'' edges. (If a path contained more than ''V(G)-1'' edges, it must contain some vertex ''v'' twice. Then, it can be shortened by removing the part between the first occurrence of ''v'' and the second occurrence, as long as that part does not have a net negative weight. This means that it was not the shortest path.)

==Implementations==