基于點割集的并行最短路徑算法

張清華，李 鴻，沈 文

（1.重慶郵電大學 計算機科學與技術研究所，重慶400065；2.重慶郵電大學 數(shù)理學院，重慶400065）

0 引 言

在18世紀30年代，一個非常有趣的問題引起了歐洲數(shù)學家的濃厚興趣，這個問題要求遍歷普魯士的哥尼斯堡七橋中的每一個座橋恰好一次后回到出發(fā)點.瑞士著名的數(shù)學家歐拉證明了這是不可能完成的.此后，歐拉發(fā)表了著名的論文《依據(jù)幾何位置的解題方法》，這是圖論領域的第一篇論文，標志著圖論的誕生［1］.圖論與其它的數(shù)學分支不同.它不像群論、拓撲等學科那樣有一套完整的理論體系和解決問題的系統(tǒng)方法.最短路問題是重要的最優(yōu)化問題之一，也是圖論研究中一個經典算法問題，它不僅直接應用于解決生產實踐中的眾多問題，而且也經常被作為一種基本工具，用于解決其他的最優(yōu)化問題以及預測和決策問題.

作者主要討論了最短路徑算法（Dij kstra算法），并將割點和點割集引入Dijkstra算法，然后把兩者有機地結合起來形成一種改進算法，即運用粒計算［2］的思想，把原問題分解成許多小規(guī)模的子問題，并且子問題之間互不相關，則可并行計算子問題，從而降低算法的計算復雜度.

1 經典Dijkstra算法的主要思想

1.1 相關定義

定義1［3］邊上有權重的圖稱為加權圖.若邊e標記數(shù)k，稱邊e的權為k..在加權圖中，鏈（跡、路）的長度為鏈（跡、路）上的所有邊的權值的和.

在加權圖中，我們經常需要找出兩個指定點之間的最短路（如有最小長度的路），通常稱其為最短路問題.其中，公認解決這類問題比較典型的算法則是Dijkstra算法.

單源點最短路徑的一個著名算法就是Dijkstra算法，它用于計算一個節(jié)點到其他所有節(jié)點的最短路徑.主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止.Dijkstra算法是求出一個連通加權簡單圖中從結點a到z的最短路.邊｛i，j｝的權w（i，j）＞0，且結點x的標號為L（x）.結束時，L（z）是從a到z的最短路的長度.該算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低.

1.2 算法描述

Dijkstra算法解決了有向圖G＝（V，E）上帶權的單源最短路徑問題，但要求所有邊的權值非負.這個算法是通過為每個頂點v保留目前為止所找到的從s到v的最短路徑來工作的.初始時，原點s的路徑長度值被賦為0（d［s］＝0），同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對于V中所有頂點v除s外d［v］＝ ∞）.當算法結束時，d［v］中儲存的便是從s到v的最短路徑，或者如果路徑不存在的話是無窮大.算法維護兩個頂點集S和Q.集合S保留了我們已知的所有d［v］的值已經是最短路徑的值頂點，而集合Q則保留其他所有頂點.集合S初始狀態(tài)為空，而后每一步都有一個頂點從Q移動到S.這個被選擇的頂點是Q中擁有最小的d［u］值的頂點.當一個頂點u從Q中轉移到了S中，算法對每條外接邊 （u，v）進行拓展.

作者用大O符號將該算法的運行時間表示為邊數(shù)m和頂點數(shù)n的函數(shù).Dijkstra算法最簡單的實現(xiàn)方法是用一個鏈表或者數(shù)組來存儲所有頂點的集合Q，所以搜索Q中最小元素的運算只需要線性搜索Q中的所有元素.這樣的話算法的運行時間是O（n2）.對于邊數(shù)少于n2的稀疏圖來說，我們可以用鄰接表來更有效的實現(xiàn)該算法.

2 割點與點割集

定義2（割點）［3］如果在圖G中刪去一個結點u后，圖G的連通分枝數(shù)增加，即W（G－u）＞W(wǎng)（G），則稱結點u為G的割點，又稱關節(jié)點.沒有割點的非凡連通圖稱為塊.G中不含割點的極大連通子圖稱為圖G的塊.

定義3（點割集）［3－4］如果圖G 的頂點集的一個真子集T滿足W（G－T）＞W(wǎng)（G）或G－T平凡圖，且對于任意的S，如果滿足S是T的真子集，則W（G－S）＝W（G），則稱T為G的一個點割集.

定義4（連通度）［3，5］設 G 是連通圖，稱 K是G 的點割｝為G的點連通度或連通度.

由深度優(yōu)先生成樹可得出兩類關節(jié)點的特性［6－7］：

（1）若生成樹的根有兩棵或兩棵以上的子樹，則此根頂點必為關節(jié)點.

（2）若生成樹中某個非葉子節(jié)點V，其某棵子樹與V的祖先節(jié)點無連接，則V為關節(jié)點.

用深度優(yōu)先搜索算法求出圖的全部割點，再進行分塊，即可達到簡化問題的效果.

定理1［8］在深度優(yōu)先搜索過程中，若e＝uv是父子邊，且k（u）＞1，l（v）≥k（u），則u是割點.

定理2［8］若r是深度優(yōu)先搜索過程中生成的樹的根，則r是圖G割點的充分必要條件是至少有兩條以r為尾的父子邊.

3 基于割點的Dij kstra改進算法

3.1 相關定理證明

為了引出基于割點改進的最短路徑算法，首先得解決下面這幾個問題，才能證明算法的正確性和可行性，下面的性質是基于圖1所示的圖從a到z的最短路徑問題.

性質1 圖1中從a到z的最短的路徑一定經過割點.

證明 我們不妨使用反證法，首先假設最短路徑不經過割點，從a到z有一條最短路徑，我們不妨把其它沒有經過的點全部刪除點，這時把割點刪除后，圖就不連通了，則最短路徑肯定無法找到，因此，這與假設矛盾，則最短的路徑一定經過割點.

性質2 圖1中從a（起始點）到z（終點）的最短路徑同從a（起始點）到f（割點）的最短路徑和f（割點）到z（終點）的最短路徑求和結果是等價的.

證明 為了方便講解，我們不妨先構造一個簡單的示意圖（如圖1所示），首先找到所求加權圖G的所有割點（如點f），由定理1可知，最短路徑一定經過割點（點f），我們不妨以割點為基準線，將圖分成幾個部分，顯然，這里每個部分通過Dij kstra能求出最短路徑，再以割點為銜接點，組成圖G的最短路徑，因此，這是等價的，證畢.

圖1 示意圖GFig.1 Diagram G

性質5 （最短路徑的子路徑是最短路徑［6］）對于一給定的帶權有向圖G＝（V，E），所定義的權函數(shù)為w：E→R.設p＝＜v1，v2，…，vk＞是從v1到vk的最短路徑.對于任意i，j，其中1≤i≤j≤k，設pij＝＜vi，vi＋1，…，vj＞為p中從頂點vi到頂點vj的子路徑.那么，pij是從vi到vj的最短路徑.

性質6 圖1中從a到z最短路徑一定經過點割集中的一個點.

證明 我們不妨使用反證法，首先假設最短路徑不經過某個點割集，從a到z有一條最短路徑，我們不妨把其它沒有經過的點全部刪除點，這時把點割集中所有的點刪除后，圖就不連通了，則最短路徑肯定無法找到，因此，這與假設矛盾，則最短的路徑一定經過點割集中某一個點.

3.2 基于割點的Dijkstra改進算法描述

Step1：使用深度優(yōu)先算法求出所有的割點Ci；

Step2：以割點為基準，分解成多個加權圖Gi；

Step3：對每個加權圖Gi用Dij kstra算法求出最短路徑Pi；

Step4：將每個最短路徑Pi，以割點Ci為銜接點，合并成最短路徑P，P即為所求.

圖2為程序流程圖：

圖2 算法流程圖Fig.2 Algorithm flowchart

3.3 算法偽代碼

Pr ocedure Cut＿vertex Dij kstra

Select割點Cl

把原圖以割點Cl分解成多個Gk

for k：＝1 to（｜Cl｜＋1）

for i：＝1 to nk

L（vi）：＝∞

L（ai）：＝0

｛初始化標記，a的標記為0，其余結點標記為∞，S是空集｝

while zi?S

begin

u：＝不屬于S的L（u）最小的一個頂點

S：＝S∪｛u｝

for所有不屬于S的頂點v

f L（u）＋w（u，v）＜L（v）

then L（v）：＝L（u）＋w（u，v）

｛這樣就給S中添加帶最小標記的頂點并且更新不在S中的頂點的標記｝

end｛L（zk）＝從a到zk的最短路的長度｝

再將所求全并

end｛L（z）＝從a到z的最短路的長度｝

3.4 算法復雜度分析

現(xiàn)在來分析一下該算法的計算復雜度，首先通過前文知道Dijkstra算法的復雜度為O（n2），因為通過割點把原圖分解成了多個相同的小問題，我們不妨設有k個割點，結點最多子圖有nmax個，因此它的計算復雜度為O（n2max）.從這個式子可以看出，計算復雜度與割點的位置有一定的關系，總之，不管怎么樣，只要nmax＜n，則計算復雜度就降低，顯然，只要有割點存在，上式就成立.

因為將圖分成了小圖進行同類問題求解也就是它們求解過程是可以同步操作，互不影響，則可以進行并行計算，從這一方面來說，也大大提高了計算的效率.

4 實驗分析與結果討論

為了更好地說明問題，下面將舉一個例子來說明，通過matlab編寫求割點［9－10］與最短路徑的程序，其程序代碼均可在文獻［8］中找到，將它們組合起來，加入求解運行時間的代碼.

我們不妨作如圖3所示的加權圖，此圖根據(jù)文獻［3］上的例子改變而來，一共有11個點，其中有一個割點（點v6）.

圖3 含有割點的圖Fig.3 Contains a cut vertex of Figure

計算步驟：

Step1：找出加權圖的割點，這里為v6；

Step2：以割點為基準，將圖分成左右兩部份，其中一部分G1包含v1至v66個點，另一部分G2包含v6至v116個點；

Step3：對G1、G2分別用Dij kstra算法求出最短路徑；

Step4：將所求的最短路徑P1和P2，以割點v6為銜接點，合并成一條最短路徑P.

運算結果如表1所示.

在實際情況中，數(shù)據(jù)往往較為復雜，因此割點可能不存在，如圖4所示.那么，我們可以采用點割來進行分解原圖，根據(jù)定理6，子圖最后一定能用點割集中的某個點連接起來.從圖4不難觀察出，點割集不是惟一，那么怎樣尋找點割才是最好的呢？因此，在尋找點割集時，按照以下三大原則執(zhí)行：

（1）盡量保證點割集合的大小也連通度相等；

表1 含有割點的加權圖運行結果Tab.1 Operating results of the weighted graph contains a cut vertex

圖4 不含割點的圖Fig.4 Not Contains a cut vertex of Figure

（2）通過點割集將圖進行分塊，盡量保證每個塊點的個數(shù)相差最?。?/p>

（3）運用并行的思想，整體運行的時間就是最大塊運行的時間.

計算步驟：Step1：因為找不到割點，則按以上三大原則尋找點割，此處為v6和v12；

Step2：以點割為基準，將圖分成左右兩部份，其中一部分G1包含v1至v6和v127個點，另一部分G2包含v6至v127個點；

Step3：對G1、G2分別用Dijkstra算法求出最短路徑；

Step4：將所求的最短路徑P1和P2，以點割集

運算結果如表2所示.

5 結束語

筆者采用逐步細分的思想，把大問題通過一定的方法分解成多個小問題，從而降低計算的時間復雜度.但是，同時也引入了求割點帶來的開銷，因此，本方法只能在一些特定的條件下，發(fā)揮它的優(yōu)勢.總之，作者從一個粒計算求解復雜問題［2，11］的視角來看待問題，對 Dijkstra算法進行了小小的改進.在復雜的實際問題中，可能不存在割點，我們就退而求其點割集，然而怎么尋找點割集，且讓其滿足本文所述的三大原則，這將是我們要繼續(xù)研究的內容.

表2 不含有割點的加權圖運行結果Tab.2 Operating results of the weighted graph not contains a cut vertex

在實際分解子問題時，割點與點割集可結合起來使用，先用割點將原圖分解成子圖，若子圖結點數(shù)仍然較大，可用點割來進一步分解，而且每個子問題屬于同一類問題.因此，可以在互不影響的情況進行計算，即并行實現(xiàn)，則整體的運行時間就是最大塊運行的時間.

顯然，本文的方法應用于某一類型的加權圖時，效率優(yōu)于不改進的最短路徑算法.那么，如何來制定一個判斷的標準呢？

（1）當一個加權圖有多個割點或者連通度較小時，則采用本文的算法能夠很好地提高效率.

（2）點連通度大于多少時，進行分解計算效果不會明顯優(yōu)于不分解的情況.

（3）在求解點連通度以用最小點割集時，同時滿足前面提到的三大原則也是一個難點.

致謝：本文是圖論教學中對Dij kstra算法改進的一種嘗試，感謝重慶郵電大學研究生創(chuàng)新計劃（Y201110）的資助.

［1］ 燕子宗，張寶琪.圖論及其應用［J］.重慶科技學院學報，2007，9（2）：121－123.

［2］ 張清華，周玉蘭，滕海濤.基于粒計算的認知模型.重慶郵電大學學報，2009，21（4）：494－501.

［3］ 殷劍宏，吳開來.圖論及其算法［M］.合肥：中國科學技術大學出版社，2003：63－70.

［4］ 方文其，胡明曉.無向關系圖視覺清晰化顯示算法［J］.計算機工程與科學，2011，33（6）：51－56.

［5］ 康曉軍，王茂才.最短路徑問題的一種高效實現(xiàn)［J］.微計算機信息，2009，25（3）：218－219.

［6］ T HOMAS H，CORMEN CHARLES E，LEISERSON，et al.算法導論［M］.潘金貴譯.北京：機械工業(yè)出版社，2006.9：366.

［7］ 許光漢.用廣度優(yōu)先搜索求割點和塊的算法研究［J］.北京航空航天大學學報，1991（2）：87－94.

［8］ 王海英，黃強.圖論算法及其 MATLAB實現(xiàn)［M］.北京：北京航空航天大學出版社，2012.

［9］ LI Wing－ning.An efficient algorith m for co mputing a mini mum node cutest from a vertex－disjoint path set for ti ming opti mization［C］／／ACMsy mposiu m on Applied Computing，Nashville，Tennessee，USA，F(xiàn)eb，1995：56－60.

［10］ 李克清，黃瑜岳.基于右手法則的網(wǎng)格割點判定算法［J］.計算機與數(shù)字工程，2010，38（7）：6－8.

［11］ TAN Zhi－bin.Minimalcut sets of s－t net works with k－out－of－nodes［J］.Reliability Engineering and System Safety，2003，82（1）：49－54.