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.
Do'stlaringiz bilan baham: