Key Takeaway: This paper presents an algorithm for constructing shortest path networks in nonnegative networks, an algorithm for enumerating shortest path trees, and an algorithm for optimizing shortest path trees.

Abstract

First, this paper gives an algorithm to construct the shortest path network in nonnegative network. Then using the enumerating problem of arborescences in the shortest path network, we design an algorithm to enumerating problem of shortest path trees. Using the Gabow algorithm, we design an algorithm to generate all the shortest path trees. Lastly, the optimization problem of shortest path trees is studied.