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.)

Question

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.)

Accepted Answer

Correct answer: (c). One invocation of the single-source shortest path subroutine will compute shortest-path distances from a single vertex s to every vertex of the graph (n numbers in all, out of the n² required). Invoking the subroutine once for each of the n choices for s computes shortest-path distances for every possible origin and destination. $^{20}$

$^{20}$ If the input graph has a negative cycle, it will be detected by one of the invocations of the single-source shortest path subroutine.

[latex]^{20}[/latex]If the input graph has a negative cycle, it will be detected by one of the invocations of the single-source shortest path subroutine.

Question 18.4: How many invocations of a single-source shortest path subrou......

Related Answered Questions

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

Verified Answer:

(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 ...

Verified Answer:

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

Verified Answer:

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

Verified Answer:

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:

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:

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:

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:

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: