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

程 遠(yuǎn)

(1.中國科學(xué)技術(shù)大學(xué)，安徽 合肥 230026;2.銅陵學(xué)院，安徽 銅陵 244000)

最小生成樹算法原本是用于求解帶權(quán)無向連通圖中最小生成樹的算法［1］，其在實際生活中的應(yīng)用一直是研究的一個熱門.例如趙白云、歐建華［2］就提出了將最小生成樹算法用于解決城市間的路線選擇問題.而實際應(yīng)用中求解最短路徑的問題更是圖論算法研究的一個熱門，文獻(xiàn)［3］就是研究最短路徑算法的應(yīng)用問題.然而，傳統(tǒng)的求單源最短路徑的Dijkstra算法需要耗費(fèi)大量的時間在路徑的比較和選取上［4］，這樣在實際應(yīng)用中，復(fù)雜的交通網(wǎng)絡(luò)會顯著降低Dijkstra算法的效率［5］.因此隨著最小生成樹算法的廣泛應(yīng)用，有些人則試圖將最小生成樹算法用于求解最短路徑問題.杜文霞［6］提出了將Prim算法所生成的最小生成樹用于求解旅游區(qū)的最短路線.王英和劉天時［7］則更進(jìn)一步，提出了一種利用Kruskal算法來求圖的單源最短路徑的方法.這些研究給最短路徑問題的求解提供了一個新的思考方向.然而，包括Kruskal算法在內(nèi)的最小生成樹算法直接用于求最短路徑，仍然存在一些問題.本文著重探討最小生成樹算法究竟是否適用于求解圖的最短路徑問題.

1 Kruskal最小生成樹算法簡介

Kruskal算法是在1956年由Joseph Bernard Kruskal提出來的［8］.設(shè)有1個有n個頂點和e條邊的連通網(wǎng)絡(luò)G=(V，{E})，n=V，e=E.Kruskal算法的基本思想為:最初先構(gòu)造1個有n個頂點且沒有邊的非連通圖T=(V，θ)，圖中每個頂點自成一個連通分量.當(dāng)在E中選到代價最小的邊時，若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T中;否則將此邊舍去，重新在剩余邊中選擇一條權(quán)值最小的邊.如此重復(fù)下去，直到所有頂點在同一個連通分量上為止［9］.

2 用Kruskal最小生成樹算法求圖最短路徑的思想描述

王英和劉天時提出的基于Kruskal算法求圖的單源最短路徑的方法的基本思想如下［7］:

1)在帶權(quán)有向圖中，對所有帶權(quán)值的有向邊按從1到v號排列由小到大編號并排序，權(quán)值相同的邊標(biāo)號相同.然后選取最小邊1號加入頂點集，若這些邊構(gòu)成了從網(wǎng)絡(luò)源點到網(wǎng)絡(luò)中某點的通路，則該通路為從源點到該點的最短路徑.

2)當(dāng)權(quán)值最小的邊沒有構(gòu)成從帶權(quán)有向圖網(wǎng)絡(luò)源點到網(wǎng)絡(luò)其它點的通路時，則再選取權(quán)值次小邊2號邊，和1號邊一起加入到剛才的頂點集中，如果這些邊構(gòu)成的到網(wǎng)絡(luò)中任意點通路并不唯一，那么在不考慮有向邊的情況下圖中必定存在圈.此時則采用破圈法去掉圖中剛加入的邊中的任意一條邊，直到圖中沒有圈為止.依此類推，直到源點到各頂點有且僅有一條路(有向邊)，則為最短路徑.

3)若在2)中的邊不能構(gòu)成從源點到網(wǎng)絡(luò)各點的路，則再選取3號邊，和前面1號、2號邊一起，重復(fù)2)的工作.直到將網(wǎng)絡(luò)中的所有邊比較結(jié)束，求得最短路徑.

3 對基于Kruskal算法在求有向帶權(quán)圖最短路徑時出現(xiàn)的問題的探討

文獻(xiàn)［7］中提出了用最小生成樹算法求圖的最短路徑這樣一種思路.然而Kruskal最小生成樹算法在求圖單源最短路徑時，會遇到一些特殊的情況，導(dǎo)致該算法找的路徑不一定就是實際中的最短路徑，有較高權(quán)值的邊參與的路徑也有可能是最短路徑.在實際情況中有較高權(quán)值邊參與的路徑可能由于經(jīng)過的邊較少而導(dǎo)致路徑權(quán)值總和小于低權(quán)值的邊參與的路徑.

這里沿用文獻(xiàn)［7］中的一個例子，做了一定的修改后來進(jìn)行描述.為描述方便，以有向帶權(quán)圖圖1為例，求解從A頂點出發(fā)到其它各個頂點的最短路徑.依據(jù)算法的實現(xiàn)步驟，應(yīng)用過程如下:設(shè)G={V，E，L}為圖1的有向帶權(quán)圖，其中，E=(AB，AD，AE，BC，CE，DC，DE)，V=(A，B，C，D，E)，L={10，10，20，30，35，70，110}，A 為圖的源點.

圖1 有向帶權(quán)圖

由圖2可以看出，按照文獻(xiàn)［7］中所提出的基于Kruskal算法求圖的最短路徑方法，求得的A到E最短路徑的權(quán)值為60.而從圖3可以看出，實際的A到E最短路徑權(quán)值為55.由此可以知，文獻(xiàn)［7］中所提出的基于Kruskal算法求圖的最短路徑方法在一些特殊情形下只能求出一個近似解，并不能得出實際的最短路徑.

此外，Kruskal算法生成的路徑并不唯一［1］.為了消除可能形成的多路徑，文獻(xiàn)［7］提出了采用破圈法來消除多路徑，然而破圈法在實際應(yīng)用時所耗費(fèi)的時間復(fù)雜度較高［10］，因此也會導(dǎo)致較高的時間代價.

圖2 基于Kruskal算法的最短路徑算法求解最短路徑的過程

圖3 實際的最短路徑

4 對用最小生成樹算法求圖的單源最短路徑可行性的探討

基于第3節(jié)得到的結(jié)論，促使我們認(rèn)真地探討最小生成樹算法是否適用于求圖的單源最短路徑問題.

最小生成樹算法中最經(jīng)典的兩個算法就是Kruskal算法和Prim算法.Prim算法與Kruskal算法有所不同.Prim算法從任意給定的頂點開始逐漸生成一棵樹，每一次都是從那些連接(已構(gòu)成的)樹中頂點的邊中選擇權(quán)值最小的邊添加到樹中［11］.由描述可以看出，Kruskal算法和 Prim算法的共同特點是都基于貪心算法的策略，總是做出當(dāng)前狀態(tài)下的最優(yōu)解，并不從整體考慮，因此在每一個步驟都選取可行的最優(yōu)解形成最小生成樹的一條邊.此外，兩個算法生成的最小生成樹均不唯一［1］.

從最小生成樹算法的特點可以看出，直接將最小生成樹算法用于求圖的單源最短路徑是不可行的.其原因由第3節(jié)的討論以及最小生成樹算法的特點可以看出，在實際情況中可能存在有高權(quán)值邊參與的路徑由于經(jīng)過的邊較少從而導(dǎo)致路徑權(quán)值總和小于低權(quán)值的邊參與的路徑.下面舉一個通用例子，用一個帶權(quán)無向圖來說明，如圖4所示.

圖4 無向帶權(quán)圖

由圖4的無向帶權(quán)圖可以看出，A→B→D顯然為頂點A到頂點D的一條最短路徑.其總權(quán)值為25.然而根據(jù)最小生成樹算法的貪心策略，其每次選的邊為當(dāng)前選擇中的最小邊，即權(quán)值為10的邊.這樣不論何種最小生成樹算法，其所選取的路線均為A→C→B→D.由此可見，最小生成樹算法的策略并不適用于圖的單源最短路徑算法.

5 對單源最短路徑算法的探討

在第4節(jié)中論證了最小生成樹算法的策略并不適用于圖的單源最短路徑算法的求解.現(xiàn)有的單源最短路徑算法大部分是基于貪心算法或者動態(tài)規(guī)劃算法.經(jīng)典的如Dijkstra算法、Floyd－Warshall算法、Johnson算法等，這些算法一直是單源最短路徑的傳統(tǒng)算法，被廣泛地研究，亦有很多學(xué)者針對這些算法做了大量的改進(jìn).比如文獻(xiàn)［12－14］就是對Dijkstra算法做了改進(jìn)，減少了Dijkstra算法的耗費(fèi)，使之更適用于實際海量數(shù)據(jù)的最短路徑求解，提高了Dijkstra算法的實用程度.此外，比較特殊的像Bellman－Ford算法，可以處理相對比較少見的，圖中含有負(fù)權(quán)邊的情況，并能檢測和報告出這種負(fù)權(quán)回路的存在［1］.同時還有基于啟發(fā)式搜索的A*算法和蟻群算法.這些算法都是通過一定的估價函數(shù)，不斷強(qiáng)化，從而在大量的節(jié)點中找到通往目的點的最短路徑.例如，蟻群算法就是通過不斷地強(qiáng)化信息素的濃度從而增加節(jié)點的選擇概率，找到到目標(biāo)點的最短路徑.這類算法，需要選擇好啟發(fā)函數(shù).在一個好的啟發(fā)函數(shù)下，可以極大地提高搜索效率.

6 結(jié)語

最小生成樹算法在實際生活中有著很多的應(yīng)用.本文則對最小生成樹在求解圖的單源最短路徑方面的應(yīng)用進(jìn)行了探討.根據(jù)第3節(jié)和第4節(jié)的結(jié)論可以看出，由于最小生成樹算法是基于貪心策略的特性，使得最小生成樹算法并不適用于求解圖的單源最短路徑問題，并在第5節(jié)簡單地探討了現(xiàn)有的可行的單源最短路徑算法.

［1］Thomas H C，Charles E L，Ronald L R，等.算法導(dǎo)論［M］.潘金貴，顧鐵成，李成法，等譯.北京:機(jī)械工業(yè)出版社，2006:344－380.

［2］趙白云，歐建華.最小生成樹算法及其在經(jīng)濟(jì)應(yīng)用中的意義［J］.河南商業(yè)高等專科學(xué)校學(xué)報，1999，12(2):60－62.

［3］梅青平.最短路徑算法在城市導(dǎo)航中的應(yīng)用［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］盧照，師軍，于海蛟，等.城市路網(wǎng)的最短路徑并行求解［J］.計算機(jī)技術(shù)與發(fā)展，2010，20(1):82－85.

［6］杜文霞.基于Prim算法構(gòu)建商丘市旅游景區(qū)最短游線［J］.三門峽職業(yè)技術(shù)學(xué)院學(xué)報，2008，7(4):41 －44.

［7］王英，劉天時.基于Kruskal算法的最短路徑算法研究［J］.重慶文理學(xué)院學(xué)報:自然科學(xué)版，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］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學(xué)出版社，2002:175.

［10］龍亞.破圈法構(gòu)造最小生成樹算法探討［J］.畢節(jié)學(xué)院學(xué)報，2007(4):108－111.

［11］Alsuwaiyel M H.算法設(shè)計技巧與分析［M］.吳偉昶，方世昌，等譯.北京:電子工業(yè)出版社，2004:153－153.

［12］盧照，師軍.并行最短路徑搜索算法的設(shè)計與實現(xiàn)［J］.計算機(jī)工程與應(yīng)用，2010，46(3):69 －71.

［13］Muhammad A Q，F(xiàn)adzil 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］張福浩，劉紀(jì)平.一種基于Dijkstra的海量空間數(shù)據(jù)最短路徑算法［J］.遼寧工程技術(shù)大學(xué)學(xué)報:自然科學(xué)版，2009，28(4):554 －557.