|
|||||
|
|
| 最短路径子图 | |
| 作者姓名： | 王涛 李伟生 |
| 作者单位： | 北京交通大学计算机与信息技术学院，北京100044 |
| 摘 要： | 在大型网络中两节点之间的最短路径常常不止一条，而且在带限制条件的路径选择等应用上，常常需要找出多条最优或近优的路径．一些经典的单源最短路径算法，如Dijkstra算法，能找出一条从起始点到目的点的最短路径，但并不能求解两点之间的所有最短路径．本文给出了最短路径子图的概念，用于存储图中两节点之间所有最短路径信息，能够节约存储空间．并给出了最短路径子图构造算法SPSG，其时间复杂度为O(n e)，比同类算法时间复杂度更低．随机网络模型的仿真结果表明：SPSG算法效率更高， |
| 关 键 词： | 图论 Dijkstra算法 最短路径 最短路径子图 |
| 本文献已被 维普 等数据库收录！ | |