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

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

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

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

4、(u)+w(u,v), pred(v)=u 結(jié)論 存在緊的邊，一定沒(méi)有正確的求出最短路樹(shù) 不存在緊的邊，一定正確的求出最短路樹(shù)一般SSSP算法的正確性 (u,v)被稱(chēng)為緊的：dist(u)+w(u,v)dist(v) 不存在緊邊，一定求出最短路樹(shù) 即由pred表示出的路徑上所有邊權(quán)和等于dist(v)（歸納于松弛的次數(shù)） 結(jié)束時(shí)對(duì)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)。因?yàn)闊o(wú)緊邊，所以 dist(v)=dist(u)+w(u,v)=w(sv

5、)一般SSSP算法的結(jié)束條件 剛才已經(jīng)證明 結(jié)束時(shí)dist(v)和pred(v)相容 若算法結(jié)束，則結(jié)果正確 算法何時(shí)能結(jié)束呢？ 含負(fù)圈能到達(dá)的），則永不結(jié)束，因?yàn)樵谝淮嗡沙谝院螅?fù)圈上一定有緊邊反證） 不含負(fù)圈，則一定結(jié)束，因?yàn)橐礈p少一個(gè)無(wú)窮dist值，要么讓所有有限dist值之和至少減少一個(gè)“不太小的正值”。一般SSSP算法 一般算法 可以以任意順序?qū)ふ揖o邊并松弛 收斂時(shí)間沒(méi)有保障 解決方案：把結(jié)點(diǎn)放到bag中，每次取一個(gè)出來(lái)檢查 特殊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)號(hào)設(shè)定算法: 每次dist(v)最小的一個(gè)恰好等于它的最短值，予以固定 正確性證明 (注意為什么需要權(quán)非負(fù))時(shí)間復(fù)雜度 Dijkstra算法使用了一個(gè)優(yōu)先隊(duì)列 INSERT (line 3), 每個(gè)結(jié)點(diǎn)一次 EXTRACT-MIN, 每個(gè)結(jié)點(diǎn)一次 DECREASE-KEY (line 8, 在RELAX過(guò)程中), 一共|E|次 直接實(shí)現(xiàn): O(V2) 二項(xiàng)堆: 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ù)邊(但無(wú)負(fù)環(huán)), 其他邊均為正權(quán). Dijkstra算法能得到最優(yōu)解嗎?運(yùn)用路的最小公倍數(shù) 給出一個(gè)帶權(quán)無(wú)向圖G 邊權(quán)為11 000的整數(shù) 對(duì)于v0到v1的任意一條簡(jiǎn)單路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. 如有最短路，則每個(gè)頂點(diǎn)最多經(jīng)過(guò)一次 這條路不超過(guò)n-1條邊 長(zhǎng)度為k的路由長(zhǎng)度為k-1的路增加一條邊得到 由最優(yōu)性原理, 只考慮長(zhǎng)度為1k-1的最短路 算法梗概: 每次迭代依次松弛每條邊 時(shí)間復(fù)雜度 O(Dm)，v為迭代次數(shù)(v=n-1) 完全圖邊權(quán)在0, 1中均勻分布, 很大概率D=O(log2n) 若某次迭代沒(méi)進(jìn)行成功松弛, 可立即停止 可用dij

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

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

11、法 定理: 如果約束圖沒(méi)有負(fù)圈, 則可取xu為起點(diǎn)v0到u的最短路長(zhǎng); 若約束圖有負(fù)圈, 差分約束系統(tǒng)無(wú)解. 正確性證明 無(wú)負(fù)圈: 由松弛條件可證明每個(gè)約束得到滿(mǎn)足 有負(fù)圈: 把負(fù)圈上的約束條件疊加將得到一個(gè)矛盾不等式 算法步驟 構(gòu)圖, 得到n+1個(gè)結(jié)點(diǎn)m+n條邊 運(yùn)行bellman-ford, 時(shí)間 O(n2+mn)練習(xí) 如何修改bellman-ford算法, 使得將它應(yīng)用在差分約束系統(tǒng)的求解中, 使得當(dāng)m比n小時(shí), 時(shí)間復(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ù)解. 如果給定變量子集需要取整數(shù)呢?運(yùn)用出納員的雇傭 24小時(shí)營(yíng)業(yè)的超市需要一批出納員來(lái)滿(mǎn)足它的需求, 每天的不同時(shí)段需要不同數(shù)目的出納員 給出每小時(shí)需要出納員的最少數(shù)R0, , R23 R(0)表示從午夜到午夜1:00需要出納員的最少數(shù)目， R(1)表示上午1:00到2:00之間需要的 每一天，這些數(shù)據(jù)都是相同的 有N人申請(qǐng)這項(xiàng)工作, 如果第i個(gè)申請(qǐng)者被錄用，他將從ti刻開(kāi)始連續(xù)工作8小時(shí) 計(jì)算為滿(mǎn)足上述限制需要雇傭的最少出納員數(shù)目

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

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

15、(u,v)等于等于2wi-1(u,v)或者或者2wi-1(u,v)+1, 因因此此 對(duì)于任意點(diǎn)對(duì)于任意點(diǎn)v, 2di-1v=dv=2di-1v+|V|-1 對(duì)對(duì)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)時(shí)間通過(guò)時(shí)間通過(guò)di-1計(jì)算計(jì)算di 總時(shí)間復(fù)雜度為總時(shí)間復(fù)雜度為O(ElogW)六、每對(duì)結(jié)點(diǎn)最短路六、每對(duì)結(jié)點(diǎn)最短路(APSP)APSP基本想法 考慮從每個(gè)點(diǎn)出發(fā)做一次SSSP的時(shí)間效率 權(quán)任意時(shí)n次bellman-ford是O(n2m), 稠密圖

16、時(shí)O(n4) 思緒: 動(dòng)態(tài)規(guī)劃基本動(dòng)態(tài)規(guī)劃算法 di,u,v為u到v最多不超過(guò)i條邊的最短路長(zhǎng) 算法一： di,u,v=mindi-1,u,x+w(x,v)，x遍歷v的鄰居 時(shí)間復(fù)雜度：O(V2E) k短路：di,u,v=sumdi-1,u,x+w(x,v) 算法二: di,u,v為u到v最多不超過(guò)2i條邊的最短路長(zhǎng), 則最短路可以在O(n3logn)算出矩陣乘法算法 可以通過(guò)矩陣乘法計(jì)算任兩點(diǎn)間最短路基本思想和改進(jìn) 矩陣乘法算法思想:不停加邊(算法如下, O(n3) 優(yōu)化 時(shí)間: 二分計(jì)算冪. O(n3logn). 空間用滾動(dòng)矩陣O(n2) 用Strassen矩陣乘法: O(nlog7log

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