BELLMAN-FORD ALGORITHM

Domain	Definition
Math	An efficient algorithm to find the shortest paths from a single source vertex to all other vertices in a weighted, directed graph. Weights may be negative. The algorithm initializes the distance to the source vertex to 0 and all other vertices to . It then does V-1 passes (V is the number of vertices) over all edges relaxing, or updating, the distance to the destination of each edge. Finally it checks each edge again to detect negative weight cycles, in which case it returns false. The time complexity is O(VE), where E is the number of edges. (references)
Source: compiled by the editor from various references; see credits.

Specialty Definition: 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);
set Distance(s) = 0; Predecessor(s) = nil;
for each vertex v in G other than s, 
   set Distance(v) = infinity, Predecessor(v) = nil;
for i <- 1 to |V(G)| - 1 do   //|V(G)| Number of vertices in the graph
   for each edge (u,v) in G do
      if Distance(v) > Distance(u) + w(u,v) then
         set Distance(v) = Distance(u) + w(u,v), Predecessor(v) = u;  
for each edge (u,r) in G do
   if Distance(r) > Distance(u) + w(u,r);
      return false;
return true;