Source code online books for professionals by professionals

Chapter 9
From A to B with Edsger and Friends
The shortest distance between two points is under construction.
— Noelie Altito
It’s time to return to the second problem from the introduction:
1
 How do you find the shortest route from Kashgar to 
Ningbo? If you pose this problem to any map software, you’d probably get the answer in less than a second. By now, 
this probably seems less mysterious than it (maybe) did initially, and you even have tools that could help you write 
such a program. You know that BFS would find the shortest path if all stretches of road had the same length, and you 
could use the DAG shortest path algorithm as long as you didn’t have any cycles in your graph. Sadly, the road map 
of China contains both cycles and roads of unequal length. Luckily, however, this chapter will give you the algorithms 
you need to solve this problem efficiently!
And lest you think all this chapter is good for is writing map software, consider in what other contexts the 
abstraction of shortest paths might be useful. For example, you could use it in any situation where you’d like to 
efficiently navigate a network, which would include all kinds of routing of packets over the Internet. In fact, the ’net 
is stuffed with such routing algorithms, all working behind the scenes. But such algorithms are also used in less 
obviously graph-like navigation, such as having characters move about intelligently in computer games. Or perhaps 
you’re trying to find the lowest number of moves to solve some form of puzzle? That would be equivalent to finding 
the shortest path in its state space—the abstract graph representing the puzzle states (nodes) and moves (edges). 
Or are you looking for ways to make money by exploiting discrepancies in currency exchange rates? One of the 
algorithms in this chapter will at least take you part of the way (see Exercise 9-1).
Finding shortest paths is also an important subroutine in other algorithms that need not be very graph-like. For 
example, one common algorithm for finding the best possible match between n people and n jobs
2
 needs to solve this 
problem repeatedly. At one time, I worked on a program that tried to repair XML files, inserting start and end tags as 
needed to satisfy some simple XML schema (with rules such as “list items need to be wrapped in list tags”). It turned 
out that this could be solved easily by using one of the algorithms in this chapter. There are applications in operations 
research, integrated circuit manufacture, robotics—you name it. It’s definitely a problem you want to learn about. 
Luckily, although some of the algorithm can be a bit challenging, you’ve already worked through many, if not most, of 
their challenging bits in the previous chapters.
The shortest path problem comes in several varieties. For example, you can find shortest paths (just like any 
other kinds of paths) in both directed and undirected graphs. The most important distinctions, though, stem from 
your starting points and destinations. Do you want to find the shortest from one node to all others (single source)? 
From one node to another (single pair, one to one, point to point)? From all nodes to one (single destination)? From 
all nodes to all others (all pairs)? Two of these—single source and all pairs—are perhaps the most important. Although 
we have some tricks for the single pair problem (see “Meeting in the Middle” and “Knowing Where You’re Going,” later), 
1
Don’t worry, I’ll revisit the “Sweden tour” problem in Chapter 11.
2
The min-cost bipartite matching problem, discussed in Chapter 10.

---

Chapter 9 
■
 From a to B with edsger and Friends
188
there are no guarantees that will let us solve that problem any faster than the general single-source problem. The 
single destination problem is, of course, equivalent to the single-source version (just flip the edges for the directed case). 
The all-pairs problem can be tackled by using each node as a single source (and we’ll look into that), but there are 
special-purpose algorithms for that problem as well.
Propagating Knowledge
In Chapter 4, I introduced the idea of relaxation and gradual improvement. In Chapter 8, you saw the idea applied 
to finding shortest paths in DAGs. In fact, the iterative shortest path algorithm for DAGs (Listing 8-4) is not just a 
prototypical example of dynamic programming; it also illustrates the fundamental structure of the algorithms in this 
chapter: we use relaxation over the edges of a graph to propagate knowledge about shortest paths.
Let’s review what this looks like. I’ll use a dict of dicts representation of the graph and use a dict D to maintain 
distance estimates (upper bounds), like in Chapter 8. In addition, I’ll add a predecessor dict, P, as for many of the 
traversal algorithms in Chapter 5. These predecessor pointers will form a so-called shortest path tree and will allow us 
to reconstruct the actual paths that correspond to the distances in D. Relaxation can then be factored out in the relax 
function in Listing 9-1. Note that I’m treating nonexistent entries in D as if they were infinite. (I could also just initialize 
them all to be infinite in the main algorithms, of course.)