Bellman-Ford algorithm

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