Groupe d’études et de recherche en analyse des décisions


Shortest Shortest Path Trees of a Network


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.

, 15 pages