All-Pairs Shortest Paths

Prev: Shortest Paths Next: Maximum Flows and Minimum Cuts

Exercises

1.

(a) Describe a modification of LeyzorekAPSP that returns an array of predecessor pointers, in addition to the array of shortest path distances, still in $O(V3logV)$ time. (b) Describe a modification of FloydWarshall that returns an array of predecessor pointers, in addition to the array of shortest path distances, still in $O(V^3)$ time.

2.

All of the algorithms discussed in this chapter fail if the graph contains a negative cycle. Johnson’s algorithm detects the negative cycle in the initialization phase (via Bellman-Ford) and aborts; the dynamic programming algorithms just return incorrect results. However, all of these algorithms can be modified to return correct shortest-path distances, even in the presence of negative cycles. Specifically, for all vertices u and v: • If u cannot reach v, the algorithm should return $dist[u,v]$ = $\infty$. • If u can reach a negative cycle that can reach v, the algorithm should return $dist[u,v]$ = $-\infty$. • 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 LeyzorekAPSP 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.

3.

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 array of all shortest-path distances or a negative cycle. (b) Describe how to modify LeyzorekAPSP 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.

In all cases, if the input graph contains more than one negative cycle, your algorithms may choose one arbitrarily.

4.

Let $G=(V,E)$ be a directed graph with weighted edges; edge weights can be positive, negative, or zero, but there are no negative cycles. (a) Describe an efficient algorithm that either finds a cycle of length zero in G, or correctly reports that no such cycle exists. (b) Describe an efficient algorithm that constructs a subgraph H of G with the 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.

5.

Let $G=(V,E)$ be a directed graph with weighted edges; edge weights can be positive, negative, or zero. Suppose the vertices of G are partitioned into $k$ disjoint subsets $V_1,V_2,\dots ,V_k$; that is, every vertex of G belongs to exactly one subset $V_i$. For each $i$ and $j$, let $\delta (i,j)$ denote the minimum shortest-path distance between vertices in $V_i$ and vertices in $V_j$:

$$\delta (i,j)=\min \{\mathrm{dist}(v_i,v_j)\mid v_i\in V_i,v_j\in V_j\}.$$

Describe an algorithm to compute $\delta (i,j)$ for all $i$ and $j$. For full credit, your algorithm should run in $O(VE+kV\log V)$ time.

6.

In this problem we will discover how you, yes you, can be employed by Wall Street and cause a major economic collapse! The arbitrage business is a money-making scheme that takes advantage of differences in currency exchange. In particular, suppose 1 US dollar buys 120 Japanese yen, 1 yen buys 0.01 euros, and 1 euro buys 1.2 US dollars. Then, a trader starting with $1canconverttheirmoneyfromdollarstoyen,thenfromyentoeuros,andfinallyfromeurosbacktodollars,endingwith$1.44! The cycle of currencies $\to \yen \to €\to$ 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\dots n,1\dots n]$ of exchange rates between every pair of 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\dots n]$, where $MaxAmt[i]$ is the maximum amount of currency i that you can obtain 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.

7.

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 back to 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 than $137$ flinks from its original storage unit. The Clackspire Labyrinth smells like farts, so Morty wants to spend as little time there as possible. Rick has given Morty a detailed map of the Clackspire Labyrinth, which consists of a directed graph $G=(V,E)$ with non-negative edge weights (indicating distance in flinks), along with two disjoint subsets $P\subseteq V$ and $F\subseteq V$, indicating the plumbus storage units and fleebholes, respectively. Morty needs to identify a start vertex $s$, a plumbus storage unit $p\in P$, and a fleebhole $f\in F$, such that the shortest-path distance from $p$ to $f$ is at most $137$ flinks long, and the length of the shortest walk $s\to p\to f\to s$ is as short as possible. Describe and analyze an algorithm to solve Morty’s problem. You can assume that it is in fact possible for Morty to succeed.

8.

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, without changing the shortest-path distance between any other pair of vertices? Describe an algorithm that constructs a directed graph $G^{\prime }$ = (V \ {v}, $E^{\prime }$) with weighted edges, such that the shortest-path distance between any two vertices in $G^{\prime }$ is equal to the shortest-path distance between the same two vertices in G, in $O(V^2)$ time. (b) Now suppose we have already computed all shortest-path distances in $G^{\prime }$. Describe an algorithm to compute the shortest-path distances in the original graph G from v to every other vertex, and from every other vertex to v, all in $O(V^2)$ time. (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!)

9.

Suppose $A$ and $B$ are boolean $n\times n$ matrices. The boolean or-and product of $A$ and $B$ is the $n\times n$ matrix $C$ defined by

$$C[i,j]:=\underset{k}{\bigvee }(A[i,k]\wedge B[k,j]).$$

(a) Reduce boolean matrix multiplication to min-plus matrix multiplication. That is, given a subroutine MinPlusMultiply that computes the min-plus product of two $n\times n$ matrices in time $T(n)$, describe and analyze an algorithm BooleanMatrixMultiply that multiplies two boolean matrices in $O(T(n))$ time. (b) Reduce boolean matrix multiplication to standard matrix multiplication. That is, given a subroutine MatrixMultiply that computes the standard product of two $n\times n$ matrices in time $T(n)$, describe and analyze an algorithm BooleanMatrixMultiply that multiplies two boolean matrices in $O(T(n))$ time.

10.

The transitive closure of a directed graph G contains an edge $u\to v$ if and only if there is a directed path from u to v in G. For this problem, assume we can multiply two n × n boolean matrices in $O(n^{\omega })$ time, for some constant 2 \le ω < 3. (Problem 9(b) implies ω \le 2.372864.) (a) Describe an algorithm to compute the transitive closure of an n-vertex directed graph in $O(n^{\omega }logn)$ time. (b) Now suppose G is a directed acyclic graph. Describe an algorithm to compute the transitive closure of G in $O(n^{\omega })$ time. [Hint: Do what you always do with dags, and then divide and conquer. Use the fact that ω \ge 2.] (c) Finally, describe an algorithm to compute the transitive closure of an arbitrary directed graph in $O(n^{\omega })$ 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 TransitiveClosure that computes the transitive closure of an n-vertex directed graph in $O(n^{\alpha })$ time, for some constant 2 \le α < 3, describe and analyze an algorithm for boolean matrix multiplication that runs in $O(n^{\alpha })$ time.

11.

Prove that the following recursive algorithm correctly computes all-pairs shortest-path distances in $O(n^3)$ time. For simplicity, you may assume n is a power of 2. As usual, the array D is passed by reference to the helper function RecAPSP. [Hint: This is a jumbled version of Floyd-Warshall, with significantly better cache behavior.]

RecursiveAPSP(V, E, w):
n ← |V |
for i ← 1 to n
for j ← 1 to n
if i = j
D[i, j] ← 0
if i  ->  j ∈ E
D[i, j] ← w(i  ->  j)
else
D[i, j] ← ∞
RecAPSP(D, n, 1, 1, 1)
return D[1 .. n, 1 .. n]

RecAPSP(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
RecAPSP(D, n/2, i,
j,
k
)
RecAPSP(D, n/2, i,
j,
k + m)
RecAPSP(D, n/2, i,
j + m, k
)
RecAPSP(D, n/2, i,
j + m, k + m)
RecAPSP(D, n/2, i + m, j,
k
)
RecAPSP(D, n/2, i + m, j,
k + m)
RecAPSP(D, n/2, i + m, j + m, k)
RecAPSP(D, n/2, i + m, j + m, k + m)

12.

Let $G=(V,E)$ be an undirected, unweighted, connected, n-vertex graph, represented by an adjacency matrix $A[1\dots n,1\dots n]$. In this problem, we will derive Seidel’s sub-cubic algorithm to compute the n×n matrix $D[1\dots n,1\dots n]$ of shortest-path distances in G using fast matrix multiplication. Assume that we have a subroutine MatrixMultiply that computes the standard product of two n × n matrices in $O(n^{\omega })$ time, for some unknown constant ω \ge 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 of length at most 2 in G. Describe an algorithm to compute the adjacency matrix of G 2 using a single call to MatrixMultiply and $O(n^2)additionaltime.(b)SupposewediscoverthatG2isacompletegraph.DescribeanalgorithmtocomputethematrixDofshortestpathdistancesinGin$O(n^2) additional time. (c) Suppose we recursively compute the matrix D2 of shortest-path distances in 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 and only if $X[i,j]$ \ge $D2[i,j]$ · deg(i). (e) Describe an algorithm to compute the matrix D of shortest-path distances in G in $O(n^{\omega }logn)$ time.

13.

Gideon Yuval proposed the following reduction from min-plus matrix multiplication to standard matrix multiplication in 1976. Suppose we are given two integers $n\times 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

$$C[i,k]=\underset{j}{\min }(A[i,j]+B[j,k]).$$

For all indices $i$ and $k$, define two new $n\times n$ matrices $A^{\prime }$ and $B^{\prime }$ by

$$A^{\prime }[i,j]=n^M-A[i,j]\text{and}{B}^{\prime }[i,j]=n^M-B[i,j].$$

Finally, let $C^{\prime }$ be the standard product of $A^{\prime }$ and $B^{\prime }$, defined by

$$C^{\prime }[i,k]=\sum _j{A}^{\prime }[i,j]\cdot B^{\prime }[j,k].$$

(a) Describe an algorithm to construct $A^{\prime }$ from A using only standard integer arithmetic operations (+, −, ×). (b) Describe an algorithm to extract the min-plus product C from $C^{\prime }$, using only standard integer arithmetic operations (+, −, ×).10 (c) Suppose we can compute the standard product of two n × n integer matrices using $O(n^\omega) arithmetic operations, for some constant 2 \le ω < 3. How many arithmetic operations does Yuval’s algorithm need to compute the 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 $\lfloor x\rfloor$. Trust me; this is a can of worms you do not want to open.

Prev: Shortest Paths Next: Maximum Flows and Minimum Cuts