Chapter 9
■
From a to B with edsger and Friends
198
for v in G[u]: # ... to v ...
G[u][v] += h[u] - h[v] # ... is adjusted (nonneg.)
D, P = {}, {} # D[u][v] and P[u][v]
for u in G: # From every u ...
D[u], P[u] = dijkstra(G, u) # ... find the shortest paths
for v in G: # For each destination ...
D[u][v] += h[v] - h[u] # ... readjust the distance
return D, P # These are two-dimensional
Note
■
there is no need to check whether the call to
bellman_ford
succeeded or whether it found a negative cycle
(in which case Johnson’s algorithm won’t work), because if there
is a
negative cycle in the graph,
bellman_ford
would
raise an exception.
Assuming the Q(
m lg
n) running time for Dijkstra’s algorithm, Johnson’s is simply a factor of
n slower, giving us
Q(
mn lg
n), which is faster than the cubic running time of Floyd-Warshall (discussed in a bit), for sparse graphs
(that is, for graphs with relatively few edges).
7
The transform used in Johnson’s algorithm closely related to the potential function of the A* algorithm
(see “Knowing Where You’re Going,” later in this chapter), and it is similar to the transform used in the min-cost
bipartite matching problem in Chapter 10. There, too, the goal is to ensure positive edge weights but in a slightly
different situation (edge weights changing from iteration to iteration).
Far-Fetched Subproblems
While Dijkstra’s algorithm is certainly based on the principles of dynamic programming,
the fact is partly obscured
by the need to discover the ordering of (or dependencies between) subproblems on the go. The algorithm I discuss
in this section, discovered independently by Roy, Floyd, and Warshall, is a prototypical example of DP. It is based on
a memoized recursive decomposition and is iterative in its common implementation. It is deceptively simple in form
but devilishly clever in design. It is, in some ways, based on the “in or out” principle discussed in Chapter 8, but the
resulting subproblems may,
at least at first glance, seem highly artificial and far-fetched.
In many DP problems, we might need to hunt a bit for a set of recursively related subproblems, but once we
find them, they often seem quite natural. Just think of the nodes in DAG shortest path, for example, or the prefix
pairs of the longest common subsequence problem. The latter illustrates a useful principle that can be extended to
less obvious structures, though: restricting which elements we’re allowed to work with. In the LCS problem, we’re
restricting
the lengths of prefixes, for example. In the knapsack problem, this is slightly more artificial: We invent
an ordering for the objects and restrict ourselves to the
k first ones. The subproblem is then parametrized by this
“permitted set” and a portion of the knapsack capacity.
In the all-pairs shortest path problem, we can use this form of restriction, along with the “in or out” principle, to
design
a set of nonobvious subproblems: We arbitrarily order the nodes and restrict how many—that is, the
k first—we’re allowed
to use as intermediate nodes in forming our paths. We have now parametrized our subproblems using three parameters:
The starting node
•
The ending node
•
The highest node number we’re
allowed to pass through
•
7
A common criterion for calling a graph
sparse is that
m is
O(
n), for example. In this case, though, Johnson’s will (asymptotically)
match Floyd-Warshall as long as
m is
O(
n
2
/lg
n), which allows for quite a lot of edges. On the other hand, Floyd-Warshall has very
low constant overhead.
Chapter 9
■
From a to B with edsger and Friends
199
Unless you had
some idea where we were going with this, adding the third item might seem totally
unproductive—how could it help us to restrict what we’re allowed to do? As I’m sure you can see,
the idea is to
partition the solution space, decomposing the problem into subproblems and then linking these into a subproblem
graph. The linking is achieved by creating a recursive dependency based on the “in or out” idea: node
k, in or out?
Let
d(
u,
v,
k) be the length of the shortest path that exists from node
u to node
v if you’re only allowed to use the
k
first nodes as intermediate nodes. We can decompose the problem as follows:
d(
u,
v,
k) = min(
d(
u,
v,
k−1),
d(
u,
k,
k−1) +
d(
k,
v,
k−1))
Like in the knapsack problem, we’re considering whether to include
k. If we don’t include it, we simply use the
existing solution, the
shortest path we could find without using
k, which is
d(
u,
v,
k−1). If we
do include it, we must use
the shortest path
to k (which is
d(
u,
k,
k−1)) as well as the shortest path
from k (which is
d(
k,
v,
k−1)). Note that in all
these three subproblems, we’re working with the
k−1 first nodes, because either we’re excluding
k or we’re
explicitly
using it as an endpoint and not an intermediate node. This guarantees us a size-ordering (that is, a topological
sorting) of the subproblems—no cycles.
You can see the resulting algorithm in Listing 9-5. (The implementation uses the memo decorator from Chapter 8.)
Note that I’m assuming the nodes are integers in the range 1...
n here. If you’re using other node objects, you could have
a list V containing the nodes in some arbitrary order and then use V[k-1] and V[k-2] instead of k and k-1 in the min
part. Also note that the returned D map has the form D[u,v] rather than D[u][v]. I’m also assuming that this is a full
weight matrix, so D[u][v] is inf if there is no edge from u to v. You could easily modify all of this, if you want.
Do'stlaringiz bilan baham: 
