算法藝術(shù)和信息學(xué)競賽教學(xué)-最短路ppt課件

1、算法藝術(shù)與信息學(xué)競賽教學(xué)幻燈片算法圖論第六講 最短路聲明 本系列教學(xué)幻燈片屬于劉汝佳、黃亮著配套幻燈片 本幻燈片可從本書上免費(fèi)下載，即使您并未購買本書. 若作為教學(xué)使用，歡迎和作者聯(lián)系以取得技術(shù)支持，也歡迎提供有不同針對性的修改版本，方便更多人使用 有任何意見，歡迎在上評論 Blog地址：artofalgo.china內(nèi)容介紹一、SSSP問題二、dijkstra算法三、Bellman-ford算法四、差分約束系統(tǒng)五、Gabow的變尺度算法六、APSP問題七、floyd-warshall算法八、Johnson算法一、單源最短路問題一、單源最短路問題(SSSP)SSSP 給加權(quán)圖和一個起點(diǎn)s, 求

2、s到所有點(diǎn)的最短路(邊權(quán)和最小的路徑) 最短路有環(huán)嗎 正環(huán): 何必呢, 刪除環(huán)則得到更短路 負(fù)環(huán): 無最短路, 因為可以沿負(fù)環(huán)兜圈子最優(yōu)性原理 最優(yōu)性原理: 若最短路uv經(jīng)過中間結(jié)點(diǎn)w, 則uw和wv的路徑分別是u到w和w到v的最短路. 意義: 貪婪、動態(tài)規(guī)劃最短路的表示 最短路的表示 s到所有點(diǎn)的最短路不需要分別表示 最短路樹: 到每個點(diǎn)都沿著樹上的唯一路徑走 實(shí)際代碼: 記錄每個點(diǎn)的父親predu即可 輸出最短路: 從終點(diǎn)沿著predu遞推回起點(diǎn)為什么單源最短路形成樹? 考慮下圖 如果uz的路只取一條即可最短路樹和最小生成樹一般SSSP算法 臨時最短路 存在此路，即真實(shí)的最短路長度不大于此

3、路長度 但是有可能有更短的，所以此路長度只是一個上界 給定起點(diǎn)s，對于每個頂點(diǎn)v，定義 dist(v)為臨時最短路樹中s-v的長度 pred(v)為臨時最短路樹中s-v中v的前驅(qū) 初始化: dist(s)=0, pred(s)=NULL, 初始化: 所有其他dist(v)為無窮，pred(v)=NULL dist(v)稱為點(diǎn)v的標(biāo)號(label), 它是最短路的上界 基本想法: 讓標(biāo)號不斷趨近, 最終達(dá)到最短路一般SSSP算法 什么樣的標(biāo)號明顯可以改進(jìn)(趨近最短路)? 一條邊(u,v)被稱為緊的(tense), 如果dist(u)+w(u,v)dist(v) 可以松弛：dist(v)=dist

4、(u)+w(u,v), pred(v)=u 結(jié)論 存在緊的邊，一定沒有正確的求出最短路樹 不存在緊的邊，一定正確的求出最短路樹一般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-vu=pred(v)） dist(u)=w(su)，兩邊加w(u,v)得： dist(u)+w(u,v)=w(sv)。因為無緊邊，所以 dist(v)=dist(u)+w(u,v)=w(sv

5、)一般SSSP算法的結(jié)束條件 剛才已經(jīng)證明 結(jié)束時dist(v)和pred(v)相容 若算法結(jié)束，則結(jié)果正確 算法何時能結(jié)束呢？ 含負(fù)圈能到達(dá)的），則永不結(jié)束，因為在一次松弛以后，負(fù)圈上一定有緊邊反證） 不含負(fù)圈，則一定結(jié)束，因為要么減少一個無窮dist值，要么讓所有有限dist值之和至少減少一個“不太小的正值”。一般SSSP算法 一般算法 可以以任意順序?qū)ふ揖o邊并松弛 收斂時間沒有保障 解決方案：把結(jié)點(diǎn)放到bag中，每次取一個出來檢查 特殊bag：dijkstra(heap), bellman-ford(queue)二、二、dijkstra算法算法Dijkstra算法 E.W.Dijkstr

6、a. A note on two problems in connection with graphs. Num.Math.,1:269-271, 1959 原始是O(n2), 可以用各種形式的堆加速Dijkstra算法 標(biāo)號設(shè)定算法: 每次dist(v)最小的一個恰好等于它的最短值，予以固定 正確性證明 (注意為什么需要權(quán)非負(fù))時間復(fù)雜度 Dijkstra算法使用了一個優(yōu)先隊列 INSERT (line 3), 每個結(jié)點(diǎn)一次 EXTRACT-MIN, 每個結(jié)點(diǎn)一次 DECREASE-KEY (line 8, 在RELAX過程中), 一共|E|次 直接實(shí)現(xiàn): O(V2) 二項堆: O(Elog

7、V) Fibonacci堆: O(E+VlogV)練習(xí) 給有向加權(quán)圖, 邊權(quán)值為0,1之間的實(shí)數(shù), 代表邊的可靠性(各邊的可靠性獨(dú)立). 找出s到t的路徑中可靠性最大的一條(總可靠性等于每條邊可靠性之乘積) 假設(shè)邊權(quán)值范圍為1, 2, 3, , W 把每條邊拆成w(u,v)條邊串聯(lián), 然后BFS 直接修改dijkstra得到O(VW+E)的算法 優(yōu)化到O(V+E)lgW) 從s出發(fā)的邊有可能有負(fù)邊(但無負(fù)環(huán)), 其他邊均為正權(quán). Dijkstra算法能得到最優(yōu)解嗎?運(yùn)用路的最小公倍數(shù) 給出一個帶權(quán)無向圖G 邊權(quán)為11 000的整數(shù) 對于v0到v1的任意一條簡單路p, 定義s(p)為p上所有邊權(quán)

8、的最大公約數(shù) 考慮v0到v1的所有路p1,p2, 求所有s(p1),s(p2),的最小公倍數(shù)三、三、bellman-ford算法算法SSSP：bellman-ford算法 Ford 1956, Bellman 1958, Moore 1959. 如有最短路，則每個頂點(diǎn)最多經(jīng)過一次 這條路不超過n-1條邊 長度為k的路由長度為k-1的路增加一條邊得到 由最優(yōu)性原理, 只考慮長度為1k-1的最短路 算法梗概: 每次迭代依次松弛每條邊 時間復(fù)雜度 O(Dm)，v為迭代次數(shù)(v=n-1) 完全圖邊權(quán)在0, 1中均勻分布, 很大概率D=O(log2n) 若某次迭代沒進(jìn)行成功松弛, 可立即停止 可用dij

9、kstra得到初始distYen的修改算法 把G中的邊(vi, vj)分為兩類: f邊: i j 每次迭代先從v1遍歷到v|V|, 松弛f邊, 再從v|V|遍歷回v1, 松弛b邊 則最多只需要|V|/2次(取上整)迭代, 但不降低時間復(fù)雜度練習(xí) 給出可能有負(fù)權(quán)的有向加權(quán)圖, 對于每個點(diǎn)v, 在O(VE)時間求出離v最近點(diǎn)到它的距離 給出有負(fù)圈的圖, 在O(VE)時間內(nèi)輸出圈上的結(jié)點(diǎn)列表運(yùn)用套匯四、差分約束系統(tǒng)四、差分約束系統(tǒng)差分約束系統(tǒng) 線性規(guī)劃(linear programming, LP): 給m*n矩陣A、m維向量b和n維向量c, 求出x為向量使得Ax=b, 且sumcixi最小 可行性

10、問題(feasibility problem): 只需要任意找出一組滿足Ax=b的解向量x 差分約束系統(tǒng)(system of difference constraints): A的每行恰好一個1和一個-1, 其他元素都是0. 相當(dāng)于關(guān)于n個變量的m個差分約束, 每個約束都形如xj-xi=bk, 其中1=i,j=n, 1=k=m.差分約束系統(tǒng)舉例 左邊的可行性問題等價于右邊的差分約束系統(tǒng)基本思路 定理: 給定差分約束系統(tǒng)的一組解, 給每個變量加上一個常數(shù)d, 將得到另外一組解 約束圖: 結(jié)點(diǎn)是變量, 一個約束對應(yīng)一條弧, 若有弧(u, v), 則得到xu后, 有xv = xu + w(u,v)算

11、法 定理: 如果約束圖沒有負(fù)圈, 則可取xu為起點(diǎn)v0到u的最短路長; 若約束圖有負(fù)圈, 差分約束系統(tǒng)無解. 正確性證明 無負(fù)圈: 由松弛條件可證明每個約束得到滿足 有負(fù)圈: 把負(fù)圈上的約束條件疊加將得到一個矛盾不等式 算法步驟 構(gòu)圖, 得到n+1個結(jié)點(diǎn)m+n條邊 運(yùn)行bellman-ford, 時間 O(n2+mn)練習(xí) 如何修改bellman-ford算法, 使得將它應(yīng)用在差分約束系統(tǒng)的求解中, 使得當(dāng)m比n小時, 時間復(fù)雜度可以由O(n2+mn)降為O(mn) 如果差分約束中存在等式約束, 即xi-xj=bk, 如何求解? xi=bk 或者-xi=bk呢? 如果限定xi=0, 證明bel

12、lman-ford算法得到的可行解讓xi總和最大化 證明bellman-ford算法得到的可行解讓maxxi-minxi最小 修改算法使得當(dāng)b取實(shí)數(shù)時可以得到整數(shù)解. 如果給定變量子集需要取整數(shù)呢?運(yùn)用出納員的雇傭 24小時營業(yè)的超市需要一批出納員來滿足它的需求, 每天的不同時段需要不同數(shù)目的出納員 給出每小時需要出納員的最少數(shù)R0, , R23 R(0)表示從午夜到午夜1:00需要出納員的最少數(shù)目， R(1)表示上午1:00到2:00之間需要的 每一天，這些數(shù)據(jù)都是相同的 有N人申請這項工作, 如果第i個申請者被錄用，他將從ti刻開始連續(xù)工作8小時 計算為滿足上述限制需要雇傭的最少出納員數(shù)目

13、 i時刻可以有比對應(yīng)的Ri更多的出納員在工作分析 前i小時的雇傭總數(shù)：si (規(guī)定s-1 = 0) 第i小時需要的出納員：ri 第i小時申請的人數(shù)：ti 取(i,j)滿足i = (j+8) mod 24, 則有不等式 0 = si si-1 j時 si sj = ri I = ri sum 當(dāng)sum固定時, 此不等式組是差分約束系統(tǒng) 可以枚舉sum, 也可以二分五、五、Gabow的變尺度算法的變尺度算法變尺度算法 變尺度算法(scaling algorithm)廣泛的應(yīng)用在圖論算法設(shè)計中, 其基本思想是先只考慮某相關(guān)輸入值的最高位, 然后考慮前兩位、前三位、直到考慮完所有位, 則得到正確結(jié)果

14、考慮SSSP問題. 令k表示需要考慮的位數(shù).一般取k=log2(W+1)(取上整), wi(u, v)表示邊權(quán)w(u, v)的前i位. (當(dāng)k=5, w(i,j)=(11001)2時w3(i,j)=(110)2 讓div表示取wi為權(quán)函數(shù)時的最短路, 則di可以通過di-1用O(E)的時間算出，因此總時間復(fù)雜度為O(ElogW)Gabow算法 引理引理: 若恒有若恒有dv =|E|, 則則d可以在可以在O(E)時間算出時間算出.證明證明: 用用dijkstra, 計數(shù)排序計數(shù)排序, 則所有操作都是則所有操作都是O(1) Gabow算法算法 首先用首先用O(E)時間算出時間算出d1 由于由于wi

15、(u,v)等于等于2wi-1(u,v)或者或者2wi-1(u,v)+1, 因因此此 對于任意點(diǎn)對于任意點(diǎn)v, 2di-1v=dv=2di-1v+|V|-1 對對w重加權(quán)重加權(quán), wi(u,v)=wi(u,v)+2di-1u-2di-1v 則則w(u,v)非負(fù)非負(fù), 且且div=div+2di-1v, 且且div=|E| 因此可以在因此可以在O(E)時間通過時間通過di-1計算計算di 總時間復(fù)雜度為總時間復(fù)雜度為O(ElogW)六、每對結(jié)點(diǎn)最短路六、每對結(jié)點(diǎn)最短路(APSP)APSP基本想法 考慮從每個點(diǎn)出發(fā)做一次SSSP的時間效率 權(quán)任意時n次bellman-ford是O(n2m), 稠密圖

16、時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)算出矩陣乘法算法 可以通過矩陣乘法計算任兩點(diǎn)間最短路基本思想和改進(jìn) 矩陣乘法算法思想:不停加邊(算法如下, O(n3) 優(yōu)化 時間: 二分計算冪. O(n3logn). 空間用滾動矩陣O(n2) 用Strassen矩陣乘法: O(nlog7log

17、n)練習(xí) 如何求出有向加權(quán)圖中邊數(shù)最少的負(fù)圈?七、七、Floyd-warshall算法算法狀態(tài)設(shè)計 設(shè)di,j,k是 在只允許經(jīng)過結(jié)點(diǎn)1k的情況下 i到j(luò)的最短路長度 則它有兩種情況想一想，為什么）： 最短路經(jīng)過點(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狀態(tài)方程Floyd-Warshall算法 把k放外層循環(huán)，可以節(jié)省內(nèi)存 留意無窮大的運(yùn)算 時間復(fù)雜度: O(n3) 空間復(fù)雜度: O(n2)輸出最短路 計算出最短路值后,可以用下面的過程可以輸出任意兩點(diǎn)間的最短路八、八、Johnson算法算法Johnson算法 稀疏圖中, floyd算法時間效率并不理想 重加權(quán) 目的：權(quán)變非負(fù)后用dijkstra 每條邊等量增加可能改變最短路樹 例子：全部增加2的情況右圖） Johnson算法 目的：找到c(v) 重加權(quán)公式：w(u,v)=c(u)+w(u,v)-c(v) 加權(quán)后最短路樹不變 因為對于任意路su, w(su)=w(su)+c(s)-c(u)Johnson算法 如何設(shè)