Bellman–Ford algorithm: Difference between revisions

Revision as of 03:15, 19 April 2005

Revision as of 20:55, 19 April 2005

Line 1:

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.