Source code online books for professionals by professionals

Listing 9-1.  The Relaxation Operation
inf = float('inf')
def relax(W, u, v, D, P):
    d = D.get(u,inf) + W[u][v]                  # Possible shortcut estimate
    if d < D.get(v,inf):                        # Is it really a shortcut?
        D[v], P[v] = d, u                       # Update estimate and parent
        return True                             # There was a change!
 
The idea is that we look for an improvement to the currently known distance to v by trying to take a shortcut 
through u. If it turns out not to be a shortcut, fine. We just ignore it. If it is a shortcut, we register the new distance and 
remember where we came from (by setting P[v] to u). I’ve also added a small extra piece of functionality: the return 
value indicates whether any change actually took place; that’ll come in handy later (though you won’t need it for all 
your algorithms).
Here’s a look at how it works:
 
>>> D[u]
7
>>> D[v]
13
>>> W[u][v]
3
>>> relax(W, u, v, D, P)
True
>>> D[v]
10
>>> D[v] = 8
>>> relax(W, u, v, D, P)
>>> D[v]
8
 

---

Chapter 9 
■
 From a to B with edsger and Friends
189
As you can see, the first call to relax improves D[v] from 13 to 10 because I found a shortcut through u, which I 
had (presumably) already reached using a distance of 7 and which was just 3 away from v. Now I somehow discover 
that I can reach v by a path of length 8. I run relax again, but this time, no shortcut is found, so nothing happens.
As you can probably surmise, if I now set D[u] to 4 and ran the same relax again, D[v] would improve, this time 
to 7, propagating the improved estimate from u to v. This propagation is what relax is all about. If you randomly relax 
edges, any improvements to the distances (and their corresponding paths) will eventually propagate throughout the 
entire graph—so if you keep randomly relaxing forever, you know that you’ll have the right answer. Forever, however, 
is a very long time ...
This is where the relax game (briefly mentioned in Chapter 4) comes in: we want to achieve correctness with as 
few calls to relax as possible. Exactly how few we can get away with depends on the exact nature of our problem. For 
example, for DAGs, we can get away with one call per edge—which is clearly the best we can hope for. As you’ll see a 
bit later, we can actually get that low for more general graphs as well (although with a higher total running time and 
with no negative weights allowed). Before getting into that, however, let’s take a look at some important facts that can 
be useful along the way. In the following, assume that we start in node s and that we initialize D[s] to zero, while all 
other distance estimates are set to infinity. Let d(u,v) be the length of the shortest path from u to v.
•  d(s,v) <= d(s,u) + W[u,v]. This is an example of the triangle inequality.
•  d(s,v) <= D[v]. For v other than s, D[v] is initially infinite, and we reduce it only when we 
find actual shortcuts. We never “cheat,” so it remains an upper bound.
If there is no path to node 
•
v, then relaxing will never get D[v] below infinity. That’s because 
we’ll never find any shortcuts to improve D[v].
Assume a shortest path to 
•
v is formed by a path from s to u and an edge from u to v. Now, if 
D[u] is correct (that is, D[u] == d(s,u)) at any time before relaxing the edge from u to v, then 
D[v] is correct at all times afterward. The path defined by P[v] will also be correct.
Let 
•
[s, a, b, ... , z, v] be a shortest path from s to v. Assume all the edges (s,a), (a,b), 
... , (z,v) in the path have been relaxed in order. Then D[v] and P[v] will be correct. It doesn’t 
matter if other relax operations have been performed in between.
You should make sure you understand why these statements are true before proceeding. It will probably make 
the rest of the chapter quite a bit easier to follow.
Relaxing like Crazy
Relaxing at random is a bit crazy. Relaxing like crazy, though, might not be. Let’s say that you relax all the edges.  
You can do it in a random order, if you like—it doesn’t matter. Just make sure you get through all of them. Then you 
do it again—perhaps in another order—but you get through all the edges, once again. And again, and again. Until 
nothing changes.
Tip
 
■
  imagine each node continuously shouting out bids for supplying short paths to its out-neighbors, based on the 
shortest path it has gotten itself, so far. if any node gets a better offer than what it already has, it switches its path  
supplier and lowers its bids accordingly.
It doesn’t seem like such an unreasonable approach, at least for a first attempt. Two questions present 
themselves, though: How long will it take until nothing changes (if we ever get there), and can you be sure you’ve got 
the answer right when that happens?

---

Chapter 9 
■
 From a to B with edsger and Friends
190
Let’s consider a simple case first. Assume that all edge weights are identical and nonnegative. This means that the 
relax operation can find a shortcut only if it finds a path consisting of fewer edges. What, then, will have happened 
after we relax all edges once? At the very least, all neighbors of s will have the correct answer and will have s set as 
their parent in the shortest path tree. Depending on the order in which we relaxed the edges, the tree may have spread 
further, but we have no guarantees of that. How about if we relax all edges once more? Well, if nothing else, the tree 
will at least have extended one more level. In fact, the shortest path tree will—in the worst case—spread level by level, 
as if we were performing some horribly inefficient BFS. For a graph with n nodes, the largest number of edges in any 
path is n-1, so we know that n-1 is the largest number of iterations we need.
In general, though, we can’t assume this much about our edges (or if we could, we should rather just use BFS, 
which would do an excellent job). Because the edges can have different (possibly even negative) weights, the relax 
operations of later rounds may modify the predecessor pointers set in earlier rounds. For example, after one round, a 
neighbor v of s will have had P[v] set to s, but we cannot be sure that this is correct! Perhaps we’ll find a shorter path 
to v via some other nodes, and then P[v] will be overwritten. What can we know, then, after one round of relaxing all 
the edges?
Think back to the last one of the principles listed in the previous section: if we relax all the edges—in order—
along a shortest path from s to a node v, then our answer (consisting of D and P) will be correct for the path. In this 
case, specifically, we will have relaxed all edges along all shortest paths ... consisting of a single edge. We don’t know 
where these paths are, mind you, because we don’t (yet) know how many edges go into the various optimal paths. 
Still, although some of the P-edges linking s to its neighbors may very well not be final, we know that the ones that are 
correct must be there already.
And so the story goes. After k rounds of relaxing every edge in the graph, we know that all shortest paths of 
consisting of k edges have been completed. Following our earlier reasoning, for a graph with n nodes and m edges, 
it will require at most n-1 rounds until we’re done, giving us a running time of Q(nm). Of course, this need only be 
the worst-case running time, if we add a check: Has anything changed in the last round? If nothing changed, there’s 
no point in continuing. We might even be tempted to drop the whole n-1 count and only rely on this check. After all, 
we’ve just reasoned that we’ll never need more than n-1 rounds, so the check will eventually halt the algorithm. Right? 
No? No. There’s one wrinkle: negative cycles.
You see, negative cycles are the enemy of shortest path algorithms. If we have no negative cycles, the “no change” 
condition will work just fine, but throw in a negative cycle, and our estimates can keep improving forever. So ... as 
long as we allow negative edges (and why wouldn’t we?), we need the iteration count as a safeguard. The good news 
about this is that we can use the count to detect negative cycles: Instead of running n-1 rounds, we run n rounds and 
see whether anything changed in the last iteration. If we did get an improvement (which we shouldn’t have), we 
immediately conclude “A negative cycle did it!” and we declare our answers invalid and give up.
Note
 
■
  don’t get me wrong. it’s perfectly possible to find the shortest path even if there’s a negative cycle. the answer 
isn’t allowed to contain cycles anyway, so the negative cycles won’t affect the answer. it’s just that finding the shortest 
path while allowing negative cycles is an unsolved problem (see Chapter 11).
We have now arrived at the first proper algorithm of the chapter: Bellman-Ford (see Listing 9-2). It’s a single-source 
shortest path algorithm allowing arbitrary directed or undirected graphs. If the graph contains a negative cycle, the 
algorithm will report that fact and give up.