All-pairs shortest paths in trees? 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)$.
 A: 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))$.
A: 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.
