最短路(算法藝術(shù))

1、算法藝術(shù)與信息學(xué)競賽第二版教學(xué)幻燈片圖論算法第七講 最短路相關(guān)問題(劉汝佳)內(nèi)容介紹一、SSSP問題二、dijkstra算法三、Bellman-ford算法四、APSP問題五、floyd-warshall算法六、每兩點(diǎn)間的k短路七、Johnson算法八、兩點(diǎn)間k短路的偏離算法九、兩點(diǎn)間k短路的MPS算法一、單源最短路問題一、單源最短路問題(SSSP)SSSP 有向或無向，加權(quán)連通圖 求s到所有點(diǎn)的最短路 最短路可能不存在 若存在，所有涉及到的邊組成一棵樹(最優(yōu)性原理)SSSP 最優(yōu)性原理 區(qū)別 最短路樹 最小生成樹一般SSSP算法 臨時最短路 存在此路，即真實(shí)的最短路長度不大于此路長度 但是有

2、可能有更短的，所以此路長度只是一個上界 給定起點(diǎn)s，對于每個頂點(diǎn)v，定義 dist(v)為臨時最短路s-v的長度 pred(v)為臨時最短路s-v中v的前驅(qū) 由pred(v)可以完全定義一棵最短路樹 初始化 dist(s)=0, pred(s)=NULL 所有其他dist(v)為無窮，pred(v)=NULL一般SSSP算法 一條邊(u,v)被稱為緊的(tense) 如果dist(u)+w(u,v)dist(v) 含義：目前的臨時最短路長度dist(v)可以改進(jìn) 可以松弛：dist(v)=dist(u)+w(u,v), pred(v)=u 結(jié)論 存在緊的邊，一定沒有正確的求出最短路樹 不存在緊

3、的邊，一定正確的求出最短路樹一般SSSP算法 (u,v)被稱為緊的：dist(u)+w(u,v)dist(v) 不存在緊邊，一定求出最短路樹 即由pred表示出的路徑上所有邊權(quán)和等于dist(v)（歸納于松弛的次數(shù)） 結(jié)束時對s到v的任意路sv，dist(v)=w(sv) 歸納于sv所含邊數(shù)，假設(shè)su-v（u=pred(v)） dist(u)=w(su)，兩邊加w(u,v)得： dist(u)+w(u,v)=w(sv)。因?yàn)闊o緊邊，所以 dist(v)=dist(u)+w(u,v)=w(sv)一般SSSP算法 剛才已經(jīng)證明 結(jié)束時dist(v)和pred(v)相容 若算法結(jié)束，則結(jié)果正確 算法

4、何時能結(jié)束呢？ 含負(fù)圈（能到達(dá)的），則永不結(jié)束，因?yàn)樵谝淮嗡沙谝院?，?fù)圈上一定有緊邊（反證） 不含負(fù)圈，則一定結(jié)束，因?yàn)橐礈p少一個無窮dist值，要么讓所有有限dist值之和至少減少一個“不太小的正值”。一般SSSP算法 一般算法 可以以任意順序?qū)ふ揖o邊并松弛 收斂時間沒有保障 解決方案：把結(jié)點(diǎn)放到bag中，每次取一個出來檢查 特殊bag：dijkstra(heap), bellman-ford(queue)二、二、dijkstra算法算法SSSP: dijkstra 使用heap?？梢宰C明：按dist從小到大計算出應(yīng)用路的最小公倍數(shù) 給出一個帶權(quán)無向圖G 邊權(quán)為11 000的整數(shù) 對于v0

5、到v1的任意一條簡單路p 定義s(p)為p上所有邊權(quán)的最大公約數(shù) 考慮v0到v1的所有路p1,p2, 求所有s(p1),s(p2),的最小公倍數(shù) 模型？最短路？ 路徑長度定義不再是權(quán)和，而是 dijkstra算法還能用嗎？三、三、bellman-ford算法算法SSSP：權(quán)任意的情形 最短路有可能不存在！ 什么時候不存在？ 有負(fù)圈！ 標(biāo)號設(shè)定標(biāo)號修正 仍然有標(biāo)號di = k 但是標(biāo)號di無法固定，只能不斷更新 新算法SSSP：bellman-ford算法 如有最短路，則每個頂點(diǎn)最多經(jīng)過一次即： 這條路不超過n-1條邊 依次考慮1,2,3n-1條邊的情形, k-1次迭代后： 長度為k的路由不超過

6、1,2,k-1的路增加一條邊得到：for k:=1 to n-1 do 松弛每條邊 核心：松弛操作 時間復(fù)雜度：O(vm)，v為迭代次數(shù)(v=n-1) 加速：用dijkstra得到初始distSSSP: Bellman-ford 用queue做bag應(yīng)用出納員的雇傭 24小時營業(yè)的超市需要一批出納員來滿足它的需求, 每天的不同時段需要不同數(shù)目的出納員 給出每小時需要出納員的最少數(shù)R0, , R23 R(0)表示從午夜到午夜1:00需要出納員的最少數(shù)目， R(1)表示上午1:00到2:00之間需要的 每一天，這些數(shù)據(jù)都是相同的 有N人申請這項(xiàng)工作, 如果第i個申請者被錄用，他將從ti刻開始連續(xù)工

7、作8小時 計算為滿足上述限制需要雇傭的最少出納員數(shù)目 i時刻可以有比對應(yīng)的Ri更多的出納員在工作分析 前i(0=i=23)小時的雇傭總數(shù)：si 規(guī)定s-1 = 0 第i(0=i=23)小時需要的出納員：ri 第i(0=i=23)小時申請的人數(shù)：ti 則有不等式 0 = si si-1 j時 si sj = ri I = ri sum sum已知道時構(gòu)圖G(-1,0,1,23) Sa sb = c：有向邊(b, a, c) -1為起點(diǎn)的單源最長路 最長路存在且s23 = sum，有解 枚舉sum！二分？四、每對結(jié)點(diǎn)最短路四、每對結(jié)點(diǎn)最短路(APSP)APSP基本想法 考慮從每個點(diǎn)出發(fā)做一次SSS

8、P的時間效率 權(quán)任意時n次bellman-ford是O(n2m), 稠密圖時O(n4) 思路: 動態(tài)規(guī)劃基本動態(tài)規(guī)劃算法 di,u,v為u到v最多不超過i條邊的最短路長 算法一： di,u,v=mindi-1,u,x+w(x,v)，x遍歷v的鄰居 時間復(fù)雜度：O(V2E) k短路：di,u,v=sumdi-1,u,x+w(x,v) 算法二: di,u,v為u到v最多不超過2i條邊的最短路長, 則最短路可以在O(n3logn)算出五、五、Floyd-warshall算法算法狀態(tài)設(shè)計 設(shè)di,j,k是 在只允許經(jīng)過結(jié)點(diǎn)1k的情況下 i到j(luò)的最短路長度 則它有兩種情況（想一想，為什么）： 最短路經(jīng)過

9、點(diǎn)k，di,j,k=di,k,k-1+dk,j,k-1 最短路不經(jīng)過點(diǎn)k，di,j,k=di,j,k-1 綜合起來: di,j,k=mindi,k,k-1+dk,j,k-1,di,j,k-1 邊界條件: di,j,0=w(i,j)（不存在的邊權(quán)為） floyd-warshall算法 把k放外層循環(huán)，可以節(jié)省內(nèi)存 對于每個k，計算每兩點(diǎn)的目前最短路 代碼(需記憶)for k:=1 to n dofor i:=1 to n do for j:=1 to n do if (di,k)and(dk,j) and(di,k+dk,jdi,j) then di,j:=di,k+dk,j 時間復(fù)雜度：O(n

10、3)六、每兩點(diǎn)間的六、每兩點(diǎn)間的k短路短路修改的floyd-warshall算法 設(shè)di,j,L為ij,只經(jīng)過1L的前k短路長度(向量) di,j,L =Mindi,j,L-1, di,L,L-1 + dL,L,L-1* + dL,j,L-1 兩個k維向量A, B的運(yùn)算 MinA, B: A和B共2k個數(shù)取前k個. O(K) A + B: Ai+Bj共k2個和取前k個. O(KlogK) A* = Min0, A, 2A, 3A, . O(K2logK) 計算dL,L,L-1*的時間復(fù)雜度: O(nK2logK) 計算狀態(tài)dI,j,L: O(2KlogK+K)=O(KlogK) 總時間復(fù)雜度:

11、 O(nK2logK+KlogKn3)七、七、Johnson算法算法Johnson算法 稀疏圖中, floyd算法時間效率并不理想 重加權(quán) 目的：權(quán)變非負(fù)后用dijkstra 每條邊等量增加可能改變最短路樹 例子：全部增加2的情況（右圖） Johnson算法 目標(biāo)：找到c(v) 重加權(quán)公式：w(u,v)=c(u)+w(u,v)-c(v) 加權(quán)后最短路樹不變 因?yàn)閷τ谌我饴穝u, w(su)=w(su)+c(s)-c(u)Johnson算法 如何設(shè)計cost(v)函數(shù)，使所有新權(quán)非負(fù)？ 增加人工節(jié)點(diǎn)s，直接到所有點(diǎn)，權(quán)均為0 以s為起點(diǎn)運(yùn)行bellman-ford，求出dist(v) 如果有負(fù)權(quán)

12、圈，退出，否則 對于原圖點(diǎn)v，c(v)=dist(v) 為什么w(u,v)=dist(u)+w(u,v)-dist(v)非負(fù)？ 如果不是，dist(u)+w(u,v)dist(v) 這意味著(u,v)是緊的！Johnson算法 時間復(fù)雜度分析 Bellman-ford：O(VE) 運(yùn)行n次dijkstra：O(VE+VElogV)八、兩點(diǎn)間八、兩點(diǎn)間k短路的偏離算法短路的偏離算法偏離算法 偏離算法(deviation algorithms)不需要滿足最優(yōu)性原理，所以它的適用范圍更為廣泛。在本專題中，我們用它來解決K最短路問題。即求長度最小的K條路徑，長度相等的路徑可以按任意順序排列。 為了解釋

13、這個算法的思想，我們先引入偽樹(pseudo-tree)的概念。偽樹 偽樹是通過依次加入一對給定節(jié)點(diǎn)(s,t)之間的K最短路p1,p2,pK建立的。通常記TK為K最短路形成的偽樹。 加入一條偽樹的過程分為兩步 當(dāng)路徑上的邊在樹中出現(xiàn)的時候順著樹邊走 一旦發(fā)現(xiàn)路徑上的邊不在樹中時，把剩下的路徑加到樹中偽樹舉例 如下圖所示，往空樹中加入三條路徑1,4,6, 1,4,1,6, 1,6，每一步形成的樹如下圖所示。注意，樹中可以有重復(fù)節(jié)點(diǎn)。偏離節(jié)點(diǎn) 每次加入新路徑的時候，第一條不在原樹中的弧叫做偏離弧。最后一個在原樹中的節(jié)點(diǎn)叫做偏離節(jié)點(diǎn)(deviation vertex)，即“分岔點(diǎn)”。往樹Tk加入新路

14、徑時的偏離節(jié)點(diǎn)通常用vk表示，vk后面的路徑叫做偏離路徑。由于在加入路徑的時候，事實(shí)上只有偏離路徑才是樹新增加的東西，所以它上面的點(diǎn)是后面將要介紹的算法最關(guān)心的。K短路問題 下面考慮k短路問題。我們用集合X來保存計算當(dāng)前第k大路徑可能會用到的路徑，初始時X為最短路徑p1。每次我們從候選集合X中選一條作為pk,并往X中填加新元素構(gòu)成pk+1的候選集合。根據(jù)剛才的討論，求求k短短路分為兩個步驟路分為兩個步驟：選偏離節(jié)點(diǎn)找偏離路徑，則新的最短路由最短路樹Tk的根到偏離節(jié)點(diǎn)vk的路與偏離路徑連接而成連接而成。 K最短路 定理：定理：用Tk表示前k條最短路形成的偽樹，則Tk+1的偏離節(jié)點(diǎn)vk+1的偏離路

15、徑是滿足“第一條弧不是在Tk中以vk+1為起點(diǎn)的弧”的所有路徑中最小的。 證明：證明：如果允許第一條弧是Tk中以vk+1為起點(diǎn)的弧，那么最小的路徑就是Tk中已經(jīng)存在的路徑。在排除了選擇Tk中路徑的前提下，把最小路徑作為偏離路徑之后理所當(dāng)然的應(yīng)該得到下一條最短路。 基本偏離算法 根據(jù)剛才的定理，我們只需要枚舉新偏離節(jié)點(diǎn)vk+1和第一條弧終點(diǎn)v(保證v不在Tk中)，則偏離路徑就是v到t的最短路。另外，在枚舉新的偏離節(jié)點(diǎn)的時候只需要從上一個偏離節(jié)點(diǎn)vk的偏離路徑上枚舉，因?yàn)橐云渌旤c(diǎn)為偏離節(jié)點(diǎn)的路徑早就被考慮過了。 讓A(v)為以v開始的弧集合，Ak(v)為Tk中以v開始的弧集合，p*(x,t)表示

16、在Tt*中x到t的最短路徑。預(yù)處理的時候，我們還需要先求出Tt*，即所有節(jié)點(diǎn)到t的最短路樹。 先求最短路，以后每求一條的復(fù)雜度為O(m)算法的預(yù)處理 左圖為一個網(wǎng)絡(luò), 右圖為Tt*算法運(yùn)行前三步九、兩點(diǎn)間九、兩點(diǎn)間k短路的短路的MPS算法算法簡化費(fèi)用 在剛才的算法中，選最優(yōu)偏離節(jié)點(diǎn)的“關(guān)鍵步驟”耗時O(m)。要改進(jìn)這個算法，我們需要優(yōu)化這個瓶頸操作。為此，我們介紹簡化費(fèi)用簡化費(fèi)用(reduced cost)的概念。讓Tt為一棵指向t的有向樹，則Tt上任意節(jié)點(diǎn)i到t的路徑唯一，我們用d(i)表示這條唯一路徑的權(quán)和，則我們用：c(i,j)=d(j)-d(i)+c(i,j) 表示弧(i,j)在樹Tt

17、的簡化費(fèi)用簡化費(fèi)用計算舉例簡化費(fèi)用定理 關(guān)于簡化費(fèi)用，我們有如下重要定理(請讀者根據(jù)定義證明這個定理)： 定理：定理：設(shè)其中c(p)表示路徑的原始費(fèi)用和，c(p)表示路徑上所有弧的簡化費(fèi)用和。 c(p) = c(q) 當(dāng)且僅當(dāng)c(p) = c(q) c(p) c(q) 當(dāng)且僅當(dāng)c(p) =0；其中Tt*的弧(i,j)滿足c(i,j)=0。 有了這個定理，我們再來看剛才的算法。算法的關(guān)鍵步驟需要考查以v開始的所有弧，因此最壞情況下一共需要考察O(m)條弧。 根據(jù)這兩個定理，我們讓c(v,x) + c(p*(x,t)最小，等價于讓c(v,x) + c(p*(x,t)最小。由于p*(x,t)上的弧都在Tt*中，因此c(p*(x,