Source code online books for professionals by professionals

Figure 9-1.  An example weighted graph

---

Chapter 9 
■
 From a to B with edsger and Friends
192
We then get a printout that starts something like the following:
 
(a,b)    D[b] = 2
(a,c)    D[c] = 1
(a,d)    D[d] = 3
(a,e)    D[e] = 9
(a,f)    D[f] = 4
(b,c)
(b,e)    D[e] = 5
(c,d)
(d,e)
(e,f)
(f,c)
(f,g)    D[g] = 6
(f,h)    D[h] = 6
(g,f)
(g,h)
(h,f)
(h,g) 
 
This is the first round of Bellman-Ford; as you can see, it has gone through all the edges once. The printout 
will continue for another round, but no assignments will be made to D, and so the function returns. There is some 
sloppiness here: The distance estimate D[e] is first set to 9, which is the distance along the path directly from a to e. 
Only after relaxing (a,b) and then (b,e) will we discover a better option, namely, the path a, b, e, of length 5. However, 
we have gotten rather lucky, in that we needed only one pass through the edges. Let’s see if we can make things more 
interesting and force the algorithm to do another round before settling down. See any ways of doing that? One way 
would be:
 
G[a][b] = 3
G[a][c] = 7
G[c][d] = -4
 
Now we have a good route to d via f, but we won’t find that in the first round:
 
(a,b)    D[b] = 3
(a,c)    D[c] = 7
(a,d)    D[d] = 3
(a,e)    D[e] = 9
(a,f)    D[f] = 4
(b,c)
(b,e)    D[e] = 6
(c,d)
(d,e)
(e,f)
(f,c)    D[c] = 6
(f,g)    D[g] = 6
(f,h)    D[h] = 6
(g,f)
(g,h)
(h,f)
(h,g)
 

---

Chapter 9 
■
 From a to B with edsger and Friends
193
We’ve gotten D[c] down to 6 in the first round, but when we get to that point, we have already relaxed (c,d),  
at a time when that edge couldn’t give us any improvement, because D[c] was 7 and D[d] was already 3. In the second 
round, however, you’d see
 
(c,d)    D[d] = 2
 
and in the third round, things would have settled down.
Before leaving the example, let’s try to introduce a negative cycle. Let’s use the original weights, with the following 
single modification:
 
G[g][h] = -9
 
Let’s get rid of the relaxations that don’t change D, and let’s add some round numbers to the printout. We then  
get the following:
 
# Round 1:
(a,b)    D[b] = 2
(a,c)    D[c] = 1
(a,d)    D[d] = 3
(a,e)    D[e] = 9
(a,f)    D[f] = 4
(b,e)    D[e] = 5
(f,g)    D[g] = 6
(f,h)    D[h] = 6
(g,h)    D[h] = -3
(h,g)    D[g] = 5
# Round 2:
(g,h)    D[h] = -4
(h,g)    D[g] = 4
# Round 3:
(g,h)    D[h] = -5
(h,g)    D[g] = 3
# Round 4:
(g,h)    D[h] = -6
(h,f)    D[f] = 3
(h,g)    D[g] = 2
 
...
 
# Round 8:
(g,h)    D[h] = -10
(h,f)    D[f] = -1
(h,g)    D[g] = -2
Traceback (most recent call last):
  ...
ValueError: negative cycle
 
I’ve removed some of the rounds, but I’m sure you can see the pattern: After round 3, the distance estimates of 
g, h, and f repeatedly decrease by one. The fact that they did so even in round 8, given that there are only 8 nodes, 
alerts us to the presence of a negative cycle. This doesn’t mean that there’s no solution—it just means that continued 
relaxation won’t find it for us, so we raise an exception.

---

Chapter 9 
■
 From a to B with edsger and Friends
194
Of course, a negative cycle is only a problem if we can actually reach it. Let’s try to eliminate the edge (f,g), for 
example by using del G[f][g]. Now at least f won’t participate in the cycle, but we still have g and h improving each 
others’ estimates beyond what’s correct. If, however, we also remove (f,h), our problem disappears! 
 
(a,b)    D[b] = 2
(a,c)    D[c] = 1
(a,d)    D[d] = 3
(a,e)    D[e] = 9
(a,f)    D[f] = 4
(b,e)    D[e] = 5
 
The graph is still connected, and the negative cycle is still there, but our traversal never reaches it. If this makes 
you uncomfortable, rest assured: The distances to g and h are correct. They are both infinite, as they should be. If, 
however, you try to call either bellman_ford(G, g) or bellman_ford(G, h), though, the cycle is once again 
reachable, so you’ll get a flurry of action, with several updates in each round, followed by the negative cycle exception 
at the end.