摘要
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.
关键词
网络
转化图
结构特点
最佳解
networks
the shortest-paths
2-transformation graphs
structural properties