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

To construct a shortest path between the two vertices using the predecessor matrix.

Prerequisite

Implement the run() method of the Floyd-Warshall 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. The method is available at the following URL:

https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson6/activity/floydwarshall/FloydWarshall.java

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

In this section, we've introduced the shortest paths problem and visited two different algorithms to solve it: one for single source shortest paths (Dijkstra's algorithm), and another for all pairs shortest paths (Floyd-Warshall). We've shown how different implementations of Dijkstra's algorithm can affect its running time. For both algorithms, we've also shown how to reconstruct shortest paths using a parent array and a predecessor matrix, respectively.