stoimen's web log

Introduction

As we saw in the previous post, the algorithm of Dijkstra is very useful when it comes to find all the shortest paths in a weighted graph. However it has one major problem! Obviously it doesn’t work correctly when dealing with negative lengths of the edges.

We know that the algorithm works perfectly when it comes to positive edges, and that is absolutely normal because we try to optimize the inequality of the triangle.

Dijkstra's Approach — Since all the edges are positive we get the closest one!

Since Dijkstra’s algorithm make use of a priority queue normally we get first the shortest adjacent edge to the starting point. In our very basic example we’ll get first the edge with the length of 3 -> (S, A).

However when it comes to negative edges we can’t use any more priority queues, so we need a different, yet working solution.

Overview

The solution was published by Richard E. Bellman and Lester Ford, Jr. in 1958 in their publication “On a Routing Problem” and it is quite simple to explain and understand. Since we can prioritize the edges by its lengths the only thing we should do is to calculate all the paths. And to be sure that our algorithm will find all the paths correctly we repeat that N-1 times, where N is the number of vertices (|V| = N)!

Bellman-Ford Approach — The algorithm of Bellman-Ford doesn’t use priority queues! Indeed they are useless since the closest node in the queue can have shorter path passing through another node!

In this very basic image we can see how Bellman-Ford solves the problem. First we get the distances from S to A and B, which are respectively 3 and 4, but there is a shorter path to A, which passes through B and it is (S, B) + (B, A) = 4 – 2 = 2.

Code

Here’s the code on PHP. Note that this time we use an adjacency matrix and an additional array of distances. It’s important (for directed graphs, and our graph this time is directed) to put the positive value of A[j][i] if A[i][j] is negative. Note the case for A[1][2]!

define('INFINITY', 10000000);
 
$matrix = array(
    0 => array( 0,  3,  4),
    1 => array( 0,  0,  2),
    2 => array( 0,  -2, 0),
);
 
$len = count($matrix);
 
$dist = array();
 
function BellmanFord(&$matrix, &$dist, $start)
{
    global $len;
 
    foreach (array_keys($matrix) as $vertex) {
        $dist[$vertex] = INFINITY;
        if ($vertex == $start) {
            $dist[$vertex] = 0;
        }
    }
 
    for ($k = 0; $k < $len - 1; $k++) {
        for ($i = 0; $i < $len; $i++) {
            for ($j = 0; $j < $len; $j++) {
                if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
                    $dist[$i] = $dist[$j] + $matrix[$j][$i];
                }
            }
        }
    }
}
 
BellmanFord($matrix, $dist, 0);
 
// [0, 2, 4]
print_r($dist);

Complexity

The complexity is clearly O(n³) which follows directly from the code above.

Application

Actually this algorithm is very useful and it not only works with negative weights, but also can help us find negative cycles in the graph.

This is done with the simple check after the main loop.

    for ($i = 0; $i < $len; $i++) {
        for ($j = 0; $j < $len; $j++) {
            if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
                echo 'The graph contains a negative cycle!';
            }
        }
    }

And here’s the full code.

$matrix = array(
    0 => array( 0,  3,  4),
    1 => array( 0,  0,  2),
    2 => array( 0,  -2, 0),
);
 
$len = count($matrix);
 
$dist = array();
 
function BellmanFord(&$matrix, &$dist, $start)
{
    global $len;
 
    foreach (array_keys($matrix) as $vertex) {
        $dist[$vertex] = INFINITY;
        if ($vertex == $start) {
            $dist[$vertex] = 0;
        }
    }
 
    for ($k = 0; $k < $len - 1; $k++) {
        for ($i = 0; $i < $len; $i++) {
            for ($j = 0; $j < $len; $j++) {
                if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
                    $dist[$i] = $dist[$j] + $matrix[$j][$i];
                }
            }
        }
    }
 
    for ($i = 0; $i < $len; $i++) {
        for ($j = 0; $j < $len; $j++) {
            if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
                echo 'The graph contains a negative cycle!';
            }
        }
    }
}
 
BellmanFord($matrix, $dist, 0);
 
// [0, 2, 4]
print_r($dist);

4 thoughts on “Computer Algorithms: Bellman-Ford Shortest Path in a Graph”

backtick says:

November 5, 2012 at 11:57 am

Stoimen, which tools are you using to create these graphs? I’m trying to explain something using graphs, yet I haven’t found the necessary toolsets yet.
Stoimen says:

November 5, 2012 at 12:02 pm

Hi backtick,

I’m using Google docs (http://docs.google.com) it gives me the perfect set of functionality.
Jerry Antony Ajay says:

September 23, 2013 at 7:51 pm

According to the logic used, I guess the echo statement would be displayed twice for every single loop.
Shahriyar says:

May 2, 2016 at 10:12 pm

hi
when we move first node to other is there any restriction to move any node of graph..
can we choose any node to move?