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}

Grading

Complete each task listed below. Each task contains automated checks which are used to calculate your grade. When you have completed each task by clicking the checkbox, open the task list panel on the left navigation bar and click the "Submit" button.

Task

Completed the implementation of the run() and path() method by improving the Floyd-Warshall algorithm.