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

程 远

(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中选到代价最小的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到T中;否则将此边舍去，重新在剩余边中选择一条权值最小的边.如此重复下去，直到所有顶点在同一个连通分量上为止［9］.

2 用Kruskal最小生成树算法求图最短路径的思想描述

王英和刘天时提出的基于Kruskal算法求图的单源最短路径的方法的基本思想如下［7］:

1)在带权有向图中，对所有带权值的有向边按从1到v号排列由小到大编号并排序，权值相同的边标号相同.然后选取最小边1号加入顶点集，若这些边构成了从网络源点到网络中某点的通路，则该通路为从源点到该点的最短路径.

2)当权值最小的边没有构成从带权有向图网络源点到网络其它点的通路时，则再选取权值次小边2号边，和1号边一起加入到刚才的顶点集中，如果这些边构成的到网络中任意点通路并不唯一，那么在不考虑有向边的情况下图中必定存在圈.此时则采用破圈法去掉图中刚加入的边中的任意一条边，直到图中没有圈为止.依此类推，直到源点到各顶点有且仅有一条路(有向边)，则为最短路径.

3)若在2)中的边不能构成从源点到网络各点的路，则再选取3号边，和前面1号、2号边一起，重复2)的工作.直到将网络中的所有边比较结束，求得最短路径.

3 对基于Kruskal算法在求有向带权图最短路径时出现的问题的探讨

文献［7］中提出了用最小生成树算法求图的最短路径这样一种思路.然而Kruskal最小生成树算法在求图单源最短路径时，会遇到一些特殊的情况，导致该算法找的路径不一定就是实际中的最短路径，有较高权值的边参与的路径也有可能是最短路径.在实际情况中有较高权值边参与的路径可能由于经过的边较少而导致路径权值总和小于低权值的边参与的路径.

这里沿用文献［7］中的一个例子，做了一定的修改后来进行描述.为描述方便，以有向带权图图1为例，求解从A顶点出发到其它各个顶点的最短路径.依据算法的实现步骤，应用过程如下:设G={V，E，L}为图1的有向带权图，其中，E=(AB，AD，AE，BC，CE，DC，DE)，V=(A，B，C，D，E)，L={10，10，20，30，35，70，110}，A 为图的源点.

图1 有向带权图

由图2可以看出，按照文献［7］中所提出的基于Kruskal算法求图的最短路径方法，求得的A到E最短路径的权值为60.而从图3可以看出，实际的A到E最短路径权值为55.由此可以知，文献［7］中所提出的基于Kruskal算法求图的最短路径方法在一些特殊情形下只能求出一个近似解，并不能得出实际的最短路径.

此外，Kruskal算法生成的路径并不唯一［1］.为了消除可能形成的多路径，文献［7］提出了采用破圈法来消除多路径，然而破圈法在实际应用时所耗费的时间复杂度较高［10］，因此也会导致较高的时间代价.

图2 基于Kruskal算法的最短路径算法求解最短路径的过程

图3 实际的最短路径

4 对用最小生成树算法求图的单源最短路径可行性的探讨

基于第3节得到的结论，促使我们认真地探讨最小生成树算法是否适用于求图的单源最短路径问题.

最小生成树算法中最经典的两个算法就是Kruskal算法和Prim算法.Prim算法与Kruskal算法有所不同.Prim算法从任意给定的顶点开始逐渐生成一棵树，每一次都是从那些连接(已构成的)树中顶点的边中选择权值最小的边添加到树中［11］.由描述可以看出，Kruskal算法和 Prim算法的共同特点是都基于贪心算法的策略，总是做出当前状态下的最优解，并不从整体考虑，因此在每一个步骤都选取可行的最优解形成最小生成树的一条边.此外，两个算法生成的最小生成树均不唯一［1］.

从最小生成树算法的特点可以看出，直接将最小生成树算法用于求图的单源最短路径是不可行的.其原因由第3节的讨论以及最小生成树算法的特点可以看出，在实际情况中可能存在有高权值边参与的路径由于经过的边较少从而导致路径权值总和小于低权值的边参与的路径.下面举一个通用例子，用一个带权无向图来说明，如图4所示.

图4 无向带权图

由图4的无向带权图可以看出，A→B→D显然为顶点A到顶点D的一条最短路径.其总权值为25.然而根据最小生成树算法的贪心策略，其每次选的边为当前选择中的最小边，即权值为10的边.这样不论何种最小生成树算法，其所选取的路线均为A→C→B→D.由此可见，最小生成树算法的策略并不适用于图的单源最短路径算法.

5 对单源最短路径算法的探讨

在第4节中论证了最小生成树算法的策略并不适用于图的单源最短路径算法的求解.现有的单源最短路径算法大部分是基于贪心算法或者动态规划算法.经典的如Dijkstra算法、Floyd－Warshall算法、Johnson算法等，这些算法一直是单源最短路径的传统算法，被广泛地研究，亦有很多学者针对这些算法做了大量的改进.比如文献［12－14］就是对Dijkstra算法做了改进，减少了Dijkstra算法的耗费，使之更适用于实际海量数据的最短路径求解，提高了Dijkstra算法的实用程度.此外，比较特殊的像Bellman－Ford算法，可以处理相对比较少见的，图中含有负权边的情况，并能检测和报告出这种负权回路的存在［1］.同时还有基于启发式搜索的A*算法和蚁群算法.这些算法都是通过一定的估价函数，不断强化，从而在大量的节点中找到通往目的点的最短路径.例如，蚁群算法就是通过不断地强化信息素的浓度从而增加节点的选择概率，找到到目标点的最短路径.这类算法，需要选择好启发函数.在一个好的启发函数下，可以极大地提高搜索效率.

6 结语

最小生成树算法在实际生活中有着很多的应用.本文则对最小生成树在求解图的单源最短路径方面的应用进行了探讨.根据第3节和第4节的结论可以看出，由于最小生成树算法是基于贪心策略的特性，使得最小生成树算法并不适用于求解图的单源最短路径问题，并在第5节简单地探讨了现有的可行的单源最短路径算法.

［1］Thomas H C，Charles E L，Ronald L R，等.算法导论［M］.潘金贵，顾铁成，李成法，等译.北京:机械工业出版社，2006:344－380.

［2］赵白云，欧建华.最小生成树算法及其在经济应用中的意义［J］.河南商业高等专科学校学报，1999，12(2):60－62.

［3］梅青平.最短路径算法在城市导航中的应用［J］.高校理科研究:科技信息，2010(32):530－531.

［4］Xu M H，Liu Y Q，Huang Q L，et al.An improved Dijkstra’s shortest path algorithm for sparse network［J］.Applied Mathematics and Computation，2007，185:247－254.

［5］卢照，师军，于海蛟，等.城市路网的最短路径并行求解［J］.计算机技术与发展，2010，20(1):82－85.

［6］杜文霞.基于Prim算法构建商丘市旅游景区最短游线［J］.三门峡职业技术学院学报，2008，7(4):41 －44.

［7］王英，刘天时.基于Kruskal算法的最短路径算法研究［J］.重庆文理学院学报:自然科学版，2009，28(6):37－39.

［8］Leticia Lorenzo，Silvia Lorenzo － Freire.A characterization of Kruskal sharing rules forminimum cost spanning tree problems［J］.International Journal of Game Theory，2009，38:107 －126.

［9］严蔚敏，吴伟民.数据结构［M］.北京:清华大学出版社，2002:175.

［10］龙亚.破圈法构造最小生成树算法探讨［J］.毕节学院学报，2007(4):108－111.

［11］Alsuwaiyel M H.算法设计技巧与分析［M］.吴伟昶，方世昌，等译.北京:电子工业出版社，2004:153－153.

［12］卢照，师军.并行最短路径搜索算法的设计与实现［J］.计算机工程与应用，2010，46(3):69 －71.

［13］Muhammad A Q，Fadzil D，Hassan B，et al.A O(E)time shortest path algorithm for non negative weighted undirected graphs［J］.International Journal on Computer Science and Information Security，2009，l6(1):40－46.

［14］张福浩，刘纪平.一种基于Dijkstra的海量空间数据最短路径算法［J］.辽宁工程技术大学学报:自然科学版，2009，28(4):554 －557.