| 基于最小生成树算法求解图的单源最短路径的研究 |
| |
| 引用本文： | 程远.基于最小生成树算法求解图的单源最短路径的研究[J].重庆文理学院学报(自然科学版),2011,30(5):80-82. |
| |
| 作者姓名： | 程远 |
| |
| 作者单位： | [1]中国科学技术大学,安徽合肥230026;[2]铜陵学院,安徽铜陵244000 |
| |
| 摘 要： | 对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论.
|
| 关 键 词： | 最小生成树算法 KRUSKAL算法 图的单源最短路径 |
Investigation of single-source shortest path graph base on minimum spanning tree algorithm |
| |
| Abstract: | 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. |
| |
| Keywords: | minimum spanning tree algorithm Kruskal algorithm single-source shortest path graph |
| 本文献已被 万方数据 等数据库收录！ |
