基于最小生成樹算法求解圖的單源最短路徑的研究

程 遠

(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］.河南商業高等?？茖W校學報，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.