5
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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)$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for your thoughts. Do you know if (given $d$ and $w$) the method you describe would be more efficient than just running Floyd-Warshall without knowing $d$? When run ab initio, Floyd-Warshall is $O(n^3)$; would the way you describe lead to a different big-oh runtime or rather a $2\times$ speedup? $\endgroup$
    – user
    Nov 1, 2015 at 21:04
  • $\begingroup$ @user My method can be implemented in $O(E)$ to get the annotation mentioned in Wikipedia. $\endgroup$
    – Yuval Filmus
    Nov 1, 2015 at 22:26
  • $\begingroup$ Sorry for my lack of intuition. Aren't there $O(n^2)$ paths ($\forall s \forall t$), and on each you are trying multiple $x$. Is there a trick to somehow prove that there are $o(n)$ $x$ that are tried for each $s,t$ pair? $\endgroup$
    – user
    Nov 1, 2015 at 23:38
  • $\begingroup$ @user The trick is not to calculate the actual paths, but rather the shortest path trees. On reflection you could be right that it takes $O(VE)$ for all nodes. But sometimes you're only interested in the shortest path between two specific nodes. $\endgroup$
    – Yuval Filmus
    Nov 2, 2015 at 5:40
  • $\begingroup$ Since we're rebuilding a shortest path tree, it might help to sort distances in decreasing order first, and then the long paths might contain "enough" shorter subpaths. Or maybe we can do it MST-style, using $d$ as the weights? $\endgroup$
    – G. Bach
    Nov 2, 2015 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.