Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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 Theran Mar 27 '11 at 22:42

1 Answer 1

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|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

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.