|
Figure 9-2. Gradually uncovering the hidden DAG. Nodes are labeled with their final distances. Because weights are
positive, the backward edges (dashed) cannot influence the result and are therefore irrelevant
Predictably enough, we now hit the major gap in the solution: It’s totally circular. In uncovering the basic problem
structure (decomposing into subproblems or finding the hidden DAG), we’ve assumed that we’ve already solved the
problem. The reasoning has still been useful, though, because we now have something specific to look for. We want to
find the ordering—and we can find it with our trusty workhorse, induction!
Consider, again, Figure
9-2
. Assume that the highlighted node is the one we’re trying to identify in our inductive
step (meaning that the earlier ones have been identified and already have correct distance estimates). Just like in the
ordinary DAG shortest path problem, we’ll be relaxing all out-edges for each node, as soon as we’ve identified it and
determined its correct distance. That means that we’ve relaxed the edges out of all earlier nodes. We haven’t relaxed
the out-edges of later nodes, but as discussed, they can’t matter: the distance estimates of these later nodes are upper
bounds, and the back-edges have positive weights, so there’s no way they can contribute to a shortcut.
This means (by the earlier relaxation properties or the discussion of the DAG shortest path algorithm in
Chapter 8) that the next node must have a correct distance estimate. That is, the highlighted node in Figure
9-2
must
by now have received its correct distance estimate, because we’ve relaxed all edges out of the first three nodes. This
is very good news, and all that remains is to figure out which node it is. We still don’t really know what the ordering is,
remember? We’re figuring out the topological sorting as we go along, step by step.
There is only one node that could possibly be the next one, of course:
3
the one with the lowest distance estimate.
We know it’s next in the sorted order, and we know it has a correct estimate; because these estimates are upper
bounds, none of the later nodes could possibly have lower estimates. Cool, no? And now, by induction, we’ve solved
the problem. We just relax all out-edges of each node in distance order—which means always taking the one with the
lowest estimate next.
This structure is quite similar to that of Prim’s algorithm: traversal with a priority queue. Just as in Prim’s, we
know that nodes we haven’t discovered in our traversal will not have been relaxed, so we’re not (yet) interested in
them. And of the ones we have discovered (and relaxed), we always want the one with the lowest priority. In Prim’s
algorithm, the priority was the weight of the edge linking back to the traversal tree; in Dijkstra’s, the priority is the
distance estimate. Of course, the priority can change as we find shortcuts (just like new possible spanning tree edges
could reduce the priority in Prim’s), but just like in Listing 7-5, we can simply add the same node to our heap multiple
times (rather than trying to modify the priorities of the heap entries), without compromising correctness or running
time. The result can be found in Listing 9-3. Its running time is loglinear, or, more specifically, Q((m+n) lg n),
where m is the number of edges and n the number of nodes. The reasoning here is that you need a (logarithmic)
heap operation for (1) each node to be extracted from the queue and (2) each edge to be relaxed.
4
As long as you have
W(n) edges, which you will for graphs where you can reach Q(n) nodes from the start node, the running time can be
simplified to Q(m lg n).
3
Well, I’m assuming distinct distances here. If more than one node has the same distance, you could have more than one candidate.
Exercise 9-2 asks you to show what happens then.
4
You may notice that edges that go back into S are also relaxed here in order to keep the code simple. That has no effect on
correctness or asymptotic running time, but you’re free to rewrite the code to skip these nodes if you want.
Chapter 9
■
From a to B with edsger and Friends
196
Do'stlaringiz bilan baham: |
