13
$\begingroup$

This is a reference request, since I'm sure what follows isn't new, but I can't seem to find it.

Suppose that we have a finite tree $T$ with non-negative weights on the edges. Naively, computing the path lengths (i.e., sum of the weights along the unique path) between every pair requires $O(n^3)$ steps: there are $\binom{n}{2}$ pairs of vertices and we can always bound the number of edges on any path by $n-1$.

We can, however, do a great deal better with the following trick. Pick a root $r$ for $T$ arbitrarily. Define the least common ancestor of $i$ and $j$ as the vertex $a$ where the path from $i$ to $r$ meets the path from $j$ to $r$. Then if $d(\cdot,\cdot)$ denotes the distance in $T$, we get $d(i,j) = d(i,r) + d(j,r) - 2d(a,r)$.

It's easy to see that all the $d(i,r)$ can be computed in $O(n)$ steps with BFS. There's also a data structure of Harel and Tarjan that, after $O(n)$ preprocessing will answer least common ancestor queries in $O(1)$ time. So the whole thing becomes $O(n^2)$.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ My feeling (having tried and failed several times to find a good early reference) is that this is folklore, but I'd also be interested in an answer. I regularly mention this in my graduate data structures class, and I've used it in some of my own papers, but I don't know its source. Tarjan's 1979 "Applications of Path Compression on Balanced Trees" has a more complicated $O(n^2\alpha(n))$ algorithm for computing any semigroup combination of edge values on paths between all pairs of nodes, whereas this trick is faster and simpler but requires that the combination be a group. $\endgroup$
    – David Eppstein
    Mar 27, 2011 at 7:24
  • 2
    $\begingroup$ Just to add to my previous comment: actually, Tarjan's method is $O(m\alpha(m,n))$ for computing $m$ pairs, where $\alpha$ is the two-parameter inverse Ackermann function. In the all-pairs case, this simplifies to constant time per pair, or total time $O(n^2)$, the same as with the trick described in the question. $\endgroup$
    – David Eppstein
    Mar 27, 2011 at 21:47
  • $\begingroup$ Thanks, David. My actual interest is closer to your first comment: I have a directed graph with group elements on the edges, and want to compute the image of the induced map from fundamental cycles of a tree into the group (by adding up with appropriate signs around each cycle). The same trick works there, but I figured that it would be known for APSP. $\endgroup$
    – Louis
    Mar 27, 2011 at 22:42

2 Answers 2

Reset to default
7
$\begingroup$

Just do a bfs on every node. Every search gives you a fine one-to-all shortest path in the tree.

All in all $n$ times $O(n)$ = $O(n^2)$.

You can also do it in $O(n)$, if you don't mind the distances being stored implicitly (still $O(1)$ lookups): Make an LCA datastructure, and calculate the distances from the root to every node $d(u)$. Then the shortest path between $u$ and $v$ is just $d(u)+d(v)-2d(lca(u,v))$.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Right, and DFS is fine for a tree too. It can also be done with a single DFS scan and a little bit of bookkeeping (as the children of each node are completed, calculate the distances between them and the descendants of previous children of that node). If instead of adding distances we have to do a noncommutative operation like multiplication in a group, it seems that keeping separate track of the left-right and right-left products will suffice. $\endgroup$
    – Brendan McKay
    Oct 23, 2011 at 14:03
  • $\begingroup$ If you want the LCA lookup to be $O(1)$, I think we need to implement something like tarjan's offline LCA algorithm which runs $O(n+Q)$ which is $O(n^2)$ in this case (since $Q=O(n^2)$ here). If we use an online LCA algorithm, then the lookup will be $O(\log n)$ overall $\endgroup$
    – suncup224
    Nov 29, 2021 at 8:49
  • $\begingroup$ @suncup224 Of course you have to run in $\Omega(n^2)$ time if you do $n^2$ queries. That's why I'm saying the distances are "stored implicitly", but still with $O(1)$ time per distance you are interested in, just as if you had made a table. $\endgroup$
    – Thomas Dybdahl Ahle
    Dec 1, 2021 at 17:05
1
$\begingroup$

Another variant would be to start with an arbitrary vertex and then to update the all pairs shortest paths table each time a new vertex is discovered, that is adjacent to one of the previously discovered ones.

When discovering vertex $v$ via edge $(u,v)$, the entries of row $u$ and of column $v$ of the distance table $T$ are first duplicated into row $v$ and colum $v$ respectively; then to every newly generated non-zero entry in the distance table the weight $w(u,v)$ of edge $(u,v)$ is added and finally the distance from $u$ to $v$ and from $v$ to $u$ are set to $w(u,v)$

The sequential complexity is $O(n^2)$, but the algorithm is much simpler and in contrast to the other variants, this algorithm also works for dynamically growing trees, i.e. initially unknown trees and/or trees with no upper bound on final size.

That algorithm can also exploit parallel computing capability, e.g. of GPUs; the complexity would then be $O(n)$ under the assumption that an unlimited number of processors is available.

Improve this answer
$\endgroup$

Your Answer

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

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