The Structure of the Optimal Solution Set on the Shortest Paths for Networks

The shortest path problem in a network G is to find shortest paths between some specified source vertices and terminal vertices when the lengths of edges are given. The structure of the optimal solutions set on the shortest paths is studied in this paper. First,the conditions of having unique shortest path between two distinguished vertices s and t in a network G are discussed;Second,the structural properties of 2-transformation graph (?) on the shortest-paths for G are presented heavily.

Abstract： The shortest path problem in a network G is to find shortest paths between some specified source vertices and terminal vertices when the lengths of edges are given. The structure of the optimal solutions set on the shortest paths is studied in this paper. First, the conditions of having unique shortest path between two distinguished vertices 8 and t in a network G are discussed; Second, the structural properties of 2-transformation ^-G graph G on the shortest-paths for G are presented heavily.