The tree which �lls the arms grew from the tiniest sprout;the tower of nine storeys rose from a (small) heap of earth;
the journey of a thousand li commenced with a single step.
— Lao-Tzu, Tao Te Ching, chapter 6� (6th century ���),translated by James Legge (�8��)And I would walk �ve hundred miles,
And I would walk �ve hundred more,
Just to be the man who walks a thousand miles
To fall down at your door.
— The Proclaimers, “I’m Gonna Be (��� Miles)”,Sunshine on Leith (����)Almost there. . . Almost there. . .
— Red Leader [Drewe Henley], Star Wars (����)�
All-Pairs Shortest Paths
�.�

Introduction

In the previous chapter, we discussed several algorithms to find the shortest
paths from a single source vertex s to every other vertex of the graph, byconstructing a shortest path tree rooted at s. The shortest path tree specifies
two pieces of information for each node v in the graph:• dist(v) is the length of the shortest path from s to v;• pred(v) is the second-to-last vertex in the shortest path from s to v.
In this chapter, we consider the more general all pairs shortest path problem,
which asks for the shortest path from every possible source to every possible
destination. For every pair of vertices u and v, we want to compute the following
information:• dist(u, v) is the length of the shortest path from u to v;• pred(u, v) is the second-to-last vertex on the shortest path from u to v.
����. A��-P���� S������� P����

These intuitive definitions exclude a few boundary cases, all of which wealready saw in the previous chapter.
• If there is no path from u to v, then there is no shortest path from u to v; inthis case, we define dist(u, v) = 1 and pred(u, v) = N.

• If there is a negative cycle between u and v, then there are paths from u
to v with arbitrarily negative length; in this case, we define dist(u, v) = 1
and pred(u, v) = N.
• Finally, if u does not lie on a negative cycle, then the shortest path from u toitself has no edges, and therefore doesn’t have a last edge; in this case, we
define dist(u, u) = 0 and pred(u, u) = N.
The desired output of the all-pairs shortest path problem is a pair of V ⇥ V arrays,
one storing all V 2 shortest-path distances, the other storing all V 2 predecessors.
In this chapter, I’ll focus almost exclusively on computing the distance array.
The predecessor array, from which we can compute the actual shortest paths,
can be computed with only minor modifications (hint, hint).

�.�

Lots of Single Sources

The most obvious solution to the all-pairs shortest path problem is to run asingle-source shortest path algorithm V times, once for each possible source
vertex. Specifically, to fill the one-dimensional subarray dist[s, ·], we invoke asingle-source algorithm starting at the source vertex s.
O

APSP(V, E, w):
for every vertex s
dist[s, ·] SSSP(V, E, w, s)

The running time of this algorithm obviously depends on which single-source
shortest path algorithm we use. Just as in the single-source setting, there are
four natural options, depending on the structure of the graph and its edge
weights:• If the edges of the graph are unweighted, breadth-first search gives us an
overall running time of O(V E) = O(V 3 ).
• If the graph is acyclic, scanning the vertices in topological order also gives
us an overall running time of O(V E) = O(V 3 ).
formally, walks
Back when road maps used to be printed on paper and had to be searched manually, it
was fairly common for them to include a triangular “distance table”. To find the distance from
Champaign to Columbus, for example, you would look in the row labeled “Champaign” and thecolumn labeled “Columbus”.

����.�. Reweighting• If all edge weights are non-negative, Dijkstra’s algorithm gives us a running
time to O(V E log V) = O(V 3 log V ).
• Finally, in the most general setting, the Bellman-Ford algorithm gives us an
overall running time of O(V 2 E) = O(V 4 ).

�.�Reweighting

Negative edges slow us down significantly; can we get rid of them? One simple
idea that occurs to many people is increasing the weights of all the edges
by the same amount so that all the weights become positive, so that we canuse Dijkstra’s algorithm instead of Bellman-Ford. Unfortunately, this simple
idea doesn’t work, intuitively because our two natural notions of “length” areincompatible—paths with more edges can have smaller total weight than paths
with fewer edges. If we increase all edge weights at the same rate, paths withmore edges get longer faster than paths with fewer edges; as a result, theshortest path between two vertices might change.
4

s

4

2

t
2

3

Figure �.�. Increasing all the edge weights by � changes the shortest path from s to t .

However, there is a more subtle method for reweighting edges that does
preserve shortest paths. This reweighting method is often attributed to Donald
Johnson, who described its application to shortest path algorithms in. But
in fact, Johnson attributed the method to apaper of Jack Edmonds andRichard Karp. The same method was also described by Nobuaki Tomizawa in, and in a slightly different form by Delbert Fulkerson in.
Suppose each vertex v has some associated price ⇡(v), which might bepositive, negative, or zero. We can define a new weight function w0 as follows:
w0 (u v) = ⇡(u) + w(u v)⇡(v)

To give some intuition, imagine that when we leave vertex u, we have to pay anexit tax of ⇡(u), and when we enter v, we get ⇡(v) as an entrance gift.
It’s not hard to show that shortest paths with the new weight function w0
are exactly the same as shortest paths with the original weight function w. In
Again, if we replace the binary heap in our implementation of Dijkstra’s algorithm withan unsorted array, the overall running time becomes O(V 3 ) (no matter how many edges thegraph has), and if we replace the binary heap with a Fibonacci heap, the running time drops toO(V (E + V log V )) = O(V E + V 2 log V ) = O(V 3 ).

����. A��-P���� S������� P����

fact, for any path u † v from one vertex u to another vertex v, we havew0 (u † v) = ⇡(u) + w(u † v)⇡(v).

We pay ⇡(u) in exit fees, plus the original weight of of the path, minus the ⇡(v)
entrance gift. At every intermediate vertex x on the path, we get ⇡(x) as an
entrance gift, but then immediately pay it back as an exit tax! Since all paths
from u to v change length by exactly the same amount, the shortest path from u
to v does not change. (Paths between different pairs of vertices could change
lengths by different amounts, so their order could change.)

�.�

Johnson’s Algorithm

Johnson’s all-pairs shortest path algorithm computes a cost ⇡(v) for each vertex,
so that the new weight of every edge is non-negative, and then computes shortest
paths with respect to the new weights using Dijkstra’s algorithm.
First, suppose the input graph has a vertex s that can reach all the othervertices. Johnson’s algorithm computes the shortest paths from s to the othervertices, using Bellman-Ford (which doesn’t care if the edge weights are negative), and then reweights the graph using the price function ⇡(v) = dist(s, v).
The new weight of every edge is
w0 (u v) = dist(s, u) + w(u v)

dist(s, v).

These new weights are non-negative because Bellman-Ford halted! Recall thatan edge u v is tense if dist(s, u) + w(u v) < dist(s, v), and that single-source
shortest path algorithms eliminate all tense edges. (If Bellman-Ford detects
a negative cycle, Johnson’s algorithm aborts, because shortest paths are notwell-defined.)If there is no suitable vertex s that can reach everything, then no matter
where we start Bellman-Ford, some of the resulting vertex prices will be infinite.
To avoid this issue, we always add a new vertex s to the graph, with zero-weightedges from s to the other vertices, but no edges going back into s. This addition
doesn’t change the shortest paths between any pair of original vertices, because
there are no paths into s.
Complete pseudocode for Johnson’s algorithm is shown in Figure . . The
running time of this algorithm is dominated by the calls to Dijkstra’s algorithm.
Specifically, we spend O(V E) time running B
Fonce, O(V E log V )time running D
V times, and O(V + E) time doing other bookkeeping.
Thus, the overall running time is O(V E log V) = O(V 3 log V ). Negative edges
don’t slow us down after all!
. . . assuming the default binary-heap implementation; see the previous footnote.

����.�. Dynamic ProgrammingJ

APSP(V, E, w) :hhAdd an arti�cial sourceii
add a new vertex sfor every vertex v
add a new edge s v
w(s v) 0
hhCompute vertex pricesii
dist[s, ·] B
F
(V, E, w, s)
if BFfound a negative cycle
fail gracefully
hhReweight the edgesii
for every edge u v 2 E
w0 (u v) dist[s, u] + w(u v) dist[s, v]
hhCompute reweighted shortest path distancesii
for every vertex u
dist0 [u, ·] D
(V, E, w0 , u)
hhCompute original shortest-path distancesii
for every vertex ufor every vertex v
dist[u, v] dist0 [u, v] dist[s, u] + dist[s, v]
Figure �.�. Johnson’s all-pairs shortest paths algorithm

�.�

Dynamic Programming

We can also solve the all-pairs shortest path problem directly using dynamic
programming, instead of invoking a single-source algorithm. For dense graphs,
where E = ⌦(V 2 ), the dynamic programming approach eventually yields analgorithm that is both simpler and (slightly) faster than Johnson’s algorithm.
For the rest of this chapter, I will assume that the input graph contains no
negative cycles.
As usual for dynamic programming algorithms, we first need a recurrence.
Just as in the single-source setting, the “obvious” recursive definition®
dist(u, v) =if u = v

0
min dist(u, x) + w(x v)xvotherwise

only works when the input graph is a dag; any directed cycles drive therecurrence into an infinite loop.
We can break this infinite loop by introducing as an additional parameter,
exactly as we did for Bellman-Ford; let dist(u, v, `) denote the length of theshortest path from u to v that uses at most ` edges. The shortest path between
any two vertices traverses at most V 1 edges, so the true shortest-path distanceis dist(u, v, V 1). Bellman’s single-source recurrence adapts to this setting����. A��-P���� S������� P����

immediately:
8
>
0
>
>
<
1
®
dist(u, v, `) =
>
>
>
:min

if ` = 0 and u = v
dist(u, v, `min (dist(u, x, `
x

v

1)

1) + w(x v))´

if ` = 0 and u 6= votherwise

Turning this recurrence into a dynamic programming algorithm is straightforward; the resulting algorithm runs in O(V 2 E) = O(V 4 ) time.
S

APSP(V, E, w):
for all vertices u
for all vertices v
if u = v
dist[u, v, 0]
else
dist[u, v, 0]
for `

0
1

1 to V 1
for all vertices u
for all vertices v 6= u
dist[u, v, `] dist[u, v, ` 1]
for all edges x v
if dist[u, v, `] > dist[u, x, ` 1] + w(x v)
dist[u, v, `] dist[u, x, ` 1] + w(x v)This algorithm was first sketched by Alfonso Shimbel in. Just like
Bellman’s formulation of Bellman-Ford, we don’t need the inner loop oververtices v or the iteration index `. The modified algorithm is shown below.
A P
BF(V, E, w):
for all vertices u
for all vertices v
if u = v
dist[u, v] 0
else
dist[u, v] 1for `1 to V 1
for all vertices u
for all edges x v
if dist[u, v] > dist[u, x] + w(x v)
dist[u, v] dist[u, x] + w(x v)

Shimbel assumed the input was a complete V ⇥ V matrix of distances, so his originalalgorithm actually runs in O(V 4 ) time no matter how many edges the graph has.

����.6. Divide and Conquer

Given how we derived it, it should come as no surprise that the resulting
algorithm is exactly the same as interleaving V different executions of BellmanFord, each with a different source vertex. In particular, for all vertices u and v,
after the `th iteration of the main for-loop, dist[u, v] is at most the length of theshortest path from u to v containing at most ` edges.

�.6

Divide and Conquer

But we can make a more significant improvement, suggested by Michael Fischerand Albert Meyer in. Bellman’s recurrence breaks the shortest path into aslightly shorter path and a single edge, by considering all possible predecessorsof the target vertex. Instead, let’s break the shortest paths into two shorter
shortest paths at the middle vertex. This idea gives us a different recurrence
for the same function dist(u, v, `). Here we need to stop at the base case ` = 1
instead of ` = 0, because a path with at most one edge has no “middle” vertex.
To simplify the recurrence slightly, let’s define w(v v) = 0 for every vertex v.
(
w(u v)
if i = 1
dist(u, v, `) =min dist(u, x, `/2) + dist(x, v, `/2) otherwisex

As stated, this recurrence only works when ` is a power of 2, since otherwise wemight try to find the shortest path with (at most) a fractional number of edges!
But that’s not really a problem; dist(u, v, `) is the true shortest-path distancefrom u to v for all ` V 1; in particular, we can use ` = 2dlg V e < 2V .
Once again, a dynamic programming solution is straightforward. Even before
we write down the algorithm, we can tell the running time is O(V 3 log V)—weneed to consider V possible values of u, v, and x, but only dlg V e possible valuesof `. In the following pseudocode for Fischer and Meyer’s algorithm, the arrayentry dist[u, v, i] stores the value of dist(u, v, 2i ).
F

M
APSP(V, E, w):
for all vertices u
for all vertices v
dist[u, v, 0]w(u v)
for i

1 to dlg V ehh` = 2i ii
for all vertices u
for all vertices v
dist[u, v, i] 1
for all vertices x
if dist[u, v, i] > dist[u, x, i 1] + dist[x, v, i 1]
dist[u, v, i] dist[u, x, i 1] + dist[x, v, i 1]

Unlike our earlier algorithms, F
M
APSP is not the same as V
invocations of any single-source shortest-path algorithm; in particular, the����. A��-P���� S������� P����

innermost loop does not simply relax tense edges. Nevertheless, we can still
remove the last dimension of the table, using dist[u, v] everywhere in place ofdist[u, v, i], just as we did in Bellman-Ford and our earlier dynamic programmingalgorithm; this reduces the space from O(V 3 ) to O(V 2 ). This more polishedalgorithm was described by Leyzorek et al. in, in the same paper where
they describe Dijkstra’s algorithm.
L

APSP(V, E, w):
for all vertices u
for all vertices v
dist[u, v]w(u v)for i

�.�

1 to dlg V ehh` = 2i ii
for all vertices u
for all vertices v
for all vertices x
if dist[u, v] > dist[u, x] + dist[x, v]
dist[u, v] dist[u, x] + dist[x, v]

Funny Matrix Multiplication

There is a very close connection (first observed by Shimbel, and later independently by Bellman) between computing shortest paths in a directed graph andcomputing powers of a square matrix. Compare the following algorithm forsquaring an n ⇥ n matrix A with the inner loop of FM
APSP. (I’veslightly modified the notation in the second algorithm to make the similarity
clearer.)
M

F

for i

S

(A):
1 to nfor j
1 to nA0 [i, j] 0for k
1 to nA0 [i, j] A0 [i, j] + A[i, k] · A[k, j]

M
I
L
(D):
for all vertices u
for all vertices v
D0 [u, v] 1
for all vertices x
D0 [u, v] min D0 [u, v], D[u, x] + D[x, v]

The only difference between these two algorithms is that the second algorithm
uses addition instead of multiplication, and minimization instead of addition. For
this reason, the shortest path inner loop is sometimes referred to as “min-plus”
or “distance” or “funny” matrix multiplication.
��6�.�. Funny Matrix Multiplication

Our slower algorithm S
APSP is the standard iterative algorithm forcomputing the (V 1)th “min-plus power” of the weight matrix w. The first
set of loops sets up the min-plus identity matrix, with 0s on the main diagonal
and 1 everywhere else, and each iteration of the second main loop computes
the next “min-plus power”. F
M
APSP replaces this iterative method
for computing powers with repeated squaring, exactly as we saw at the end ofChapter . Once again, we see the influence of ancient Egyptian!
There are faster divide-and-conquer algorithms for (standard) matrix multiplication, similar to Karatsuba’s divide-and-conquer algorithm for multiplying
integers. The first such algorithm, described by Volker Strassen in, reducesthe problem of multiplying two n ⇥ n matrices to seven instances of multiplying
two n/2 ⇥ n/2 matrices; Strassen’s algorithm runs in O(nlg 7 ) = O(n2.807355 ).
Strassen’s algorithm has been improved many times over the last fifty years; asof, the fastest matrix-multiplication algorithm known runs in O(n2.372864 )time. Unfortunately, all of these faster algorithms use subtraction, and there’s
no “funny” equivalent of subtraction. (What’s the inverse operation for min?)
So at least for general graphs, there’s no obvious way to speed up the inner loopof our dynamic programming algorithms.
But “not obvious” does not mean “impossible”! In fact, there are several
significantly faster algorithms for special cases of the all-pairs shortest paths
problem. One of the nicest is a simple randomized algorithm discovered inby Zvi Galil and Oded Margalit, and further simplified inby Raimund
Seidel, that computes all-pairs shortest path distances in unweighted, undirected
graphs in O(M (V ) log V ) expected time, where M (n) = O(n2.372864 ) is the timerequired to (seriously) multiply two n ⇥ n integer matrices. Galil, Margalit, andSeidel’s approach has since been extended to compute actual shortest paths,
deterministically, in directed graphs, with small integer edge weights, in strongly
subcubic time.
On the other hand, despite considerable progress in the small-integer-weight
setting, nobody knows how to compute all-pairs shortest paths for more generaledge weights in O(V 2.999999 ) time, for any number of 9s. Moreover, there issome evidence that such an algorithm is impossible! So maybe “not obvious”
does mean “impossible” after all.
Determining the minimum time required to multiply two arbitrary n ⇥ n matrices is along-standing open problem; many people believe there is an undiscovered algorithm that runsin O(n2+" ) time for any " > 0, or possibly even in O(n2 ) time.
Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs.
Journal of Computer and System Sciences, ( ):,. This is one of the few algorithms
papers where (in theconference version at least) the algorithm is completely describedand analyzed in the abstract of the paper. See also: Noga Alon, Zvi Galil, Oded Margalit*. On
the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences( ): – ,.

����. A��-P���� S������� P����

�.8(Kleene-Roy-)Floyd-Warshall(-Ingerman)

Our fast dynamic programming algorithm is still a factor of O(log V ) slower
in the worst case than the standard implementation of Johnson’s algorithm.
A different formulation of shortest paths that removes this logarithmic factor
was proposed twice in, first by Robert Floyd and later independently byPeter Ingerman, both slightly generalizing an algorithm of Stephen Warshall
published earlier in the same year. In fact, Warshall’s algorithm was previously
discovered by Bernard Roy in, and the underlying recursion pattern wasused by Stephen Kleene in.
Warshall’s (and Roy’s and Kleene’s) insight was to use a different thirdparameter in the dynamic programming recurrence. Instead of considering
paths with a limited number of edges, they considered paths that can passthrough only certain vertices. Here, “pass through” means “both enter andleave”; for example, the path w x y z starts at w, passes through x and y,and ends at z.
Number the vertices arbitrarily from 1 to V . For every pair of vertices uand v and every integer r, we define a path ⇡(u, v, r) as follows:⇡(u, v, r) is the shortest path (if any) from u to v that passes
through only vertices numbered at most r.
In particular, ⇡(u, v, V ) is the true shortest path from u to v. Kleene and Roy
and Warshall all observed that these paths have a simple recursive structure.
intermediate nodes ≤ r–1

uintermediate nodes ≤ rvuintermediate
nodes ≤ r–1— or —
rv
intermediate
nodes ≤ r–1

Figure �.�. Recursive structure of the restricted shortest path ⇡(u, v, r).

• The path ⇡(u, v, 0) can’t pass through any intermediate vertices, so it must
be the edge (if any) from u to v.
• For any integer r > 0, either ⇡(u, v, r) passes through vertex r or it doesn’t.
– If ⇡(u, v, r) passes through vertex r, it consists of a subpath from u to r,
followed by a subpath from r to v. Both of those subpaths pass throughonly vertices numbered at most r 1; moreover, those subpaths are as
short as possible with this restriction. So the two subpaths must be⇡(u, r, r 1) and ⇡(r, v, r 1).
Pronounced “clay knee”, not “clean” or “clean-ee” or “clay-nuh” or “dimaggio”. Specifically,
Kleene described an inductive proof that every finite automata has an equivalent regular expression; Kleene’s induction pattern is essentially identical to the Floyd-Warshall recurrence.

��8�.8. (Kleene-Roy-)Floyd-Warshall(-Ingerman)– On the other hand, if ⇡(u, v, r) does not pass through vertex r, then it
passes through only vertices numbered at most r 1, and it must be
the shortest path with this restriction. So in this case, we must have⇡(u, v, r) = ⇡(u, v, r 1).
Now let dist(u, v, r) denote the length of the path ⇡(u, v, r). The recursive
structure of ⇡(u, v, r) immediately implies the following recurrence:8>
if r = 0<w(u ®v)´
dist(u, v, r) =dist(u, v, r 1)>
otherwise:mindist(u, r, r 1) + dist(r, v, r 1)
Our goal is to compute dist(u, v, V ) for all vertices u and v. Once again,
this recurrence can be evaluated by a straightforward dynamic programmingalgorithm in O(V 3 ) time.
K

APSP(V, E, w):
for all vertices u
for all vertices v
dist[u, v, 0]for rw(u v)

1 to V
for all vertices u
for all vertices v
if dist[u, v, r 1] < dist[u, r, r 1] + dist[r, v, r 1]
dist[u, v, r] dist[u, v, r 1]
else
dist[u, v, r] dist[u, r, r 1] + dist[r, v, r 1]

Like all our previous dynamic programming algorithms for shortest paths, we
can simplify K
APSP by removing the third dimension of the memoizationtable. Also, because we chose the vertex numbering arbitrarily, there’s noreason to refer to it explicitly in the pseudocode. We finally arrive at Floyd’s
improvement of Warshall’s algorithm:
F

W(V, E, w):
for all vertices u
for all vertices v
dist[u, v]w(u v)
for all vertices r
for all vertices u
for all vertices v
if dist[u, v] > dist[u, r] + dist[r, v]
dist[u, v] dist[u, r] + dist[r, v]

It’s interesting to compare F
W
dynamic programming algorithm Lwith our earlier, slightly slower
APSP. Instead of O(log V ) passes
����. A��-P���� S������� P����

through all triples of vertices, FW
requires only a single pass, but
only because it uses a different nesting order for the three loops!

Exercises. (a) Describe a modification of L
APSP that returns an array of
predecessor pointers, in addition to the array of shortest path distances,
still in O(V 3 log V ) time.
(b) Describe a modification of F
W
that returns an array of
predecessor pointers, in addition to the array of shortest path distances,
still in O(V 3 ) time.
. All of the algorithms discussed in this chapter fail if the graph contains anegative cycle. Johnson’s algorithm detects the negative cycle in the initialization phase (via Bellman-Ford) and aborts; the dynamic programmingalgorithms just return incorrect results. However, all of these algorithms canbe modified to return correct shortest-path distances, even in the presenceof negative cycles. Specifically, for all vertices u and v:• If u cannot reach v, the algorithm should return dist[u, v] = 1.

• If u can reach a negative cycle that can reach v, the algorithm should
return dist[u, v] = 1.
• Otherwise, there is a shortest path from u to v, so the algorithm should
return its length.

(a) Describe how to modify Johnson’s algorithm to return the correct
shortest-path distances, even if the graph has negative cycles.
(b) Describe how to modify L
APSP to return the correct shortestpath distances, even if the graph has negative cycles.
(c) Describe how to modify Floyd-Warshall to return the correct shortest-path
distances, even if the graph has negative cycles.
. The algorithms described in this chapter can also be modified to return an
explicit description of some negative cycle in the input graph G, if one exists,
instead of only reporting whether or not G contains a negative cycle.
(a) Describe how to modify Johnson’s algorithm to return either the arrayof all shortest-path distances or a negative cycle.
(b) Describe how to modify L
APSP to return either the array of all
shortest-path distances or a negative cycle.
(c) Describe how to modify Floyd-Warshall to return either the array of all
shortest-path distances or a negative cycle.
���Exercises

In all cases, if the input graph contains more than one negative cycle, youralgorithms may choose one arbitrarily.
. Let G = (V, E) be a directed graph with weighted edges; edge weights canbe positive, negative, or zero, but there are no negative cycles.
(a) Describe an efficient algorithm that either finds a cycle of length zeroin G, or correctly reports that no such cycle exists.
(b) Describe an efficient algorithm that constructs a subgraph H of G withthe following properties:• Every vertex of G is a vertex of H.
• Every directed cycle in H has length 0.
• Every directed cycle of length 0 in G is also a cycle in H.
In particular, if there are no zero-cycles in G, then H has no edges.
. Let G = (V, E) be a directed graph with weighted edges; edge weights canbe positive, negative, or zero. Suppose the vertices of G are partitioned
into k disjoint subsets V1 , V2 , . . . , Vk ; that is, every vertex of G belongs toexactly one subset Vi . For each i and j, let (i, j) denote the minimum
shortest-path distance between vertices in Vi and vertices in Vj :(i, j) = min dist(vi , v j ) vi 2 Vi and v j 2 Vj .

Describe an algorithm to compute (i, j) for all i and j. For full credit, youralgorithm should run in O(V E + kV log V ) time.
. In this problem we will discover how you, yes you, can be employed byWall Street and cause a major economic collapse! The arbitrage businessis a money-making scheme that takes advantage of differences in currency
exchange. In particular, suppose US dollar buys
Japanese yen, yenbuys . euros, and euro buys . US dollars. Then, a trader starting with$ can convert their money from dollars to yen, then from yen to euros,
and finally from euros back to dollars, ending with $ . ! The cycle ofcurrencies $ ! ¥ ! e ! $ is called an arbitrage cycle. Of course, finding
and exploiting arbitrage cycles before the prices are corrected requires
extremely fast algorithms.
Suppose n different currencies are traded in your currency market. You
are given the matrix Exch[1 .. n, 1 .. n] of exchange rates between every pairof currencies; for each i and j, one unit of currency i can be traded for
Exch[i, j] units of currency j. (Do not assume that Exch[i, j] · Exch[ j, i] = 1.)(a) Describe an algorithm that returns an array MaxAmt[1 .. n], where
MaxAmt[i] is the maximum amount of currency i that you can obtain����. A��-P���� S������� P����

by trading, starting with one unit of currency 1, assuming there are no
arbitrage cycles.
(b) Describe an algorithm to determine whether the given matrix of currency
exchange rates creates an arbitrage cycle.
(c) Modify your algorithm from part (b) to actually return an arbitrage
cycle, if it exists.
. Morty needs to retrieve a stabilized plumbus from the Clackspire Labyrinth.
He must enter the labyrinth using Rick’s interdimensional portal gun, traverse
the Labyrinth to a plumbus, then take that plumbus through the Labyrinth
to a fleeb to be stabilized, and finally take the stabilized plumbus backto the original portal to return home. Plumbuses are stabilized by fleeb
juice, which any fleeb will release immediately after being removed from its
fleebhole. An unstabilized plumbus will explode if it is carried more thanflinks from its original storage unit. The Clackspire Labyrinth smells likefarts, so Morty wants to spend as little time there as possible.
Rick has given Morty a detailed map of the Clackspire Labyrinth, which
consist of a directed graph G = (V, E) with non-negative edge weights(indicating distance in flinks), along with two disjoint subsets P ⇢ V andF ⇢ V , indicating the plumbus storage units and fleebholes, respectively.
Morty needs to identify a start vertex s, a plumbus storage unit p 2 P, and a
fleebhole f 2 F , such that the shortest-path distance from p to f is at mostflinks long, and the length of the shortest walk s†p† f †s is as short as
possible.
Describe and analyze an algo(burp)rithm to so(burp)olve Morty’s problem. You can assume that it is in fact possible for Morty to succeed.
. Let G = (V, E) be a directed graph with weighted edges; edge weights could
be positive, negative, or zero.
(a) How would we delete an arbitrary vertex v from this graph, withoutchanging the shortest-path distance between any other pair of vertices?
Describe an algorithm that constructs a directed graph G 0 = (V \ {v}, E 0 )with weighted edges, such that the shortest-path distance between any
two vertices in G 0 is equal to the shortest-path distance between thesame two vertices in G, in O(V 2 ) time.
(b) Now suppose we have already computed all shortest-path distances in G 0 .
Describe an algorithm to compute the shortest-path distances in theoriginal graph G from v to every other vertex, and from every othervertex to v, all in O(V 2 ) time.
���Exercises(c) Combine parts (a) and (b) into another all-pairs shortest path algorithm
that runs in O(V 3 ) time. (The resulting algorithm is almost the same as
Floyd-Warshall!). Suppose A and B are boolean n ⇥ n matrices. The boolean or and-or productof A and B is the n ⇥ n matrix C defined as follows:_
C[i, j] :=A[i, k] ^ B[k, j]k(a) Reduce boolean matrix multiplication to min-plus matrix multiplication.
That is, given a subroutine M P
Mthat computes the minplus product of two n ⇥ n matrices in T (n) time, describe and analyze
an algorithm B
M
M
that multiplies two boolean
matrices in O(T (n)) time.
(b) Reduce boolean matrix multiplication to standard matrix multiplication.
That is, given a subroutine M
Mthat computes the standard
product of two n ⇥ n matrices in T (n) time, describe and analyze
an algorithm B
M
M
that multiplies two boolean
matrices in O(T (n)) time.
. The transitive closure of a directed graph G contains an edge u v if and only
if there is a directed path from u to v in G. For this problem, assume wecan multiply two n ⇥ n boolean matrices in O(n! ) time, for some constant2  ! < 3. (Problem (b) implies !  2.372864.)(a) Describe an algorithm to compute the transitive closure of an n-vertex
directed graph in O(n! log n) time.

(b) Now suppose G is a directed acyclic graph. Describe an algorithm tocompute the transitive closure of G in O(n! ) time. [Hint: Do what you
always do with dags, and then divide and conquer. Use the fact that
! 2.](c) Finally, describe an algorithm to compute the transitive closure of anarbitrary directed graph in O(n! ) time. [Hint: Do what you always do
to turn an arbitrary directed graph into a dag.](d) Now let’s reverse the previous reduction. Given a subroutine T
Cthat computes the transitive closure of an n-vertex directed
graph in O(n↵ ) time, for some constant 2  ↵ < 3, describe and analyze
an algorithm for boolean matrix multiplication that runs in O(n↵ ) time.
. Prove that the following recursive algorithm correctly computes all-pairs
shortest-path distances in O(n3 ) time. For simplicity, you may assume n
is a power of 2. As usual, the array D is passed by reference to the helper����. A��-P���� S������� P����

function R APSP. [Hint: This is a jumbled version of Floyd-Warshall, withsignificantly better cache behavior. ]
R

n
for i

|V |

1 to nfor j
1 to nif i = j
D[i, j]if i j 2 E
D[i, j]else
D[i, j]

R APSP(D, n, 1, 1, 1)
return D[1 .. n, 1 .. n]™

R

APSP(V, E, w):

0
w(i
1

j)

APSP(D, n, i, j, k):
if n = 1
D[i, j] min D[i, j], D[i, k] + D[ j, k]
else
m
n/2
R APSP(D, n/2, i,j,k)
R APSP(D, n/2, i,j,k + m)R APSP(D, n/2, i,
j + m, k)
R APSP(D, n/2, i,
j + m, k + m)
R APSP(D, n/2, i + m, j,k)
R APSP(D, n/2, i + m, j,
k + m)R APSP(D, n/2, i + m, j + m, k)
R APSP(D, n/2, i + m, j + m, k + m)

. Let G = (V, E) be an undirected, unweighted, connected, n-vertex graph,
represented by an adjacency matrix A[1 .. n, 1 .. n]. In this problem, we will
derive Seidel’s sub-cubic algorithm to compute the n⇥n matrix D[1 .. n, 1 .. n]of shortest-path distances in G using fast matrix multiplication. Assume that
we have a subroutine M
Mthat computes the standard product!
of two n ⇥ n matrices in O(n ) time, for some unknown constant ! 2.
(a) Let G 2 denote the graph with the same vertices as G, where two vertices
are connected by a edge if and only if they are connected by a path oflength at most 2 in G. Describe an algorithm to compute the adjacency
matrix of G 2 using a single call to M
M
and O(n2 ) additionaltime.

(b) Suppose we discover that G 2 is a complete graph. Describe an algorithm
to compute the matrix D of shortest path distances in G in O(n2 )additional time.
(c) Suppose we recursively compute the matrix D2 of shortest-path distancesin G 2 . Prove that the shortest-path distance in G from node i to node j
is either 2 · D2 [i, j] or 2 · D2 [i, j] 1.

(d) Now suppose G 2 is not a complete graph. Let X = D2 · A, and let deg(i)denote the degree of vertex i in the original graph G. Prove that the
shortest-path distance from node i to node j in G is 2 · D2 [i, j] if andonly if X [i, j] D2 [i, j] · deg(i).
Joon-Sang Park, Michael Penner, and Viktor K. Prasanna. Optimizing graph algorithms for
improved cache performance. IEEE Trans. Parallel and Distributed Systems ( ):– ,.
For a significant generalization to a wider class of dynamic programming problems, see Rezaul
Alam Chowdhury and Vijaya Ramachandran. Cache-oblivious dynamic programming. Proc. th
SODA
–
,
.

���

Exercises(e) Describe an algorithm to compute the matrix D of shortest-path distancesin G in O(n! log n) time.
. Gideon Yuval proposed the following reduction from min-plus matrix multiplication to standard matrix multiplication in. Suppose we are given
two integers n ⇥ n matrices A and B of integers, each of whose entries is
between 0 and M , and we want to compute their min-plus product matrix C,
defined by setting
C[i, k] = min(A[i, j] + B[ j, k])j

for all indices i and k. Define two new n ⇥ n matrices A0 and B 0 , whereA0 [i, j] = n M A[i, j]

and

B 0 [i, j] = n M B[i, j] .

Finally, letPC 0 be the (standard) product of A0 and B 0 , defined by setting
C 0 [i, k] = j A0 [i, j] · B 0 [ j, k].

(a) Describe an algorithm to construct A0 from A using only standard integer
arithmetic operations (+, , ⇥).

(b) Describe an algorithm to extract the min-plus product C from C 0 , using
only standard integer arithmetic operations (+, , ⇥).

(c) Suppose we can compute the standard product of two n ⇥ n integer matrices using O(n! ) arithmetic operations, for some constant 2  ! < 3.
How many arithmetic operations does Yuval’s algorithm need to computethe min-plus product C?

(d) Given a single n⇥n integer matrix A, how many arithmetic operations are
required to compute the nth “funny” power of A using Yuval’s algorithm?
(Recall that if A is the weighted adjacency matrix of a graph, then the
nth “funny” power of A is the matrix of shortest-path distances.)(e) Why doesn’t Yuval’s algorithm imply an all-pairs shortest path algorithm
that is faster than Floyd-Warshall for arbitrary edge weights? How are
we cheating?

In particular, do not use logarithms or division or the floor function bxc. Trust me—this is acan of worms you do not want to open.

���