Enumerating problem and optimization problem of shortest path trees

beta

Enumerating problem and optimization problem of shortest path trees

Li Bang

2002

Citations

Journal

Journal of systems engineering

Semantic Scholar

Key Takeaway

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.

Text copied to clipboard

copied to clipboard