The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra’s algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.

Bellman-Ford

Complexity

Worst-case performance $O( V   E )$
Best-case performance $O( E )$    
Worst-case space complexity $O( V )$    

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

    function BELLMAN_FORD(src, dest) {
  const weights = new Array(G.length);
  let i;
  let j;

  for (i = 0; i < G.length; i++) {
    weights[i] = MAX_VALUE;
    
  }
  weights[src] = 0;

  console.log(`Initializing weights to: [${weights}]`);
  console.log('');

  // begin BF algorithm execution
  let k = G.length;
  while (k--) {
    
    console.log(`Iteration: ${G.length - k}`);
    console.log('------------------------------------------------------------------');

    for (i = 0; i < G.length; i++) {
      for (j = 0; j < G.length; j++) {
        if (G[i][j]) { // proceed to relax Edges only if a particular weight !== 0 (0 represents no edge)
          if (weights[j] > (weights[i] + G[i][j])) {
            weights[j] = weights[i] + G[i][j];
            
            console.log(`weights[${j}] = weights[${i}] + ${G[i][j]}`);
            
          }
          
        }
      }
    }

    console.log(`updated weights: [${weights.join(', ')}]`);
    console.log('');
    
  }

  // check for cycle
  console.log('checking for cycle');
  for (i = 0; i < G.length; i++) {
    for (j = 0; j < G.length; j++) {
      if (G[i][j]) {
        if (weights[j] > (weights[i] + G[i][j])) {
          
          console.log(`A cycle was detected: weights[${j}] > weights[${i}] + ${G[i][j]}`);
          
          return (MAX_VALUE);
        }
      }
    }
  }

  console.log(`No cycles detected. Final weights for the source ${src} are: [${weights}]`);

  return weights[dest];
}

const src = Randomize.Integer({ min: 0, max: G.length - 1 });
let dest;
let MAX_VALUE = 0x7fffffff;
let minWeight;

/*
 src = start node
 dest = start node (but will eventually at as the end node)
 */

do {
  dest = Randomize.Integer({ min: 0, max: G.length - 1 });
}
while (src === dest);

console.log(`finding the shortest path from ${src} to ${dest}`);

minWeight = BELLMAN_FORD(src, dest);

if (minWeight === MAX_VALUE) {
  console.log(`there is no path from ${src} to ${dest}`);
} else {
  console.log(`the shortest path from ${src} to ${dest} is ${minWeight}`);
}