Source code online books for professionals by professionals

Figure 9-3.  An edge weight, or length, simulated by dummy nodes
It’s a bit like if you had set up a series of dominoes along each edge (the number of dominoes proportional to the 
weight), and you then tip the first domino in the start node. A node may be reached from multiple directions, but we 
can see which direction won, by looking at which dominoes lie below the others.
If we started with this approach, we could see Dijkstra’s algorithm as a way of gaining performance by 
“simulating” BFS, or the dominoes (or flowing water or a spreading sound wave, or ...), without bothering to deal  
with each dummy node (or domino) individually. Instead, we can think of our priority queue as a timeline, where 
we mark various times at which we will reach nodes by following various paths. We look down the length of a newly 
discovered edge and think, “When could the dominoes reach that node by following this edge?” We add the time the 
edge would take (the edge weight) to the current time (the distance to the current node) and place the result on the 
timeline (our heap). We do this for each node that is reached for the first time (we’re interested only in the shortest 
paths, after all), and we keep moving along the timeline to reach other nodes. As we reach the same node again, later 
in the timeline, we simply ignore it.
5
I’ve been clear about how Dijkstra’s algorithm is similar to the DAG shortest path algorithm. It is very much an 
application of dynamic programming, although the recursive decomposition wasn’t quite as obvious as in the DAG 
case. To get a solution, it also uses greed, in that it always moves to the node that currently has the lowest distance 
estimate. With the binary heap as a priority queue, there’s even a bit of divide and conquer going on in there; all in 
all, it’s a beautiful algorithm that uses much of what you’ve learned so far. It’s well worth spending some time on fully 
understanding it.
5
In a more conventional version of Dijkstra’s algorithm, where each node is just added once but its estimate is modified inside the 
heap, you could say this path is ignored if some better estimate comes along and overwrites it.

---

Chapter 9 
■
 From a to B with edsger and Friends
197
All Against All
In the next section, you’ll see a really cool algorithm for finding the shortest distances between all pairs of nodes. It’s 
a special-purpose algorithm that is effective even if the graph has a lot of edges. In this section, though, I’ll have a 
quick look at a way to combine the two previous algorithms—Bellman-Ford and Dijkstra’s algorithm—into one that 
really shines in sparse graphs (that is, ones with relatively few edges). This is Johnson’s algorithm, one that seems to 
be neglected in many courses and books on algorithm design, but which is really clever and which you get almost for 
free, given what you already know.
The motivation for Johnson’s algorithm is the following: When solving the all-pairs shortest paths problem for 
sparse graphs, simply using Dijkstra’s algorithm from every node is, in fact, a really good solution. That in itself doesn’t 
exactly motivate a new algorithm ... but the trouble is that Dijkstra’s algorithm doesn’t permit negative edges. For the 
single-source shortest path problem, there isn’t much we can do about that, except use Bellman-Ford instead. For the 
all-pairs problem, though, we can permit ourselves some initial preprocessing to make all the weights positive.
The idea is to add a new node s, with zero-weight edges to all existing nodes, and then to run Bellman-Ford from 
s. This will give us a distance—let’s call it h (v)—from s to each node v in our graph. We can then use h to adjust the 
weight of every edge: We define the new weight as follows: w ’(u,v) = w(u,v) + h(u) - h(v). This definition has two very 
useful properties. First, it guarantees us that every new weight w’(u,v) is nonnegative (this follows from the triangle 
inequality, as discussed earlier in this chapter; see also Exercise 9-5). Second, we’re not messing up our problem! That 
is, if we find the shortest paths with these new weights, those paths will also be shortest paths (with other lengths, 
though) with the original weights. Now, why is that?
This is explained by a sweet idea called telescoping sums: A sum like (a - b) + (b - c) + ... + (y - z) will collapse like 
a telescope, giving us a – z. The reason is that every other summand is included once with a plus before it and once 
with a minus, so they all sum to zero. The same thing happens to every path with the modified edges in Johnson’s 
algorithm. For any edge (u,v) in such a path, except for the first or last, the weight will be modified by adding h(u) and 
subtracting h (v). The next edge will have v as its first node and will add h(v), removing it from the sum. Similarly, the 
previous edge will have subtracted h (u), removing that.
The only two edges that are a bit different (in any path) are the first and the last. The first one isn’t a problem, 
because h (s) will be zero, and w (s,v) was set to zero for all nodes v. But what about the last one? Not a problem. Yes, 
we’ll end up with h (v) subtracted for the last node v, but that will be true of all paths ending at that node—the shortest 
path will still be shortest.
The transformation doesn’t discard any information either, so once we’ve found the shortest paths using 
Dijkstra’s algorithm, we can inversely transform all the path lengths. Using a similar telescoping argument, we can see 
that we can get the real length of the shortest path from u to v by adding h(v) and subtracting h(u) from our answer 
based on the transformed weights. This gives us the algorithm implemented in Listing 9-4.
6