The Floyd-Warshall algorithm below calculates the shortest path between every pa

Question

The Floyd-Warshall algorithm below calculates the shortest path between every pair of vertices i and j in a graph that has positive edge lengths and is directed (for this problem).

(b) The pseudocode above computes the length of the shortest path between every two vertices, but it does not compute the prev pointers associated with that shortest path.

Suppose we define a new table, prev, where prev(i, j, k) stores the predecessor of j on a shortest-path from i to j using only vertices in {1, . . . , k} as intermediate vertices. Give a recurrence for prev(i, j, k), including a base case. Then give the pseudocode for a modified version of Floyd-Warshall that computes both the dist table and the prev table.

Explanation / Answer

import java.util.Scanner; /** Class Warshall **/ public class Warshall { private int V; private boolean[][] tc; /** Function to make the transitive closure **/ public void getTC(int[][] graph) { this.V = graph.length; tc = new boolean[V][V]; for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.