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

王志堅(jiān)，韓偉一，李一軍

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

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

1 修正的Dijkstra算法

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

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

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

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

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

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

Dijkstra算法的具體步驟為:

Step.1 初始化.

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

λ(v)=M;S=φ.

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

Step.3 對(duì)所有未進(jìn)入集合S的、點(diǎn)y的鄰點(diǎn)x進(jìn)行T更新過程.即:

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

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

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

Step.1 初始化.

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

Step.2 在集合R中選取具有最小T標(biāo)號(hào)的點(diǎn)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;

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

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

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

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

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

引理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)時(shí)，都將有μ(y，x)=1且T(y)+w(y，x)=T(x).而當(dāng)T(y)+w(y，x)＞T(x)時(shí)，由算法的Step.3，μ(y，x)的值不發(fā)生變化，由于每個(gè)點(diǎn)僅進(jìn)行一次T更新過程且μ(y，x)的初始值為0，因而μ(y，x)的值仍然為0.另一方面，根據(jù)算法的Step.3，點(diǎn)y的T過程使得T(z)+w(z，x)=T(x)不再成立，情形1將令μ(z，x)=0，從而保證了只有當(dāng)T(y)+w(y，x)=T(x)時(shí)，μ(y，x)的值才可能為1.

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

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

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

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

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

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

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

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

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

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

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

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

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

2 獲得兩點(diǎn)間的所有最短路徑

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

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

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

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

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

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

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

Step.4 令k=2.

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

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

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

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

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

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

在最短路徑圖上，應(yīng)用Yen算法得到從點(diǎn)1到點(diǎn)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)對(duì)Dijkstra算法進(jìn)行了修正，修正后的算法得到的不再是最短路徑樹，而是最短路徑圖.

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

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

［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］孫強(qiáng)，楊宗源.求受頂點(diǎn)數(shù)限制的最短路徑問題的一個(gè)算法［J］.計(jì)算機(jī)工程，2002，28(9):73-74.

［9］周經(jīng)綸，吳煥群.受頂點(diǎn)數(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.