This question concerns the all-pairs shortest paths (APSP) problem (where we are given a graph with edge $(i,j)$ given weight $w_{i,j}$ by the distances between the two nodes $i$ and $j$, and where we want to get the lowest-weight path from every starting vertex $i$ to every ending vertex $j$),The Path reconstruction subsection of the Wikipedia article on the Floyd-Warshall algorithm, claims:FloydWarshall algorithm typically only provides the lengths of the  paths between all pairs of vertices. With simple modifications, it is  possible to create a method to reconstruct the actual path between any  two endpoint vertices. While one may be inclined to store the actual  path from each vertex to each other vertex, this is not necessary, and  in fact, is very costly in terms of memory. Instead, the Shortest-path  tree can be calculated for each node in (|E|) time using (|V|)  memory to store each tree which allows us to efficiently reconstruct a  path from any two connected vertices.In general (not simply on the FloydWarshall algorithm), if we were given the optimal path distances (i.e., the distances of the most efficient routes) between every starting vertex $i$ and every ending vertex $j$, but not given the paths themselves, is this of any help to finding the best paths? I can think of trivial uses (like branch and bound to discard any paths that exceed the provided optimal path length), but am curious if there are other uses for the minimal distances.Do you know if starting with the minimum final path distances would help find the corresponding paths?
All pairwise shortest paths in a graph: does knowing the path weights help?
algorithms;graphs;shortest path;weighted graphs