第六講最短路

第六講最短路第一頁，共五十六頁，編輯于2023年，星期五聲明本系列教學幻燈片屬于劉汝佳、黃亮著《算法藝術與信息學競賽》配套幻燈片本幻燈片可從本書blog上免費下載，即使您并未購買本書.若作為教學使用，歡迎和作者聯(lián)系以取得技術支持，也歡迎提供有不同針對性的修改版本，方便更多人使用有任何意見，歡迎在blog上評論Blog地址：第二頁，共五十六頁，編輯于2023年，星期五內容介紹一、SSSP問題二、dijkstra算法三、Bellman-ford算法四、差分約束系統(tǒng)五、Gabow的變尺度算法六、APSP問題七、floyd-warshall算法八、Johnson算法第三頁，共五十六頁，編輯于2023年，星期五一、單源最短路問題(SSSP)第四頁，共五十六頁，編輯于2023年，星期五SSSP給加權圖和一個起點s,求s到所有點的最短路(邊權和最小的路徑)最短路有環(huán)嗎正環(huán):何必呢,刪除環(huán)則得到更短路負環(huán):無最短路,因為可以沿負環(huán)兜圈子第五頁，共五十六頁，編輯于2023年，星期五最優(yōu)性原理最優(yōu)性原理:若最短路uv經(jīng)過中間結點w,則uw和wv的路徑分別是u到w和w到v的最短路.意義:貪心、動態(tài)規(guī)劃第六頁，共五十六頁，編輯于2023年，星期五最短路的表示最短路的表示s到所有點的最短路不需要分別表示最短路樹:到每個點都沿著樹上的唯一路徑走實際代碼:記錄每個點的父親pred[u]即可輸出最短路:從終點沿著pred[u]遞推回起點第七頁，共五十六頁，編輯于2023年，星期五為什么單源最短路形成樹?考慮下圖如果uz的路只取一條即可第八頁，共五十六頁，編輯于2023年，星期五最短路樹和最小生成樹第九頁，共五十六頁，編輯于2023年，星期五一般SSSP算法臨時最短路存在此路，即真實的最短路長度不大于此路長度但是有可能有更短的，所以此路長度只是一個上界給定起點s，對于每個頂點v，定義dist(v)為臨時最短路樹中s->v的長度pred(v)為臨時最短路樹中s->v中v的前驅初始化:dist(s)=0,pred(s)=NULL,初始化:所有其他dist(v)為無窮，pred(v)=NULLdist(v)稱為點v的標號(label),它是最短路的上界基本想法:讓標號不斷趨近,最終達到最短路第十頁，共五十六頁，編輯于2023年，星期五一般SSSP算法什么樣的標號明顯可以改進(趨近最短路)?一條邊(u,v)被稱為緊的(tense),如果dist(u)+w(u,v)<dist(v)可以松弛：dist(v)=dist(u)+w(u,v),pred(v)=u結論存在緊的邊，一定沒有正確的求出最短路樹不存在緊的邊，一定正確的求出最短路樹第十一頁，共五十六頁，編輯于2023年，星期五一般SSSP算法的正確性(u,v)被稱為緊的：dist(u)+w(u,v)<dist(v)不存在緊邊，一定求出最短路樹即由pred表示出的路徑上所有邊權和等于dist(v)（歸納于松弛的次數(shù)）結束時對s到v的任意路sv，dist(v)<=w(sv)歸納于sv所含邊數(shù)，假設su-v（u=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)第十二頁，共五十六頁，編輯于2023年，星期五一般SSSP算法的結束條件剛才已經(jīng)證明結束時dist(v)和pred(v)相容若算法結束，則結果正確算法何時能結束呢？含負圈（能到達的），則永不結束，因為在一次松弛以后，負圈上一定有緊邊（反證）不含負圈，則一定結束，因為要么減少一個無窮dist值，要么讓所有有限dist值之和至少減少一個“不太小的正值”。第十三頁，共五十六頁，編輯于2023年，星期五一般SSSP算法一般算法可以以任意順序尋找緊邊并松弛收斂時間沒有保障解決方案：把結點放到bag中，每次取一個出來檢查特殊bag：dijkstra(heap),bellman-ford(queue)第十四頁，共五十六頁，編輯于2023年，星期五二、dijkstra算法第十五頁，共五十六頁，編輯于2023年，星期五Dijkstra算法E.W.Dijkstra.Anoteontwoproblemsinconnectionwithgraphs.Num.Math.,1:269-271,1959原始是O(n2),可以用各種形式的堆加速第十六頁，共五十六頁，編輯于2023年，星期五Dijkstra算法標號設定算法:每次dist(v)最小的一個恰好等于它的最短值，予以固定正確性證明(注意為什么需要權非負)第十七頁，共五十六頁，編輯于2023年，星期五第十八頁，共五十六頁，編輯于2023年，星期五時間復雜度Dijkstra算法使用了一個優(yōu)先隊列INSERT(line3),每個結點一次EXTRACT-MIN,每個結點一次DECREASE-KEY(line8,在RELAX過程中),一共|E|次直接實現(xiàn):O(V2)二項堆:O(ElogV)Fibonacci堆:O(E+VlogV)第十九頁，共五十六頁，編輯于2023年，星期五練習給有向加權圖,邊權值為[0,1]之間的實數(shù),代表邊的可靠性(各邊的可靠性獨立).找出s到t的路徑中可靠性最大的一條(總可靠性等于每條邊可靠性之乘積)假設邊權值范圍為{1,2,3,…,W}把每條邊拆成w(u,v)條邊串聯(lián),然后BFS直接修改dijkstra得到O(VW+E)的算法優(yōu)化到O((V+E)lgW)從s出發(fā)的邊有可能有負邊(但無負環(huán)),其他邊均為正權.Dijkstra算法能得到最優(yōu)解嗎?第二十頁，共五十六頁，編輯于2023年，星期五應用——路的最小公倍數(shù)給出一個帶權無向圖G邊權為1…1000的整數(shù)對于v0到v1的任意一條簡單路p,定義s(p)為p上所有邊權的最大公約數(shù)考慮v0到v1的所有路p1,p2,…,求所有s(p1),s(p2),…的最小公倍數(shù)第二十一頁，共五十六頁，編輯于2023年，星期五三、bellman-ford算法第二十二頁，共五十六頁，編輯于2023年，星期五SSSP：bellman-ford算法Ford1956,Bellman1958,Moore1959.如有最短路，則每個頂點最多經(jīng)過一次這條路不超過n-1條邊長度為k的路由長度為k-1的路增加一條邊得到由最優(yōu)性原理,只考慮長度為1…k-1的最短路算法梗概:每次迭代依次松弛每條邊時間復雜度O(Dm)，v為迭代次數(shù)(v<=n-1)完全圖邊權在[0,1]中均勻分布,很大概率D=O(log2n)若某次迭代沒進行成功松弛,可立即停止可用dijkstra得到初始dist第二十三頁，共五十六頁，編輯于2023年，星期五第二十四頁，共五十六頁，編輯于2023年，星期五Yen的修改算法把G中的邊(vi,vj)分為兩類:f邊:i<jb邊:i>j每次迭代先從v1遍歷到v|V|,松弛f邊,再從v|V|遍歷回v1,松弛b邊則最多只需要|V|/2次(取上整)迭代,但不降低時間復雜度第二十五頁，共五十六頁，編輯于2023年，星期五練習給出可能有負權的有向加權圖,對于每個點v,在O(VE)時間求出離v最近點到它的距離給出有負圈的圖,在O(VE)時間內輸出圈上的結點列表第二十六頁，共五十六頁，編輯于2023年，星期五應用——套匯第二十七頁，共五十六頁，編輯于2023年，星期五四、差分約束系統(tǒng)第二十八頁，共五十六頁，編輯于2023年，星期五差分約束系統(tǒng)線性規(guī)劃(linearprogramming,LP):給m*n矩陣A、m維向量b和n維向量c,求出x為向量使得Ax<=b,且sum{cixi}最小可行性問題(feasibilityproblem):只需要任意找出一組滿足Ax<=b的解向量x差分約束系統(tǒng)(systemofdifferenceconstraints):A的每行恰好一個1和一個-1,其他元素都是0.相當于關于n個變量的m個差分約束,每個約束都形如xj-xi<=bk,其中1<=i,j<=n,1<=k<=m.第二十九頁，共五十六頁，編輯于2023年，星期五差分約束系統(tǒng)舉例左邊的可行性問題等價于右邊的差分約束系統(tǒng)第三十頁，共五十六頁，編輯于2023年，星期五基本思路定理:給定差分約束系統(tǒng)的一組解,給每個變量加上一個常數(shù)d,將得到另外一組解約束圖:結點是變量,一個約束對應一條弧,若有弧(u,v),則得到xu后,有xv<=xu+w(u,v)第三十一頁，共五十六頁，編輯于2023年，星期五算法定理:如果約束圖沒有負圈,則可取xu為起點v0到u的最短路長;若約束圖有負圈,差分約束系統(tǒng)無解.正確性證明無負圈:由松弛條件可證明每個約束得到滿足有負圈:把負圈上的約束條件疊加將得到一個矛盾不等式算法步驟構圖,得到n+1個結點m+n條邊運行bellman-ford,時間O(n2+mn)第三十二頁，共五十六頁，編輯于2023年，星期五練習如何修改bellman-ford算法,使得將它應用在差分約束系統(tǒng)的求解中,使得當m比n小時,時間復雜度可以由O(n2+mn)降為O(mn)如果差分約束中存在等式約束,即xi-xj=bk,如何求解?xi<=bk或者-xi<=bk呢?如果限定xi<=0,證明bellman-ford算法得到的可行解讓xi總和最大化證明bellman-ford算法得到的可行解讓max{xi}-min{xi}最小修改算法使得當b取實數(shù)時可以得到整數(shù)解.如果給定變量子集需要取整數(shù)呢?第三十三頁，共五十六頁，編輯于2023年，星期五應用——出納員的雇傭24小時營業(yè)的超市需要一批出納員來滿足它的需求,每天的不同時段需要不同數(shù)目的出納員給出每小時需要出納員的最少數(shù)R0,…,R23R(0)表示從午夜到午夜1:00需要出納員的最少數(shù)目，R(1)表示上午1:00到2:00之間需要的…每一天，這些數(shù)據(jù)都是相同的有N人申請這項工作,如果第i個申請者被錄用，他將從ti刻開始連續(xù)工作8小時計算為滿足上述限制需要雇傭的最少出納員數(shù)目i時刻可以有比對應的Ri更多的出納員在工作第三十四頁，共五十六頁，編輯于2023年，星期五分析前i小時的雇傭總數(shù)：s[i](規(guī)定s[-1]=0)第i小時需要的出納員：r[i]第i小時申請的人數(shù)：t[i]取(i,j)滿足i=(j+8)mod24,則有不等式0<=s[i]–s[i-1]<=t[i]s[23]–s[-1]=sumi>j時s[i]–s[j]>=r[i]I<j時s[i]–s[j]>=r[i]–sum當sum固定時,此不等式組是差分約束系統(tǒng)可以枚舉sum,也可以二分第三十五頁，共五十六頁，編輯于2023年，星期五五、Gabow的變尺度算法第三十六頁，共五十六頁，編輯于2023年，星期五變尺度算法變尺度算法(scalingalgorithm)廣泛的應用在圖論算法設計中,其基本思想是先只考慮某相關輸入值的最高位,然后考慮前兩位、前三位、…直到考慮完所有位,則得到正確結果考慮SSSP問題.令k表示需要考慮的位數(shù).一般取k=log2(W+1)(取上整),wi(u,v)表示邊權w(u,v)的前i位.(當k=5,w(i,j)=(11001)2時w3(i,j)=(110)2讓di[v]表示取wi為權函數(shù)時的最短路,則di可以通過di-1用O(E)的時間算出，因此總時間復雜度為O(ElogW)第三十七頁，共五十六頁，編輯于2023年，星期五Gabow算法引理:若恒有d[v]<=|E|,則d可以在O(E)時間算出.證明:用dijkstra,計數(shù)排序,則所有操作都是O(1)Gabow算法首先用O(E)時間算出d1由于wi(u,v)等于2wi-1(u,v)或者2wi-1(u,v)+1,因此對于任意點v,2di-1[v]<=d[v]<=2di-1[v]+|V|-1對w重加權,wi’(u,v)=wi(u,v)+2di-1[u]-2di-1[v]則w’(u,v)非負,且di[v]=di’[v]+2di-1[v],且di’[v]<=|E|因此可以在O(E)時間通過di-1計算di總時間復雜度為O(ElogW)第三十八頁，共五十六頁，編輯于2023年，星期五六、每對結點最短路(APSP)第三十九頁，共五十六頁，編輯于2023年，星期五APSP基本想法考慮從每個點出發(fā)做一次SSSP的時間效率權任意時n次bellman-ford是O(n2m),稠密圖時O(n4)思路:動態(tài)規(guī)劃第四十頁，共五十六頁，編輯于2023年，星期五基本動態(tài)規(guī)劃算法d[i,u,v]為u到v最多不超過i條邊的最短路長算法一：d[i,u,v]=min{d[i-1,u,x]+w(x,v)}，x遍歷v的鄰居時間復雜度：O(V2E)k短路：d[i,u,v]=sum{d[i-1,u,x]+w(x,v)}算法二:d[i,u,v]為u到v最多不超過2i條邊的最短路長,則最短路可以在O(n3logn)算出第四十一頁，共五十六頁，編輯于2023年，星期五矩陣乘法算法可以通過矩陣乘法計算任兩點間最短路第四十二頁，共五十六頁，編輯于2023年，星期五基本思想和改進矩陣乘法算法思想:不停加邊(算法如下,O(n3))優(yōu)化時間:二分計算冪.O(n3logn).空間用滾動矩陣O(n2)用Strassen矩陣乘法:O(nlog7logn)第四十三頁，共五十六頁，編輯于2023年，星期五練習如何求出有向加權圖中邊數(shù)最少的負圈?第四十四頁，共五十六頁，編輯于2023年，星期五七、Floyd-warshall算法第四十五頁，共五十六頁，編輯于2023年，星期五狀態(tài)設計設d[i,j,k]是在只允許經(jīng)過結點1…k的情況下i到j的最短路長度則它有兩種情況（想一想，為什么）：最短路經(jīng)過點k，d[i,j,k]=d[i,k,k-1]+d[k,j,k-1]最短路不經(jīng)過點k，d[i,j,k]=d[i,j,k-1]第四十六頁，共五十六頁，編輯于2023年，星期五狀態(tài)方程第四十七頁，共五十六頁，編輯于2023年，星期五第四十八頁，共五十六頁，編輯于2023年，星期五第四十九頁，共五十六頁，編輯于2023年，星期五Floyd-Warshall算法把k放外層循環(huán)，可以節(jié)省內存注意”無窮大”的運算時間復雜度:O(n3)