第K條最短路的算法介紹

1,、前言
大家現(xiàn)在已經(jīng)知道了如何求單源點最短路徑問題,，但在實際應用中，有時候需要除了需要知道最短路徑外,，尚需求解次最短路或第三最短路,，即要知道多條最短路，并排出其長度增加的順序,。如在通信網(wǎng)絡中,，有時候某條線路中斷，則需要找一個替代的方案,，這就需要找到幾條最短路以備不時之需,。這樣一類多條最短路問題即稱為K最短路問題。
2,、二重掃除算法
求解第K條最短路主要應用的是二重掃除算法（double-sweep algorithm）,，有些地方也叫雙向掃除算法。
2.1 概念介紹
在介紹這個具體算法之前,，我們要先來看幾個概念,，這幾個概念在后面具體的算法介紹時需要用到。先看第一個概念,，是兩類推廣運算,。
? 兩類運算：推廣的求極小值運算與推廣的加法運算
令Rk表示向量（d1，d2,，…,，dk）的集合，di<dj,，i=1,，2，…,，k-1,；j=2,，…，k,。如（-5,，-2，0,，6,，7）∈R5。設A=（a1,，a2,，…，ak）,，B=（b1,，b2，…,，bk）是Rk的兩個元素,。
Note：Rk中的各個向量的元素必須是①按遞增順序排列；②取不同的數(shù)值（除∞之外）,。此外,，運算的結(jié)果A＋B及A×B也要滿足此要求。
定義A與B的推廣的求極小值的運算為：
A＋B＝mink{ai,，bi：i＝1,，2，…,，k},，其中mink{X}表示集合X中前k個最小的元素。
定義A與B的推廣的加法為：
A×B＝mink{ai＋bi：i＝1,，2,，…，k},，即求出A與B的元素分別相加的前K個最小的和,。
Exp1：A＝（1，3,，4,，8）B＝（3，5,，7,，16）則可知：
A＋B＝min4{1，3,，4,，8,，3，5,，7,，16}＝（1，3,，4,，5）
A×B＝min4{1＋3，1＋5,，1＋7,，1＋16，3＋3,，3＋5,，…,，8＋16}＝{4,，6，7,，8}
Exp2：A＝（－4,，0，7,，∞）或B＝（3,，4，∞,，∞）是可接受的,；
而A＝（－4，3,，3,，9）與B＝（－9，0,，∞,，9）不可接受。
下面講一下前向掃除和后向掃除兩個概念：
? 前向掃除與后向掃除
雙重掃除算法中的每次迭代由兩個過程組成：
前向掃除 按照頂點號的遞增順序（即j＝1,，2,，…，p）,，通過連續(xù)地檢查所有與j頂點相鄰的前一個頂點i（i<j）,，確定從源頂點到j頂點的K最短路徑是否可能通過這個相鄰頂點，若這樣的路存在,，則可取新的估計值,，并用于進一步的迭代,。
后向掃除 執(zhí)行類似的算法，其過程是按照頂點號遞減的序列（即,，j＝p,，p-1，…,，1）,，并且只檢查與j頂點相鄰的后一個頂點（按網(wǎng)絡的方向），即i>j,。

2.2 算法思想介紹
下面我們來看一下雙重掃除算法,。這個算法的思想其實還是比較簡單的，就是實現(xiàn)起來比較復雜,，要涉及到兩種迭代及矩陣運算,，當然還包括前面提及的推廣的求極小值運算與推廣的加法運算。
它的思想是：從原始點到頂點j的第K條最短路是由原始點到頂點i（i是j的相鄰頂點,，最短路從i指向j）的第K條最短路加上i到j的一段弧,。即把與i關(guān)聯(lián)的弧作為K最短路的最后一段掃視一遍，無論是前向運算或是后向運算,，都需要從L或U中取出dij元素參加運算,，dij元素在運算中作為K最短路的最后一段弧被挑選，并且以前一次運算的向量為基礎,，取相應的中間點,。

2.3 算法過程
在雙重掃除算法過程中，主要反復執(zhí)行加法和求極小值的運算,。
對于每個有向圖,，我們先對它進行分析，可以用向量 表示從i到j的k條不同最短路的長度,。而D0是以 為元素的矩陣,。注意，它的元素是 ,，這表示這個矩陣中的每個元素都是一個向量,，每個向量表示的是從i到j的k條最短路，即是k維向量,，如若遇到不足k維的,，則以∞補全。如圖1,，若k為3,，則它的D0矩陣可以表示為：

                 圖1
其實從這個矩陣中我們可以看到各個頂點間是否有有向邊相連，同時還可以知道該有向邊的權(quán)值。因為運算中找最短路徑,，實際上就是計算各條通路的邊的權(quán)值和再加以比較,，從而得到最小值或次小值。
由D0我們可以得到上三角矩陣U和下三角矩陣L如下：


算法的具體思路如下：
⑴ 先設個向量,，對原始點到各頂點的最短路長度進行估計,。要注意各個值要不小于相應的最優(yōu)值。除原始點到其本身的最短路用0估計外,，其余都可以用∞來估計,。即為：   
顯然， 是個元素值為向量的向量,。其中向量 表示從i到j的k條最短的不同路的長度,。
如圖1中，令d10＝（（0,，∞,，∞），（∞,，∞,，∞），（∞,，∞,，∞）,，（∞,，∞，∞））
⑵ 然后根據(jù)原來的估計值,，可以根據(jù)前向和后向掃除計算出新的估計值：
   后向掃除：d1(2r+1)＝d1(2r+1)L＋d1(2r)
   前向掃除：d1(2r+2)＝d1(2r+2)U＋d1(2r＋1) （r＝0,，1，2,，…）
其中矩陣運算中的加法和乘法分別指前面提及的推廣的求極小值和推廣的加法運算,。令 ，可將后向掃除公式分解為：
   由上式可見在求 時,， 本身也參與了運算,，但是，觀察L,，我們可知L的最后一列元素全為 ,，由于 ，而 ,，所以 ,；而求 時，只需知道 ，不需知道其它幾項,；由此一步步往前推,，我們可以將整個 完整地計算出來，因此稱其為后向掃除,。如下,，是 向量中的各個元素的計算式：
即 

……
同理：我們可以將前向掃除的計算公式進行分解，如下：
   在計算 時也要用到 其本身,，但根據(jù)U的特點,，我們可以發(fā)現(xiàn)先可以計算出 ，然后可以依次計算出 ,， ,，……，這與上面的后向掃除類似,，只是這里我們要先從前面開始計算,，因此稱其為前向掃除。具體的 的各個元素的計算式與上面后向掃除類似,，這里就不一一寫出了,。
如圖1，可計算d141＝（∞,，∞,，∞），d131＝（∞,，∞,，∞），
d121＝（∞,，∞,，∞），d111＝（0,，∞,，∞）；（后向）
（前向）d112＝（0,，∞,，∞），
d122＝（∞,，∞,，∞）+（0，∞,，∞）×（2,，∞，∞）＝（2，∞,，∞）
d132＝（∞,，∞，∞）+（0,，∞,，∞）×（5，∞,，∞）＝（5,，∞，∞）
d142＝（∞,，∞,，∞）+（2，∞,，∞）×（3,，∞，∞）
+（5,，∞,，∞）×（3，∞,，∞）＝（5,，8，∞）,；
（后向）d143＝（5,，8，∞）,，
d133＝（5,，∞，∞）
d123＝（2,，∞，∞）+（5,，∞,，∞）×（2，∞,，∞）＝（2,，7，∞）
d112＝（0,，∞,，∞）；
（前向）d113＝（0，∞,，∞）,，
d123＝（2，7,，∞）+（0,，∞，∞）×（2,，∞,，∞）＝（2，7,，∞）
d133＝（5,，∞，∞）+（0,，∞,，∞）×（5，∞,，∞）＝（5,，∞，∞）
d143＝（5,，8,，∞）+（2，7,，∞）×（3,，∞，∞）
+（5,，∞,，∞）×（3，∞,，∞）＝（5,，8，10）,；
（后向）d144＝（5,，8，10）,，
d134＝（5,，∞，∞）
d124＝（2,，7,，∞）+（5,，∞，∞）×（2,，∞,，∞）＝（2，7,，∞）
d114＝（0,，∞，∞）,；
顯然,，第三第四次迭代后，運算結(jié)果相同,，從而可得：
d1＝（（0,，∞，∞）,，（2,，7，∞）,，（5,，∞，∞）,，（5,，8，10））

⑶ 當 與 的每個分量都相等時,，算法中止,。
2.4 路徑的確定
K最短路長度求得以后，我們要確定相應的路徑,，這時我們可以采用追蹤的方法,。設需要知道從源頂點到i頂點的第m最短路長的路徑，我們可以令 為該路的路長,，并且令j表示與i相鄰的頂點,，則

這里 是弧ji的長度， 是對應與頂點j的t最短路長度,，t≤m,。