無向圖中嚴格第三短路問題的多項式時間算法

曾慶紅

(保山學院數(shù)學學院，云南保山678000)

最短路問題是圖論中的核心問題之一，最短路算法是許多更深層算法的基礎(chǔ).次短路問題最早是由 Lalgudi和 Papaefthymiou［1］于 1997 年提出，并證明了非負權(quán)重有向圖中次短路問題是NP－完備的，而當次短路允許含圈時這個問題是有多項式時間算法的.2004 年 Krasikov和 Noble［2］首次設(shè)計了一個O(n3m)多項式時間算法解決正權(quán)重無向圖中次短路問題，這里及下面都要求是簡單路，即不含圈和回路.2006年Li等［3］在O(n3m)算法的基礎(chǔ)上設(shè)計了一個O(n3)多項式時間算法解決正權(quán)重無向圖中次短路問題.2010年Kao等［4］設(shè)計了一個O(n2)多項式時間算法解決正權(quán)重無向圖中次短路問題.2011年Wu［5］設(shè)計了一個O(m+nlog n)多項式時間算法解決正權(quán)重無向圖中次短路問題.2011年Zhang和Nagamochi［6］設(shè)計了一個 O(n6)多項式時間算法解決非負權(quán)重無向圖中次短路問題.2012年Wu［7］等人提出一個線性時間算法解決非負權(quán)重無向圖中次短路問題.1971 年 Yen［8］設(shè)計一個O(kn(m+nlog n))時間算法解決有向圖中第k短路問題.1982年Katoh［9］等人設(shè)計一個O(k(m+nlog n))時間算法解決無向圖中第k短路問題.而嚴格第k短路問題目前還沒有相關(guān)的多項式時間算法解決.

把最短路及次短路算法與最小費用整數(shù)流方法結(jié)合起來研究嚴格第三短路問題，并設(shè)計一個O(n4)多項式時間算法解決正權(quán)重無向圖中嚴格第三短路問題.

1 基本概念與引理

定義1 給定一個無向賦權(quán)圖G=(V，E;w;s，t)，其中s，t是2個固定頂點，w:E→R+是邊的長度函數(shù).

1)在 G中尋找一條從 s到 t的路 Pst，使得w(Pst)≤w(Qst)，其中:，Qst是從s到t的任意一條路.稱路Pst是從s到t的一條最短路.最短路問題是指在圖G中求出s－t最短路及其長度.

2)在G中尋找一條從 s到t的路P'st，滿足:w(P'st)=min(w(P)|w(P)＞ w(Pst))，其中:Pst是s到t的一條最短路，P是s到t的任意一條路.稱路P'st是從s到t的一條次短路.次短路問題是指在圖G中求出s－t次短路的長度.

3)在G中尋找一條從s到t的路P″st，滿足:w(P″st)=min(w(P)|w(P) ＞ w(P'st))，其中:P'st是s到t的一條次短路，P是s到t的任意一條路.稱路P″st是從s到t的一條嚴格第三短路.嚴格第三短路問題是指在圖G中求出s－t嚴格第三短路的長度.

定義2 給定一個無向賦權(quán)圖G=(V，E;w;s，t)，其中s，t是2個固定頂點，是邊的長度函數(shù).構(gòu)造s － t最短路網(wǎng)絡(luò) DG=(Vst，Ast;w;s，t)，構(gòu)造方法如下:弧(u，v)∈Ast當且僅當弧(u，v)在原圖G中的某一條s－t最短路上，頂點集合Vst是指所有s－t最短路上的頂點組成的集合.稱最短路網(wǎng)絡(luò)上的弧對應與原圖G中的邊為內(nèi)部邊，其余的邊稱為外部邊.稱最短路網(wǎng)絡(luò)上指向頂點t的弧為正向弧，反之稱為反向弧.如果一條s－t路至少含有一條外部邊或至少含有一條反向弧，則稱這條路中由外部邊組成的子路或反向弧組成的子路為反常路.

引理1［4］給定1個無向賦權(quán)圖G=(V，E;w;s，t)，其中 s，t是2 個固定頂點，w:E → R+是邊的長度函數(shù).則圖G的s－t次短路P'st至少含有1條外部邊或至少含有1條反向弧.

引理2［4］給定1個無向賦權(quán)圖G=(V，E;w;s，t)，其中 s，t是2 個固定頂點，w:E → R+是邊的長度函數(shù).則圖G的s－t次短路P'st上所有的外部邊或反向弧一定是連續(xù)的.

引理3［2］給定1個無向賦權(quán)圖G=(V，E;w;s，t，x)，其中 s，t，x 是 3 個固定頂點，w:E → R+是邊的長度函數(shù).則存在一個O(n2)多項式時間算法求從s經(jīng)過頂點x到t的最短路Psxt.

引理4 給定1個無向賦權(quán)圖G=(V，E;w;s，t)，其中s，t是2個固定頂點，w:E→R+是邊的長度函數(shù).則圖G的s－t嚴格第三短路最多含有2條反常路.

證明 反證法，假設(shè)圖G的s－t嚴格第三短路P″st含有 3 條反常路 P1，P2，P3，則存在 1 條只含有 2條反常路(含 P1，P2或 P1，P3或 P2，P3)的 s－ t路，路的長度嚴格大于次短路的長度且嚴格小于路 P″st的長度，這與 P″st是嚴格第三短路矛盾.故引理得證.

引理5 給定1個無向賦權(quán)圖G=(V，E;w;s，t，x，y)，其中s，t，x，y是G中4 個固定的頂點，w:E→R+是邊的長度函數(shù).則存在一個O(n2)多項式時間算法求從頂點s到頂點x和從頂點y到頂點t的2條點不交的最短路.

證明 首先利用圖G構(gòu)造1個網(wǎng)絡(luò)N=(V，A;b，c;s，t)，構(gòu)造方法如下:將原圖G中的每一條邊變成2條向相的弧，每條弧的容量為無窮大，費用為邊權(quán)重;增加2個頂點u，v，從頂點u加2條弧分別指向頂點x，y，每條弧的容量為無窮大，費用為0.從頂點s，t加2條弧分別指向頂點v，每條弧的容量為無窮大，費用為0.頂點u，v的容量為無窮大，其余頂點的容量為1.要求從頂點s到頂點x和從頂點y到頂點t的2條點不交的最短路就相當于求從頂點u到頂點v的流量值為2的最小費用整數(shù)流.所以可以利用最小費用整數(shù)流方法在O(n2)時間內(nèi)求出從頂點s到頂點x和從頂點y到頂點t的2條點不交最短路.

2 算法

求次短路的基本思想:通過分析無向圖中最短路問題，利用Dijkstra算法計算2個固定頂點s，t之間的所有最短路，在s－t最短路網(wǎng)絡(luò)上求次短路.求次短路的方法是對任意頂點x∈V－{t}刪除其在最短路網(wǎng)絡(luò)N上的所有出弧G=(V，E;w;s，t)所對應于原無向圖中的邊得到一個新的無向圖G'=(V，E';w;s，t)，然后在新圖G'求從起點s經(jīng)過頂點x到終點t的最短路Psxt，最小者就是次短路.

稱次短路算法為:Next－to－shortest path algorithm，簡稱 NTSPA.詳細算法如下［3］:

算法 1［3］NTSPA

輸入:無向賦權(quán)圖 G=(V，E;w;s，t)，其中 s，t∈ V，w:E → R+.

輸出:求出s到t的次短路或說明無次短路.

Step 1:利用Dijkstra算法求出圖G所有s－t最短路，然后構(gòu)造最短路網(wǎng)絡(luò) DG=(Vst，Ast;w;s，t);

Step 2:置S=?;

Step 3:對于所有x∈V－{t}:

刪除頂點x在最短路網(wǎng)絡(luò)DG中所有的出弧對應于原圖G中的邊，得到一個新的無向圖G'=(V，E';w;s，t);

利用最小費用整數(shù)流方法在新圖G'=(V，E';w;s，t)中求出從s經(jīng)過頂點x到t的最短路Psxt;

S=S∪{w(Psxt)};

Step 4:如果(S=?)則說明沒有s－t次短路;否則輸出S中的最小者.

定理1［3］算法1可以解決次短路問題，其時間復雜性為O(n3).

下面分析嚴格第三短路候選路:

1)含1條反常路的s－t路中的第二短路.

求候選路方法:對任意頂點x∈V－{t}刪除其在最短路網(wǎng)絡(luò)N上的所有出弧所對應于原無向圖中的邊得到一個新的無向圖G'=(V，E';w;s，t).利用最小費用整數(shù)流的方法在新圖G'中求從起點s經(jīng)過頂點x到終點t的最短路Psxt，這些路的長度一定比最短路更長.其中，最小者就是次短路，而第二小者是嚴格第三短路的候選路.算法1已經(jīng)求出這條候選路.

2)含2條反常路的s－t路中的最短路.

求候選路方法:對任意2個頂點x，y∈V－{t}，刪除頂點x，y在最短路網(wǎng)絡(luò)DG中的所有出弧所對應于原圖 G 中的邊，得到新圖 G″=(V，E″;w;s，t).利用最小費用整數(shù)流方法在新圖G″中求出從s經(jīng)過頂點x，y到t的最短路Psxyt.其中，最小者是嚴格第三短路的候選路.

定理2 算法1得到的結(jié)果S中的最小者是次短路記為:S1，第二小者是嚴格第三短路的候選路記為:S2.

證明 定理1已經(jīng)證明了算法1得到的結(jié)果S中的最小者是次短路，而S中的第二小者長度一定比次短路更長，所以S2是嚴格第三短路的候選路.

求嚴格第三短路的基本思想:首先，求從起點s經(jīng)過一個固定頂點x∈V－{t}到終點t的最短路，其中最小的是次短路，而第二小者是嚴格第三短路的候選路之一.其次，求起點s經(jīng)過2個固定頂點x，y∈V－{t}到終點t的最短路，最小者也是嚴格第三短路的候選路之一.其中:這2條嚴格第三短路候選路都是利用最小費用整數(shù)流方法來求.最后，比較這兩條候選路較小者就是嚴格第三短路.

先介紹求嚴格第三短路第2條候選路算法.

稱該算法為:Second candidate path algorithm，簡稱SCPA.詳細算法如下.

算法2:SCPA

輸入:無向賦權(quán)圖 G=(V，E;w;s，t)，其中 s，t∈ V，w:E → R+.

輸出:求出s到t含2條反常路的嚴格第三短路候選路或說明無含有2條反常路的嚴格第三短路候選路.

Step 1:利用Dijkstra算法求出圖G所有s－t最短路，然后構(gòu)造最短路網(wǎng)絡(luò) DG=(Vst，Ast;w;s，t);

Step 2:置L=?;

Step 3:對于所有x，y∈V－{t}:

在圖G=(V，E;w;s，t)中求出x到y(tǒng)的最短路Pxy;

刪除頂點x，y在最短路網(wǎng)絡(luò)DG中所有的出弧對應于原圖G中的邊，得到一個新的無向圖G″=(V，E″;w;s，t);

利用最小費用整數(shù)流方法在新圖G″=(V，E″;w;s，t)中求出從s到x和y到t的2條點不交的最短路Psx和Pyt;

Step 4:如果(L=?)則，含2條反常路的嚴格第三短路候選路不存在;否則輸出L中的最小者.

定理3 算法2得到的結(jié)果L中的最小者L1對應的路一定是簡單路.

證明 反證法，假設(shè)L中的最小者L1對應的路不是簡單路，即含有圈.則路含圈可以分為3種情況:

1)s到x的最短路與x到y(tǒng)的最短路有交點，記距離s最近的交點為x';則用x'替換x可以求得1條含有2條反常路的最短路且w()＜w，這與路是最小者矛盾;

2)y到t的最短路與x到y(tǒng)的最短路有交點，記距離t最近的交點為y';則用y'替換y可以求得1條含有2條反常路的最短路且w()＜w)，這與路是最小者矛盾;

3)s到x的最短路以及y到t的最短路都與x到y(tǒng)的最短路有交點，記距離s最近的交點為x″，距離t最近的交點為y″;則用x″和y″替換x和y可以求得1條含有2條反常路的最短路且w)＜w()，這與路是最小者矛盾;

定理3 算法2可以求出嚴格第三短路的第2條候選路，其時間復雜性為O(n4).

證明 算法2第1步求出從s到t最短路網(wǎng)絡(luò)DG=(Vst，Ast;w;s，t)，顯然最短路網(wǎng)絡(luò)上所有的路都是最短路.對任意2個頂點x，y∈V－{t}For循環(huán)，先求出從x到y(tǒng)的最短路Pxy，然后刪除頂點x，y在網(wǎng)絡(luò)DG中所有的出弧對應于原圖G中的邊，得到一個新的無向圖G″=(V，E″;w;s，t)，利用最小費用整數(shù)流方法在新圖G″=(V，E″;w;s，t)中求出從s到x和y到t的2條點不交的最短路Psx和Pyt，最后將三條路合并得到1條從起點s經(jīng)過2個固定頂點x，y到終點t的最短路，這條路恰好含有2條反常路.所以算法2求得的結(jié)果L中的最小者L1是含有2條反常路的嚴格第三短路候選路.

時間復雜度分析:對任意2個頂點x，y∈V－{t}For語句循環(huán)，時間復雜性為O(n2)，循環(huán)內(nèi)求x到y(tǒng)的最短路Pxy及用最小費用整數(shù)流方法在新圖G″=(V，E″;w;s，t)中求出從 s經(jīng)過2個頂點x，y到t的最短路Psxyt的時間復雜性都是O(n2)，故算法2的時間復雜性為O(n4).

最后給出求嚴格第三短路的算法.

稱該算法為:Strictlythirdshortestpath algorithm，簡稱STSPA.詳細算法如下:

算法3 STSPA

輸入:無向賦權(quán)圖 G=(V，E;w;s，t)，其中 s，t∈ V，w:E → R+.

輸出:求出s到t的嚴格第三短路或說明無嚴格第三短路.

Step 1:置T=?;

Step 2:調(diào)用算法1，輸出S中的第二小者S2;

Step 3:T=T∪{S2};

Step 4:調(diào)用算法2，輸出L中的最小者L1;

Step 5:T=T∪{L1};

Step 6:如果(T=?)則嚴格第三短路不存在;否則輸出T中的較小者.

定理4 算法3可以解決嚴格第三短路問題，其時間復雜性為O(n4).

證明 算法3將嚴格第三短路的2條候選路放入集合T，故T中較小者就是嚴格第三短路的長度.所以算法3可以解決嚴格第三短路問題.

時間復雜性分析:算法1的時間復雜性為O(n3)，算法2的時間復雜性為O(n4).所以算法3的時間復雜性為O(n4).

3 結(jié)語

在嚴格第三短路這個問題的研究中還存在如下2個問題:①本文解決了正權(quán)重無向圖中嚴格第三短路問題，但算法的時間復雜性較高.是否能設(shè)計出時間復雜性更低的多項式時間算法.②對于非負權(quán)重無向圖中嚴格第三短路問題，目前還沒有相關(guān)的算法.是否能設(shè)計一個多項式時間算法來解決該問題.在今后的學習研究中將著力解決這2個的問題.

［1］LALGUDI K N，PAPAEFTHYMIOU M C.Computing strictly － second shortest paths［J］.Information processing letters，1997，63(4):177 －181.

［2］KRASIKOV I，NOBLE S D.Finding next－to－shortest paths in a graph［J］.Information Processing Letters，2004，92(3):117－119.

［3］LI S，SUN G，CHEN G.Improved algorithm for finding next－to－shortest paths［J］.Information Processing Letters，2006，99(5):192 －194.

［4］KAO K H，CHANG J M，WANG Y L，et al.A quadratic algorithm for finding next－to－shortest paths in graphs［J］.Algorithmica，2011，61(2):402－418.

［5］WU B Y.A simpler and more efficient algorithm for the next－to－shortest path problem［M］//Combinatorial Optimization and Applications.Berlin Heidelberg:Springer 2010:219－227.

［6］ZHANG C，NAGAMOCHI H.The Next－to－Shortest Path in Undirected Graphs with Nonnegative Weights［C］//CATS.2012:13－20.

［7］WU B Y，GUO J L，WANG Y L.A linear time algorithm for the next－to－shortest path problem on undirected graphs with nonnegative edge lengths［J］.arXiv preprint arXiv:1203.5235，2012.

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

［9］KATOH N，IBARAKI T，MINE H.An efficient algorithm for k shortest simple paths［J］.Networks，1982，12(4):411－427.