Scenario

Improve Floyd-Warshall's algorithm so that we're able to reconstruct the shortest path between two given nodes after running the algorithm, using the predecessor matrix.

Aim

Construct a shortest path between the two vertices using the predecessor matrix.

Prerequisite

The predecessor matrix is used to compute the shortest path between two given vertices. Each cell of the predecessor matrix P_ij should be either empty (meaning that there is no path between i and j), or equal to some index k (meaning that vertex k is the one that precedes j in the shortest path between i and j). As such, we need to update our predecessor matrix whenever we use an intermediate vertex.

Implement the run() method of the FloydWarshall class that shall compute the shortest paths for the current graph and populate the path matrix, used later in the path() method to return the path between two given vertices.

public List path(int u, int v) { return null; } public void run() { }

Steps for Completion

1. Adapt the implementation shown in Snippet 6.8 of the Floyd-Warshall algorithm to update the path matrix.
2. Use it to reconstruct the paths similarly to what we have previously shown in the implementation of Dijkstra's algorithm.

public void run() { for (int k = 0; k < adj.length; k++) { for (int i = 0; i < adj.length; i++) { if (adj[i][k] >= Integer.MAX_VALUE) continue; for (int j = 0; j < adj.length; j++) { if (adj[k][j] >= Integer.MAX_VALUE) continue; adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]); } } } }

^{Snippet 6.8: Implementation of Floyd Warshall's algorithm}

We have to use the code below and finsh where it says //write your code here

^{import java.util.List;}

^{public class FloydWarshall { int[][] adj; int[][] path;}

^{public FloydWarshall(int nodes) { this.adj = new int[nodes][nodes]; this.path = new int[nodes][nodes]; for (int i = 0; i < adj.length; i++) { for (int j = 0; j < adj[i].length; j++) { if (i == j) { this.adj[i][j] = 0; this.path[i][j] = i; } else { this.adj[i][j] = Integer.MAX_VALUE; this.path[i][j] = -1; } } } }}

^{public void addEdge(int u, int v, int weight) { if (weight < adj[u][v]) { adj[u][v] = weight; path[u][v] = u; } }}

^{public List path(int u, int v) { \ // Write your code here return null; }}

^{public void run() { // Write your code here } }}