Implementation of Floyd-Warshall

Implementation notes

The implementation of Floyd-Warshall is relatively straightforward compared to Dijkstra’s algorithm. We’ll construct the matrices $A_0, P_0$ from the weighted adjacency list and then iteratively compute the distance and predecessor matrices $A_k, P_k$, for $k = 1, \ldots, |V|$.

One important observation to reduce the memory footprint of the algorithm is that the computation of $A_{k+1}$ and $P_{k+1}$ ...