Bellman–Ford algorithm: Difference between revisions

Revision as of 04:05, 30 April 2005

Revision as of 14:24, 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.