  We present two algorithms for computing the geodesic distance between
phylogenetic trees in tree space, as introduced by Billera, Holmes, and
Vogtmann (2001). We show that the possible combinatorial types of shortest
paths between two trees can be compactly represented by a partially ordered
set. We calculate the shortest distance along each candidate path by converting
the problem into one of finding the shortest path through a certain region of
Euclidean space. In particular, we show there is a linear time algorithm for
finding the shortest path between a point in the all positive orthant and a
point in the all negative orthant of R^k contained in the subspace of R^k
consisting of all orthants with the first i coordinates non-positive and the
remaining coordinates non-negative for 0 <= i <= k.
