### G-93-02

# Shortest Shortest Path Trees of a Network

## Pierre Hansen and Maolin Zheng

Let *N =* (*V,E*) be an undirected network with *n* vertices and *m* edges (i.e., |*V*| = *n* and |*E*| = *m*) in which each edge has a positive length. We study the length of the shortest path trees of *N* rooted at *x* (the length of a shortest path tree is defined to be the sum of the lengths of its edges) and the sum of distances from *x* to all (other) vertices of *N*, where *x* may be a vertex or an internal point of an edge. We first present an *O*(*m n* log *n*) algorithm to find a shortest shortest path tree, i.e., a shortest path tree with minimum length, and then give an algorithm with the same complexity to determine a maximum set of non-equivalent efficient points of *N* for the two criteria cited above. Finally we extend these results to networks with some non-positive edge lengths as well as to directed networks.

Published **January 1993**
,
15 pages