最短路径子图
王涛
李伟生
1.北京交通大学,计算机与信息技术学院,北京,1000442.北京交通大学,计算机与信息技术学院,北京,100044
摘要：在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n+e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高.
关键词：图论Dijkstra算法最短路径最短路径子图
分类号：TP301.6(计算技术、计算机技术)
论文发表日期：2004-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：4( 46-49 )
英文信息