Path Reconstruction

Floyd-Warshall computes distances but not the actual paths. To reconstruct paths, maintain a $2D$ array next[i][j]. Initialize next[i][j] = j if there is a direct edge from $i$ to $j$. When you improve dist[i][j] via vertex $k$, set next[i][j] = next[i][k].

After the algorithm, follow next pointers to reconstruct the path from $i$ to $j$. This adds $O(n^2)$ space but allows you to output the actual path, not its length.

Space complexity is $O(n^2)$ for the data structures used.