  Comparing and computing distances between phylogenetic trees are important
biological problems, especially for models where edge lengths play an important
role. The geodesic distance measure between two phylogenetic trees with edge
lengths is the length of the shortest path between them in the continuous tree
space introduced by Billera, Holmes, and Vogtmann. This tree space provides a
powerful tool for studying and comparing phylogenetic trees, both in exhibiting
a natural distance measure and in providing a Euclidean-like structure for
solving optimization problems on trees. An important open problem is to find a
polynomial time algorithm for finding geodesics in tree space. This paper gives
such an algorithm, which starts with a simple initial path and moves through a
series of successively shorter paths until the geodesic is attained.
