最短路徑課件1

最短路徑2019/3/29最短路徑2019/3/29單源最短路徑 Dijkstra算法及堆優(yōu)化 Bellman-Ford算法 SPFA算法任意兩點(diǎn)間的最短路 Folyd算法

應(yīng)用：傳遞閉包最短路問題的擴(kuò)展與應(yīng)用

差分約束系統(tǒng)

CONTENTS單源最短路徑CONTENTS單源最短路徑SSSP,SingleSourceShortestPathProblem/01單源最短路徑SSSP,/01單源最短路徑問題4給定一張帶權(quán)圖以及一個起點(diǎn)S,終點(diǎn)T，求S到T的最短路徑。單源最短路徑問題4給定一張帶權(quán)圖以及一個起點(diǎn)S,終點(diǎn)T，求SDijkstra算法5適用于正權(quán)圖的單源最短路徑問題。算法流程：定義源點(diǎn)為S，數(shù)組dis[x]為源點(diǎn)S到x的最短路徑初始化dis數(shù)組為INF,并令dis[S]=0遍歷數(shù)組，找到未訪問點(diǎn)中dis[x]最小值的下標(biāo)x，將x點(diǎn)標(biāo)記為已訪問松弛原理，遍歷與x直接相鄰的點(diǎn)y，更新dis[y]的最小值重復(fù)第2,3步，直到所有點(diǎn)都已被訪問Dijkstra算法5適用于正權(quán)圖的單源最短路徑問題。松弛原理、三角不等式6if(dis[u]+w[u][v]<dis[v])

dis[v]=dis[u]+w[u][v];Dis[A]Dis[B]Dis[C]step10INFINFstep20206step30min(dis[b],dis[c]+w[b][c])=min(20,13)=136松弛原理、三角不等式6if(dis[u]+w[u][v]樸素Dijkstra算法7intdijkstra(ints,intt){ memset(vis,0,sizeofvis); for(inti=0;i<n;i++)dis[i]=(i==s?0:INF); //初始化dis for(inti=0;i<n;i++) { intx,m=INF; for(inty=0;y<n;y++)if(!vis[y]&&dis[y]<=m)m=dis[x=y]; //未訪問點(diǎn)中dis最小值 vis[x]=1; for(inty=0;y<n;y++)dis[y]=min(dis[y],dis[x]+w[x][y]); //松弛操作 } returndis[t];}復(fù)雜度為O(n^2).樸素Dijkstra算法7intdijkstra(intDijkstra算法的優(yōu)化8樸素Dijkstra算法通過O(n)遍歷dis數(shù)組實(shí)現(xiàn)每次找到未訪問的最小值結(jié)點(diǎn)x，重復(fù)n次操作，復(fù)雜度為O(n^2)考慮優(yōu)化過程中每次尋找dis值最小值的過程以dis值為key維護(hù)小頂堆，每次取堆頂結(jié)點(diǎn)x，對其相鄰節(jié)點(diǎn)進(jìn)行松弛操作總復(fù)雜度為O((n+m)logn)，在稀疏圖中作用比較明顯structnode{intu,dis;booloperator<(constnode&no)const{returndis>no.dis;}};Dijkstra算法的優(yōu)化8樸素Dijkstra算法通過O(堆優(yōu)化Dijkstra9voiddijkstra(ints){for(inti=1;i<=n;i++)dis[i]=inf;dis[s]=0;priority_queue<node>que;que.push({0,s});while(!que.empty()){nodef=que.top();que.pop();intu=f.u,d=f.dis;if(d!=dis[u])continue;for(inti=head[u];~i;i=edge[i].nex){intv=edge[i].to,w=edge[i].w;if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;que.push({v,dis[v]});}}}}堆優(yōu)化Dijkstra9voiddijkstra(int帶負(fù)權(quán)邊的最短路徑問題10基于貪心性質(zhì)，Dijkstra算法不能處理帶負(fù)權(quán)邊的最短路問題。對于可能負(fù)權(quán)邊的圖上的最短路徑，我們引入Bellman-Ford算法求解。帶負(fù)權(quán)邊的最短路徑問題10基于貪心性質(zhì)，Dijkstra算法Bellman-Ford算法11Bellman-Ford算法基于動態(tài)規(guī)劃，反復(fù)使用已有的邊來更新最短距離，算法的核心思想是松弛。即if(dis[v]<dis[u]+map[u][v])dis[v]=dis[u]+map[u][v]，與dijkstra算法相同如果沒有負(fù)權(quán)回路，Bellman-Ford算法應(yīng)該會在n-1次松弛后結(jié)束如果有負(fù)權(quán)回路，第n次操作仍然會成功，Bellman-Ford算法就是利用這個性質(zhì)判定負(fù)環(huán)。算法流程：定義源點(diǎn)為S，數(shù)組dis[x]為源點(diǎn)S到x的最短路徑初始化dis數(shù)組為INF,并令dis[S]=0對于每條邊(u,v),如果dis[u]!=INF且dis[v]>dis[u]+map[u][v]，更新dis[v]重復(fù)步驟2n-1次或直到某次中不再更新，進(jìn)入步驟4對于每條邊(u,v),如果dis[u]!=INF且dis[v]>dis[u]+map[u][v]，則存在負(fù)權(quán)回路復(fù)雜度為O(n*m)Bellman-Ford算法11Bellman-Ford算法Bellman-Ford算法12boolbellmanFord(ints){ for(inti=0;i<n;i++)dis[i]=i==s?0:INF; for(inti=0;i<n-1;i++) //n-1次松弛操作 { for(intu=0;u<n;u++) //取以u為起點(diǎn)的所有邊進(jìn)行更新 { if(dis[u]==INF)continue; for(intk=head[u];~k;k=edge[k].nex) dis[edge[i].to]=min(dis[edge[i].to],dis[u]+edge[i].w); } } for(intu=0;u<n;u++) //判斷負(fù)環(huán) { if(dis[u]==INF)continue; for(intk=head[u];~k;k=edge[i].nex) if(dis[edge[k].to]>dis[u]+edge[k].w)returnfalse; } returntrue;}Bellman-Ford算法12boolbellmanFoSPFA算法130.關(guān)于SPFA它死了 ——NOI2018在非負(fù)權(quán)邊的單源最短路徑問題中，不要使用SPFA

請使用穩(wěn)定O(nlogn)的堆優(yōu)化Dijkstra

在含負(fù)權(quán)邊的最短路徑問題中，SPFA的復(fù)雜度最壞情況下復(fù)雜度等同于Bellman-Ford為什么

如何看待SPFA算法已死這種說法？

如何卡SPFA？

SPFA算法130.關(guān)于SPFASPFA算法14SPFA算法是在Bellman-Ford算法基礎(chǔ)上進(jìn)行改進(jìn)的一種算法，使其能夠在計(jì)算帶負(fù)邊權(quán)圖的單源最短路徑的情況下，時間復(fù)雜度大幅度降低。算法流程：初始化dis數(shù)組為INF,并令dis[S]=0,新建隊(duì)列，講源點(diǎn)S入隊(duì)，標(biāo)記S已在隊(duì)列中；取出隊(duì)首結(jié)點(diǎn)u，標(biāo)記出隊(duì)，對u出隊(duì)的次數(shù)進(jìn)行檢查，如果大于n，說明出現(xiàn)負(fù)環(huán)，算法結(jié)束否則，遍歷x所連接的邊，如果邊k的另一端的節(jié)點(diǎn)v可以更新（松弛原理），則更新dis[v]并檢查v是否在隊(duì)列中，如果不在，加入隊(duì)列重復(fù)執(zhí)行步驟2，直到隊(duì)列為空SPFA算法14SPFA算法是在Bellman-Ford算法SPFA算法15boolspfa(ints){for(inti=0;i<n;i++)dis[i]=INF;queue<int>que;que.push(s);dis[s]=0,vis[s]=true;while(!que.empty()){intu=que.front();que.pop();vis[u]=false,cnt[u]++;if(cnt[u]>n)returnfalse; //存在負(fù)環(huán)for(inti=head[u];~i;i=edge[i].nex){ //更新相鄰結(jié)點(diǎn)disif(dis[edge[i].to]>dis[u]+edge[i].w){if(!vis[edge[i].to])que.push(edge[i].to),vis[edge[i].to];dis[edge[i].to]=dis[u]+edge[i].w;}}}returntrue;}SPFA算法15boolspfa(ints){任意兩點(diǎn)間的最短路Supportingtexthere.Whenyoucopy&paste,choose"keeptextonly"option./02任意兩點(diǎn)間的最短路Supportingtexthere.Floyd算法17F[i][j]=min(F[i][j],F[i][k]+F[k][j]);這個算法是RobertW.Floyd和StephanWarshall在1962年各自獨(dú)立發(fā)表的Floyd算法17Floyd算法18for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)for(intk=1;k<=n;k++)F[i][j]=min(F[i][j],F[i][k]+F[k][j]);在設(shè)定邊權(quán)之前，需要初始化F[i][j]=i==j?0:

INF;Floyd算法基于動態(tài)規(guī)劃的思想，用于求解任意兩點(diǎn)間的最短路問題，復(fù)雜度為O(n^3)Floyd算法18for(inti=1;i<=n傳遞閉包19傳遞閉包，即在離散數(shù)學(xué)中，在集合X上的二元關(guān)系R的傳遞閉包是包含R的X上的最小的傳遞關(guān)系。如，集合X為一系列人的集合，二元關(guān)系R為“為父子”，則R的傳遞閉包即為關(guān)系：x是y的祖先；再如，集合X為空港的集合，而關(guān)系xRy為“從空港x到空港y有直航”，則R的傳遞閉包是：可能經(jīng)一次或多次航行從x飛到y(tǒng)以一個表示兩點(diǎn)間直接關(guān)系的矩陣R，通過Floyd算法，求出其傳遞閉包（即每兩點(diǎn)存在的直接或間接關(guān)系）傳遞閉包19傳遞閉包，即在離散數(shù)學(xué)中，在集合X上的二元關(guān)POJ-366020有n頭牛比賽，m種比賽結(jié)果，求一共有多少頭牛的排名被確定了。其中如果a戰(zhàn)勝b，b戰(zhàn)勝c，則也可以說a戰(zhàn)勝c，即可以傳遞勝負(fù)。求能確定排名的牛的數(shù)目。POJ-366020有n頭牛比賽，m種比賽結(jié)果，求一共有多少POJ-366021如果一頭牛被x頭牛打敗，打敗了y頭牛，且x+y=n-1，則這頭牛的排名被確定了。則我們只要確定任意兩頭牛的勝負(fù)關(guān)系，再遍歷所有牛的狀態(tài)，判斷x+y是否等于n-1，將滿足這個條件的牛數(shù)目加起來即為所求解。將其確定勝負(fù)過程抽象為傳遞閉包，對原矩陣跑Floyd。傳遞閉包中矩陣上點(diǎn)的入度和出度即為勝負(fù)次數(shù)。POJ-366021如果一頭牛被x頭牛打敗，打敗了y頭牛，且最短路問題的擴(kuò)展與應(yīng)用Supportingtexthere.Whenyoucopy&paste,choose"