Question 18.P.6: (S) The Floyd-Warshall algorithm runs in O(n³) time on graph......

Algorithms Illuminated Greedy Algorithms and Dynamic Programming [1340562]

(S) The Floyd-Warshall algorithm runs in O(n³) time on graphs with n vertices and m edges, whether or not the input graph contains a negative cycle. Modify the algorithm so that it solves the all-pairs shortest path problem in O(mn) time for input graphs with a negative cycle and O(n³) time otherwise.

Step-by-Step

The 'Blue Check Mark' means that this solution was answered by an expert.
Learn more on how do we answer questions.

Modify the input graph G = (V,E) by adding a new source vertex s and a new zero-length edge from s to each vertex $v \in V$ . The new graph $G^{\prime}$ has a negative cycle reachable from s if and only if G has a negative cycle. Run the Bellman-Ford algorithm on $G^{\prime}$ with source vertex s to check whether G contains a negative cycle. If not, run the Floyd-Warshall algorithm on G.

Related Answered Questions

Question: 18.P.4

(S) For the input graph what are the final array entries of the Floyd-Warshall algorithm from Section 18.4? ...

Verified Answer:

With columns indexed by k and rows by vertex pairs...

Question: 18.P.5

(S) For the input graph what are the final array entries of the Floyd-Warshall algorithm? ...

Verified Answer:

With columns indexed by k and rows by vertex pairs...

Question: 18.P1

(S) For the input graph what are the final array entries of the Bellman-Ford algorithm from Section 18.2? ...

Verified Answer:

With columns indexed by i and rows by vertices:

Question: 18.6

Let G = (V,E) be an input graph. What is L0,v,w in the case where: (i) v = w; (ii) (v,w) is an edge of G; and (iii) v ≠ w and (v,w) is not an edge of G? a) 0, 0, and +∞ b) 0, ℓvw, and ℓvw c) 0, ℓvw, and +∞ d) +∞, ℓvw, and +∞ (See Section 18.4.6 for the solution and discussion) ...

Verified Answer:

Correct answer: (c). If v = w, the only v-w path w...

Question: 18.3

What’s the running time of the Bellman-Ford algorithm, as a function of m (the number of edges) and n (the number of vertices)? (Choose the strongest true statement.) a) O(n²) b) O(mn) c) O(n³) d) O(mn²) (See Section 18.2.9 for the solution and discussion.) ...

Verified Answer:

Correct answer: (b). The Bellman-Ford algorithm so...

Question: 18.5

Do you see any bugs in the argument above? (Choose all that apply.)a) The concatenation P* of P1 and P2 need not have origin v. b) P need not have destination w. c) P* need not have internal vertices only in {1, 2, . . . ,k}. d) P* need not be cycle-free. ...

Verified Answer:

Correct answer: (d). The concatenation

P^{*...

Question: 18.4

How many invocations of a single-source shortest path subroutine are needed to solve the all-pairs shortest path problem? (As usual, n denotes the number of vertices.) a) 1 b) n − 1 c) n d) n² (See Section 18.3.3 for the solution and discussion.) ...

Verified Answer:

Correct answer: (c). One invocation of the single-...

Question: 18.1

Consider an instance of the single-source shortest path problem with n vertices, m edges, a source vertex s, and no negative cycles. Which of the following is true? (Choose the strongest true statement.) a) For every vertex v reachable from the source s, there is a shortest s-v path ...

Verified Answer:

Correct answer: (a). If you give me a path P betwe...

Question: 18.2

How many candidates are there for an optimal solution to a subproblem with the destination v? (Let n denote the number of vertices in the input graph. The in- and outdegree of a vertex is the number of incoming and outgoing edges, respectively.) a) 2 b) 1 + the in-degree of v ...

Verified Answer:

Correct answer: (b). The optimal substructure lemm...