最短路径子图

• 作者: 李伟生 王涛
• 来源期刊: 北方交通大学学报
• 学科: 工学
• 关键词: 图论 Dijkstra算法 最短路径 最短路径子图
• 年，卷（期）: 2004,（2）
• 所属期刊栏目: 计算机与通信工程
• 页码范围: 46-49
• 页数: 4页
• 分类号: TP301.6
• 字数: 3317字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-0291.2004.02.011

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李伟生	北京交通大学计算机与信息技术学院	30	318	8.0	16.0
2	王涛	北京交通大学计算机与信息技术学院	33	379	11.0	19.0