具有多條最短路徑的最短路問題

王志堅，韓偉一，李一軍

(哈爾濱工業(yè)大學(xué)管理學(xué)院，哈爾濱150001，wyhan@mails.gucas.ac.cn)

單源點正權(quán)最短路問題是最短路問題中最簡單的、應(yīng)用最為廣泛的一類問題，在計算機科學(xué)、交通科學(xué)等工程技術(shù)領(lǐng)域具有非常重要的應(yīng)用. Shimbel［1］提出了第一種算法——矩陣算法，但計算效率較低，計算復(fù)雜性為O(n3logn).長期以來，Dijkstra算法一直是解決正權(quán)單源點最短路問題的最好算法之一［2］，該算法既可用于有向問題，又可用于無向問題，應(yīng)用Fibonacci堆計算復(fù)雜性為O(m+nlogn)［3-7］.然而，它只能求得從源點到其它點的一條最短路徑，最終結(jié)果表現(xiàn)為一棵最短路徑樹.事實上，從源點到指定點可能存在多條最短路徑，Dijkstra算法無法給出所有的最短路徑.為了方便，本文把這類從源點到指定點存在多條最短路徑的問題特稱為具有多條最短路徑的最短路問題.如果源點和指定點僅僅存在數(shù)量不多的最短路徑，獲得這些最短路徑不存在實質(zhì)性難度，可以通過枚舉列出.如果源點和指定點間的最短路徑數(shù)量龐大，則無法一一列出，只能從中選出若干條較滿意的最短路徑，如所選擇的最短路徑具有最少的邊數(shù)等［8-10］.為此，本文將對Dijkstra算法進行修正，修正后的算法得到的不再是最短路徑樹，而是最短路徑圖.在最短路徑圖中，從源點到指定點的任意兩條路徑都具有相同的距離.文中還將基于最短路圖，應(yīng)用Yen算法羅列出從源點到指定點的所有最短路徑.

1 修正的Dijkstra算法

單源點正權(quán)最短路問題可描述為:給定一個具有n個點xi(1≤i≤n)、m條邊的有向圖或無向圖G(V，E)，令源點為v1，邊(vi，vj)的權(quán)w(vi，vj)為正實數(shù).若點v為圖中任意一點，R是G(V，E)中從v1到v的一條路徑，定義路徑的權(quán)是所有邊的權(quán)之和，記為w(R).單源點最短路問題就是在所有從v1到v的路R中，求一條權(quán)最小的路R0使得w(R0)= {w(R)}.

經(jīng)典 Dijkstra算法是一種標(biāo)號算法，其思想為:

1)引入了兩種標(biāo)號，即T和P.T為從源點v1到v的最短路權(quán)的上界，稱為臨時標(biāo)號，記為T(v).P為從源點v1到這一點的最短路權(quán)，稱為固定標(biāo)號，記為P(v).之所以稱為固定標(biāo)號，是因為當(dāng)點v擁有P后，其T的值就不再改變.同時，引入集合S，用以表示所有具有P的點的集合.

2)引入函數(shù)λ(v)，用以記錄路徑R中點v的上一個點.

3)首先令源點v1的T(v1)=0，其它點v的T(v)=+∞，并令源點v1首先成為具有P的點，同時把點v1加入到集合S.算法的每一步總能使一個沒有P的點轉(zhuǎn)變?yōu)樾碌木哂蠵的點，這樣一來，經(jīng)n-1步，所有點都將擁有P，算法終止.這時候，點v的P就是從源點v1到v的最短路權(quán).

4)根據(jù)函數(shù)λ(v)，反溯得到從源點v1到v的最短路徑.

Dijkstra算法的具體步驟為:

Step.1 初始化.

T(v1)=0，λ(v1)=v1;T(v)=+∞，

λ(v)=M;S=φ.

Step.2 選取不擁有P但具有最小T的點y，同時令P(y)=T(y)，S=S∪{y}.

Step.3 對所有未進入集合S的、點y的鄰點x進行T更新過程.即:

如果T(y)+w(y，x)＜T(x)，那么T(x)= T(y)+w(y，x)，同時令λ(x)=y.

Step.4 如果所有點都進入集合S，那么算法停止，根據(jù)函數(shù)λ(v)得到從源點v1到v的最短路徑，否則轉(zhuǎn)入Step.2.

應(yīng)用Dijkstra算法可以求得最短路徑樹.在最短路徑樹中，從源點到任意點僅僅只有一條最短路徑，這條路徑在原圖中則表現(xiàn)為相應(yīng)兩點之間的一條最短路徑.下面給出修正的Dijkstra算法為:

Step.1 初始化.

T(v1)=0;μ(y，x)=0;R={v1};S=φ.

Step.2 在集合R中選取具有最小T標(biāo)號的點y，則:

1)S=S∪{y}，R=R-{y};

2)若邊(y，x)∈E且x?S，則R=R∪{x}.

Step.3 若邊(y，x)∈E，則:

情形1 若T(y)+w(y，x)＜T(x)，則T(x)=T(y)+w(y，x)，μ(y，x)=1;

同時若μ(z，x)=1且z≠y，則μ(z，x)=0.

情形2 若T(y)+w(y，x)=T(x)，則μ(y，x)=1.

Step.4 如果所有點都進入集合S，那么算法停止，把所有μ(y，x)=0的邊從圖G(V，E)中刪去，這樣得到的新圖就是最短路徑圖，記為G#，在G#中從源點v1到v的任意一條路徑都是原圖G(V，E)中從源點v1到v的最短路徑，此時的T(v)就是從源點v1到v的最短路徑的權(quán);否則轉(zhuǎn)入Step.2.

修正的Dijkstra算法相對于經(jīng)典的Dijkstra算法得到的不再是最短路徑樹，而是最短路徑圖.在最短路徑圖中，從源點到指定點的任意一條路徑在原圖中均是最短路徑.修正的Dijkstra算法具有:1)本改進算法僅保留了Dijkstra算法的T標(biāo)號，簡化了Dijkstra算法;2)在Dijkstra算法的初始化步驟中，令T(v)=+∞，這給計算機編程實現(xiàn)帶來了困難，不得不選定一個足夠大的數(shù)來代替+∞，本文的算法可避免這個麻煩.

下面給出算法正確性的證明:

引理1 在修正的 Dijkstra算法中，如果T(y)+w(y，x)=T(x)，那么必有μ(y，x)=1.

證明 根據(jù)算法的Step.3，當(dāng)T(y)+w(y，x)＜T(x)或T(y)+w(y，x)=T(x)時，都將有μ(y，x)=1且T(y)+w(y，x)=T(x).而當(dāng)T(y)+w(y，x)＞T(x)時，由算法的Step.3，μ(y，x)的值不發(fā)生變化，由于每個點僅進行一次T更新過程且μ(y，x)的初始值為0，因而μ(y，x)的值仍然為0.另一方面，根據(jù)算法的Step.3，點y的T過程使得T(z)+w(z，x)=T(x)不再成立，情形1將令μ(z，x)=0，從而保證了只有當(dāng)T(y)+w(y，x)=T(x)時，μ(y，x)的值才可能為1.

綜合上述幾種情形，當(dāng)μ(y，x)=1時，T(y)+ w(y，x)=T(x)時，總有μ(y，x)=1.

定理1 修正的Dijkstra算法可獲得從源點v1到點v的所有最短路徑.

證明 假設(shè)P0=(v1，U1，…，Ui，…，Uh，v)是得到的從點v1到點v的任一條最短路徑，而P1=(v1，Q1，…，Qi，…，Qr，v)是從點v1到點v的任意一條路徑.

根據(jù)算法的步驟和引理1，對于路P0有

如果P1也是從點v1到點v的一條最短路徑，那么必有

根據(jù)引理1，那么總有μ(Qr，v)=1.這樣就保證了邊(Qr，v)保留在最短路圖中.同時，也必然有

否則P1就不是從點v1到點v的最短路徑，這樣也有μ(v1，Q1)=1且μ(Qi-1，Qi)=1(2≤i≤r)，說明P1中的所有邊都在最短路圖中.

鑒于P1的任意性，因而修正的Dijkstra算法總可獲得從源點v1到點v的所有最短路徑，這些最短路徑中的任意一邊都保留在最短路圖中.

定理1保證了算法的正確性.由引理1和定理1可直接得到:

推論1 在最短路圖中，從點v1到點v的任一條路徑都是原圖中從點v1到點v的最短路徑.

例1 求解下列最短路問題.

在例1中，顯然從點1到點2～點8和點9都存在多條路徑，應(yīng)用經(jīng)典的Dijkstra算法得到的最短路徑樹為:

而應(yīng)用修正的Dijkstra算法，得到的最短路徑圖與原圖相同.由最短路徑圖，從點1到點9將具有8條最短路徑.例1的圖規(guī)模較小，列出兩點間的所有最短路徑是容易的，而當(dāng)圖的規(guī)模龐大且兩點間的最短路徑的數(shù)目可觀時，將不得不尋求專門的算法.

2 獲得兩點間的所有最短路徑

應(yīng)用修正的Dijkstra算法得到一個最短路徑圖.該算法基于最短路徑圖可以獲得從源點到指定點的所有最短路徑.該算法的思想是，根據(jù)各最短路徑中邊的數(shù)目對各最短路徑進行排序，邊數(shù)越少的最短路徑對應(yīng)的級別就越高，算法將按照級別由高到低的順序依次列出所有的最短路徑.

如果令最短路徑圖中的各邊的權(quán)均為1，那么從源點到指定點的路徑長度和路徑中的邊數(shù)相等.這樣一來，從源點到指定點的路徑長度越短，該路徑的級別就越高.按照級別由高到低依次列出所有的最短路徑，可以借助于求解第k條最短路徑問題的Yen算法來解決［11］.

設(shè)從源點到指定點有多條路徑，這些路徑具有不同的長度，如果按照長度由小到大進行排序，那么第k條最短路徑是指排在第k個位置的路徑.Yen算法是求解無圈第k條最短路徑問題當(dāng)前公認的最好算法.Yen算法的思想是，首先求得從源點到指定點的第1，2，…，k-1條最短路徑，然后在這k-1條最短路徑的基礎(chǔ)上求得第k條最短路徑.由于在最短路徑圖中，從源點到指定點的最短路徑是有限的，因而當(dāng)k足夠大時，按照Yen算法總可以求得從源點到指定點的所有最短路徑.

下面給出獲得所有最短路徑的算法為:

Step.1 應(yīng)用修正的Dijkstra算法得到最短路徑圖G#.

Step.2 令最短路圖G#中所有邊的權(quán)均為1，得到新的圖G*.

Step.3 應(yīng)用經(jīng)典的Dijkstra算法得到圖G*的從源點到指定點的最短路徑，也就是第1條最短路徑.

Step.4 令k=2.

Step.5 應(yīng)用Yen算法求得圖G*的從源點到指定點的第k條最短路徑.如果Yen算法無法得到第k條最短路徑，則算法結(jié)束，否則轉(zhuǎn)入Step.6.

Step.6 k=k+1，轉(zhuǎn)入Step.5.

由于從源點到指定點的最短路徑的數(shù)目是有限的，因而算法是收斂的.事實上，在算法的Step.3就得到了從源點到指定點的、邊數(shù)最少的一條最短路徑.

例2 求解下列最短路問題，求得從點1到點9的所有最短路徑.

解:應(yīng)用修正的Dijkstra算法得到最短路徑圖.

由最短路徑圖，可知從點1到點9具有多條最短路徑，最短路徑的長度為20.接下來，令最短路徑圖的各邊的權(quán)均為1，得到:

在最短路徑圖上，應(yīng)用Yen算法得到從點1到點9的所有最短路徑為:

第1條最短路徑:1→2→9;

第2條最短路徑:1→4→2→9;

第3條最短路徑:1→4→5→9;

第4條最短路徑:1→3→4→5→9;

第5條最短路徑:1→3→4→2→9;

第6條最短路徑:1→4→6→7→8→9;

第7條最短路徑:1→3→6→7→8→9;

第8條最短路徑:1→3→4→6→7→8→9.

3 結(jié)論

1)對Dijkstra算法進行了修正，修正后的算法得到的不再是最短路徑樹，而是最短路徑圖.

2)對Dijkstra算法進行了簡化，不再沿用P標(biāo)號僅僅保留了T標(biāo)號，在初始化步驟中也不再令各點的T標(biāo)號的值為無窮大，客觀上為算法的計算機實現(xiàn)提供了方便.

3)基于最短路徑圖，應(yīng)用求解第k條最短路徑的Yen算法，根據(jù)邊數(shù)由少到多可依次給出從源點到指定點的所有最短路徑.

［1］SHIMBEL A.Structure in communication nets［C］// Proceedings of the Symposium on Information Networks. New York:Polytechnic Press of the Polytechnic Institute of Brooklyn，1955:199-203.

［2］DIJKSTRA E W.A note on two problems in connexion with graphs［J］.Numerische Mathematik，1959，1(1):269-271.

［3］FREDMAN M L，TARJAN R E.Fibonacci heaps and their uses in improved network optimization problems［J］.Journal of the ACM，1987，34(3):596-615.

［4］NOSHITA K，MASUDA E，MACHIDA H.On the expected behaviors of the Dijkstra’s shortest paths algorithm for complete graph［J］.Information Processing Letters，1978，7(5):237-243.

［5］NOSHITA K.A theorem on the expected complexity of Dijkstra’s shortest paths algorithm［J］.Journal of Algorithms，1985，6(3):400-408.

［6］PETTIE S，RAMACHANDRAN V.Computing shortest paths with comparisons and additions［C］//Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms.Philadelphia:Society for Industrial and Applied Mathematics，2002:267-276.

［7］PETTIE S，RAMACHANDRAN V.A shortest path algorithm for real-weighted undirected graphs［J］.SIAM Journal on Computing，2005，34(6):1398-1431.

［8］孫強，楊宗源.求受頂點數(shù)限制的最短路徑問題的一個算法［J］.計算機工程，2002，28(9):73-74.

［9］周經(jīng)綸，吳煥群.受頂點數(shù)限制的最短路徑問題及其算法［J］.系統(tǒng)工程，l996，l4(5):37-44.

［10］MARFINS V E Q.On a multicriteria shortest path problem［J］.European Journal of Operational Research，1984，l6(2):236-245.

［11］YEN J Y.Finding the K shortest loopless paths in a network［J］.Management Science，1971，17(11):712-716.