Source code online books for professionals by professionals

Pillow Talk. Maybe I should’ve tried Wexler? (
http://xkcd.com/69
)
Finding the Hidden DAG
The Bellman-Ford algorithm is great. In many ways it’s the easiest to understand of the algorithms in this chapter: 
Just relax all the edges until we know everything must be correct. For arbitrary graphs, it’s a good algorithm, but if we 
can make some assumptions, we can (as is usually the case) do better. As you’ll recall, the single-source shortest path 
problem can be solved in linear time for DAGs. In this section, I’ll deal with a different constraint, though. We can still 
have cycles, but no negative edge weights. (In fact, this is a situation that occurs in a great deal of practical applications, 
such as those discussed in the introduction.) Not only does this mean that we can forget about the negative cycle 
blues; it’ll let us draw certain conclusions about when various distances are correct, leading to a substantial 
improvement in running time.
The algorithm I’m building up to here, designed by algorithm super-guru Edsger W. Dijkstra in 1959, can be 
explained in several ways, and understanding why it’s correct can be a bit tricky. I think it can be useful to see it as a 
close relative to the DAG shortest path algorithm, with the important difference that it has to uncover a hidden DAG. 
You see, even though the graph we’re working with can have any structure it wants, we can think of some of  
the edges as irrelevant. To get things started, we can imagine that we already know the distances from the start node  
to each of the others. We don’t, of course, but this imaginary situation can help our reasoning. Imagine ordering  
the nodes, left to right, based on their distance. What happens? For the general case—not much. However,  
we’re assuming that we have no negative edge weights, and that makes all the difference.
Because all edges are positive, the only nodes that can contribute to a node’s solution will lie to its left in our 
hypothetical ordering. It will be impossible to locate a node to the right that will help us find a shortcut because 
this node is further away and could give us a shortcut only if it had a negative back edge. The positive back edges are 
completely useless to us and aren’t part of the problem structure. What remains, then, is a DAG, and the topological 

---

Chapter 9 
■
 From a to B with edsger and Friends
195
ordering we’d like to use is exactly the hypothetical ordering we started with: nodes sorted by their actual distance. 
See Figure 
9-2
 for an illustration of this structure. (I’ll get back to the question marks in a minute.)