Question 18.P.5: (S) For the input graph what are the final array entries of ......

Algorithms Illuminated Greedy Algorithms and Dynamic Programming [1340562]

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

Step-by-Step

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

With columns indexed by k and rows by vertex pairs:

(1,1)	0	0	0	0	-4
(1,2)	2	2	2	2	-2
(1,3)	5	5	3	3	-1
(1,4)	$+\infty$	$+\infty$	$+\infty$	0	-4
(2,1)	$+\infty$	$+\infty$	$+\infty$	$+\infty$	-6
(2,2)	0	0	0	0	-4
(2,3)	1	1	1	1	-3
(2,4)	$+\infty$	$+\infty$	$+\infty$	-2	-6
(3,1)	$+\infty$	$+\infty$	$+\infty$	$+\infty$	-7
(3,2)	$+\infty$	$+\infty$	$+\infty$	$+\infty$	-5
(3,3)	0	0	0	0	-4
(3,4)	-3	-3	-3	-3	-7
(4,1)	-4	-4	-4	-4	-8
(4,2)	$+\infty$	-2	-2	-2	-6
(4,3)	$+\infty$	1	-1	-1	-5
(4,4)	0	0	0	-4	-8
	0	1	2	3	4

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

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

Modify the input graph G = (V,E) by adding a new s...

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