程 远

(1.中国科学技术大学，安徽 合肥 230026;2.铜陵学院，安徽 铜陵 244000)

最小生成树算法原本是用于求解带权无向连通图中最小生成树的算法［1］，其在实际生活中的应用一直是研究的一个热门.例如赵白云、欧建华［2］就提出了将最小生成树算法用于解决城市间的路线选择问题.而实际应用中求解最短路径的问题更是图论算法研究的一个热门，文献［3］就是研究最短路径算法的应用问题.然而，传统的求单源最短路径的Dijkstra算法需要耗费大量的时间在路径的比较和选取上［4］，这样在实际应用中，复杂的交通网络会显著降低Dijkstra算法的效率［5］.因此随着最小生成树算法的广泛应用，有些人则试图将最小生成树算法用于求解最短路径问题.杜文霞［6］提出了将Prim算法所生成的最小生成树用于求解旅游区的最短路线.王英和刘天时［7］则更进一步，提出了一种利用Kruskal算法来求图的单源最短路径的方法.这些研究给最短路径问题的求解提供了一个新的思考方向.然而，包括Kruskal算法在内的最小生成树算法直接用于求最短路径，仍然存在一些问题.本文着重探讨最小生成树算法究竟是否适用于求解图的最短路径问题.

1 Kruskal最小生成树算法简介

Kruskal算法是在1956年由Joseph Bernard Kruskal提出来的［8］.设有1个有n个顶点和e条边的连通网络G=(V，{E})，n=V，e=E.Kruskal算法的基本思想为:最初先构造1个有n个顶点且没有边的非连通图T=(V，θ)，图中每个顶点自成一个连通分量.当在E中选到代价最小的边时，若该边的两个顶点落在不同……