基于最小生成树算法求解图的单源最短路径的研究  

Investigation of single-source shortest path graph base on minimum spanning tree algorithm

作　　者：程远[1,2] 

机构地区：[1]中国科学技术大学,安徽合肥230026 [2]铜陵学院,安徽铜陵244000

出　　处：《重庆文理学院学报（自然科学版）》2011年第5期80-82,87,共4页Journal of Chongqing University of Arts and Sciences

摘　　要：对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论.Firstly,the method in the Investigation of A Shortest Path Algorithm based on Kruskal Algorithm was investigated.The example proofed that Kruskal Algorithm can not be directly used to solve the problem of single-source shortest path for the weighted directed graph.Then the problem of using minimum spanning tree algorithm to solve single-source shortest path graph was analyzed,and the example proved the minimum spanning tree algorithm is not suitable for solving the problem of single-source shortest path graph.

关 键 词：最小生成树算法 KRUSKAL算法 图的单源最短路径 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]