All pairwise shortest paths in a graph: does knowing the path weights help? 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:


  Floyd–Warshall 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?
Yes, given the lengths of the shortest paths it is easy to actually find these paths. Suppose for example that you want to find the shortest path from $s$ to $t$. Let $d(s,t)$ be the length of the shortest path, and $w(s,t)$ the length of the edge from $s$ to $t$, or $\infty$ if there is none.

If $d(s,t) = w(s,t)$ then the shortest path is simply $s,t$. Otherwise, there must be a vertex $x$ such that $d(s,t) = w(s,x) + d(x,t)$ (why?). The shortest path then starts $s,x$ and continues with the shortest path from $x$ to $t$, which you can find recursively.

You can also go from $t$ back to $s$ if you prefer. You can also make progress by finding some point $u$ such that $d(s,t) = d(s,u) + d(u,t)$.