Bellman-Ford algorithm

Bellman-Ford algorithm is a graph search algorithm that can handle edges with negative weight of traversal (this means, better to pass through such an edge than not to pass). Edges with negative weights may arise after transforming many real world problems into graph search algorithm.

Bellman-Ford algorithm runs in O(V E) (number of nodes multiplied by the number of vertices) time. Hence it is less efficient than Dijkstra algorithm and only should be used when graph edges may have negative weights (Dijkstra algorithm cannot handle such graphs).

Algorithm

Unlike Dijkstra or A*, Bellman-Ford algorithm does not try to pick the optimal set of nodes to scan: it simply iterates over all edges that may come in any order. For each node, the algorithm may assign a "predecessor". At the end of the algorithm, the path from the target to the starting point can be traced by tracking which node is a predecessor in the path. Bellman-Ford algorithm iterates through edges, not through nodes (vertices) of the graph, and treats all edges as directional (hence path from A to B may have different cost than path from B to A). A pair of opposite edges must be added for every connection if the node relations in the task are not directional.

The algorithm itself is described as following^[1]:

Assign the zero tentative distance to the start node.
Assign the infinite tentative distance to all other nodes.

Repeat as many times as there are nodes in the graph
  For each edge |uv| in the graph,
    where u is the source and v is the destination
       if u.distance + |uv|.weight < v.distance
         then
           v.distance := u.distance + |uv|.weight
           v.predecessor := u 
         end if

Negative-weight cycles

A negative cycle is a cycle whose edges sum to a negative value. If graph contains such a cycle, then walks of arbitrarily low weight can be constructed (there is no shortest path). The extension, defined below, detects negative cycles and report their existence:

This extension is usually understood as part of the Bellman-Ford algorithm itself. After running the algorithms as described above, with all node distances still assigned, the following steps must be performed:

For each edge |uv| in the graph
   if u.distance + |uv|.weight < v.distance
     then
       report negative cycle - no solution

This means, if after one iteration of the loop some node still can be "relaxed" (finding a "better solution" for it), this can only mean that the task itself is not consistent (negative weight cycle present) and no proper solution exists.

References

1. ¹ Algorithm description at Kent state university page

Categories: Articles | Programming | Graph traversal algorithms