Bellman–Ford algorithm: Difference between revisions

Revision as of 14:54, 18 May 2003

Revision as of 05:22, 19 June 2003

Line 1:

'''Bellman-Ford algorithm''' computes single-source shortest paths in a weighted graph (where some of the 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.

Here is a sample algorithm of Bellman-Ford

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

Determine Single Source(G,s)

for i <- 1 to |V(G)| - 1 //|V(G)| Number of Vertices in the graph

do for each edge in G

do Relax edge

for each edge in G

do if Cost of Vertice r > Cost to Vertice r from Vertice u

return false

return true

== Proof of the Algorithm ==

*TODO

''See also: [[List of algorithms]]''