Bellman-Ford Algorithm

The Bellman-Ford algorithm solves single-source shortest path problem in a directed graph with negative and positive  weights. Its time complexity in worst case is equal to Ο(V*E) while Dijkstra’s algorithm has Ο((V+E)log V) time complexity. Thus, if you don’t have negative weights it’s preferable to use Dijkstra’s algorithm.

The only problem that can occur during execution of Bellman-Ford algorithm is  a negative weight cycle. It is a cycle with weights that sum to a negative number. In that case the algorithm relaxes its nodes indefinitely. Fortunately, Bellman-Ford algorithm can detect negative weight cycle.

nwcg

The algorithm was discovered independently by Richard Bellman and Lester Ford, Jr.

Implementation

The algorithm is based on relaxation technique that is also used in Dijkstra’s algorithm. The process of relaxation tests whether the distance going from some vertex through vertex can be improved. If so, the distance is replaced by smallest value.

Let’s have a look at the example. Suppose we have the directed graph below and want to apply Bellman-Ford algorithm to figure out the shortest path from node A to F.

BF_1

Step 1:

We need to store distance from starting vertex A to others. Initially, all vertices have unknown distance (we can use infinity for this) and only vertex A has distance 0 (because distance from A to A is equal to 0).

BF_2

Step 2:

Run relaxation for all edges in the graph. The edges can go in arbitrary order. Suppose, we relax edges in following order:

  1. A–>B
  2. E–>F
  3. A–>C
  4. B–>D
  5. C–>E
  6. D–>F
  7. B–>E

If so, the result will be following:

  1. A–>B = 0 + 10 = 10
  2. E–>F = 
  3. A–>C = 0 + 20 = 20
  4. B–>D = 10 + 20 = 30
  5. C–>E = 20 + 15 =  35
  6. D–>F = 10 + 20 + 30 = 60
  7. B–>E = 10 + 15 = 25 (Replace existing distance to vertex E, the previous distance was C->E = 35)

BF_3

Step 3:

In step 3, we again relaxing all vertices in the same order.

  1. A–>B = 10
  2. E–>F = 25 + 10 = 35 (Repace current value which is 60)
  3. A–>C = 20
  4. B–>D = 30
  5. C–>E = 35
  6. D–>F = 60
  7. B–>E = 25

BF_4

Voila, the shortest is found and basing on example above we can distinguish following steps of the algorithm:

Pre-conditions:

  1. Graph G = (V, E).
  2. Array D of size |V| for storing distances.
  3. Array P of size |V| for storing predecessors.
  4. Starting vertex s.

Algorithm:

  1. Set for all elements in D. I and many other use max int value to represent infinity.
  2. Set D[v] equal to 0.
  3. Repeate step 3.1 |V|-1 times.
    1. For each edge (u, v) ∈ G.E do step 3.1.1.
      1. If D[u] + weight of edge u->v is less than D[v] then set D[v] = D[u] + weight of edge u->v. And put P[v] = u.
  4. For each edge (u, v) G.E do step 4.1.
    1. If D[u] + weight of edge u->v is less than D[v] then throw exception. Because, graph contains a negative-weight cycle.
  5. End.

Note: step 3.1.1 is the relaxation process.

Here goes Java version of this algorithm on my GitHub repository: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/graph/BellmanFordAlgorithm.java

Leave a Reply