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