最短路径子图

在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高.

The Shortest Path Subgraph

There are always more than one shortest paths between two nodes in large-scale network, and in the application of route selection with additional constraints, several optimal or near-optimal paths are desired. Some typical algorithms of single source shortest path problem, such as Dijkstra algorithm, can find one shortest path from source node to destination node, but they can't compute all the shortest paths between two nodes. The conception of Shortest Path Subgraph is presented in this paper, and it is able to save the storage spending by using this structure to store all possible shortest paths between two nodes. The SPSG algorithm for constructing the Shortest Path Subgraph is also given. Its computational complexity is O(n e), which is lower than the similar algorithms. The simulation results with random network model show that the SPSG algorithm is more effective.