MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
2  
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. – David Eppstein Mar 27 '11 at 7:24
2  
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. – David Eppstein Mar 27 '11 at 21:47
    
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. – Louis Mar 27 '11 at 22:42
up vote 5 down vote accepted

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

share|cite|improve this answer
2  
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. – Brendan McKay Oct 23 '11 at 14:03

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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