最短路径课件1

最短路径2019/3/29最短路径2019/3/29单源最短路径 Dijkstra算法及堆优化 Bellman-Ford算法 SPFA算法任意两点间的最短路 Folyd算法

应用：传递闭包最短路问题的扩展与应用

差分约束系统

CONTENTS单源最短路径CONTENTS单源最短路径SSSP,SingleSourceShortestPathProblem/01单源最短路径SSSP,/01单源最短路径问题4给定一张带权图以及一个起点S,终点T，求S到T的最短路径。单源最短路径问题4给定一张带权图以及一个起点S,终点T，求SDijkstra算法5适用于正权图的单源最短路径问题。算法流程：定义源点为S，数组dis[x]为源点S到x的最短路径初始化dis数组为INF,并令dis[S]=0遍历数组，找到未访问点中dis[x]最小值的下标x，将x点标记为已访问松弛原理，遍历与x直接相邻的点y，更新dis[y]的最小值重复第2,3步，直到所有点都已被访问Dijkstra算法5适用于正权图的单源最短路径问题。松弛原理、三角不等式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]; //未访问点中dis最小值 vis[x]=1; for(inty=0;y<n;y++)dis[y]=min(dis[y],dis[x]+w[x][y]); //松弛操作 } returndis[t];}复杂度为O(n^2).朴素Dijkstra算法7intdijkstra(intDijkstra算法的优化8朴素Dijkstra算法通过O(n)遍历dis数组实现每次找到未访问的最小值结点x，重复n次操作，复杂度为O(n^2)考虑优化过程中每次寻找dis值最小值的过程以dis值为key维护小顶堆，每次取堆顶结点x，对其相邻节点进行松弛操作总复杂度为O((n+m)logn)，在稀疏图中作用比较明显structnode{intu,dis;booloperator<(constnode&no)const{returndis>no.dis;}};Dijkstra算法的优化8朴素Dijkstra算法通过O(堆优化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]});}}}}堆优化Dijkstra9voiddijkstra(int带负权边的最短路径问题10基于贪心性质，Dijkstra算法不能处理带负权边的最短路问题。对于可能负权边的图上的最短路径，我们引入Bellman-Ford算法求解。带负权边的最短路径问题10基于贪心性质，Dijkstra算法Bellman-Ford算法11Bellman-Ford算法基于动态规划，反复使用已有的边来更新最短距离，算法的核心思想是松弛。即if(dis[v]<dis[u]+map[u][v])dis[v]=dis[u]+map[u][v]，与dijkstra算法相同如果没有负权回路，Bellman-Ford算法应该会在n-1次松弛后结束如果有负权回路，第n次操作仍然会成功，Bellman-Ford算法就是利用这个性质判定负环。算法流程：定义源点为S，数组dis[x]为源点S到x的最短路径初始化dis数组为INF,并令dis[S]=0对于每条边(u,v),如果dis[u]!=INF且dis[v]>dis[u]+map[u][v]，更新dis[v]重复步骤2n-1次或直到某次中不再更新，进入步骤4对于每条边(u,v),如果dis[u]!=INF且dis[v]>dis[u]+map[u][v]，则存在负权回路复杂度为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为起点的所有边进行更新 { 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++) //判断负环 { 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.关于SPFA它死了 ——NOI2018在非负权边的单源最短路径问题中，不要使用SPFA

请使用稳定O(nlogn)的堆优化Dijkstra

在含负权边的最短路径问题中，SPFA的复杂度最坏情况下复杂度等同于Bellman-Ford为什么

如何看待SPFA算法已死这种说法？

如何卡SPFA？

SPFA算法130.关于SPFASPFA算法14SPFA算法是在Bellman-Ford算法基础上进行改进的一种算法，使其能够在计算带负边权图的单源最短路径的情况下，时间复杂度大幅度降低。算法流程：初始化dis数组为INF,并令dis[S]=0,新建队列，讲源点S入队，标记S已在队列中；取出队首结点u，标记出队，对u出队的次数进行检查，如果大于n，说明出现负环，算法结束否则，遍历x所连接的边，如果边k的另一端的节点v可以更新（松弛原理），则更新dis[v]并检查v是否在队列中，如果不在，加入队列重复执行步骤2，直到队列为空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; //存在负环for(inti=head[u];~i;i=edge[i].nex){ //更新相邻结点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){任意两点间的最短路Supportingtexthere.Whenyoucopy&paste,choose"keeptextonly"option./02任意两点间的最短路Supportingtexthere.Floyd算法17F[i][j]=min(F[i][j],F[i][k]+F[k][j]);这个算法是RobertW.Floyd和StephanWarshall在1962年各自独立发表的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]);在设定边权之前，需要初始化F[i][j]=i==j?0:

INF;Floyd算法基于动态规划的思想，用于求解任意两点间的最短路问题，复杂度为O(n^3)Floyd算法18for(inti=1;i<=n传递闭包19传递闭包，即在离散数学中，在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。如，集合X为一系列人的集合，二元关系R为“为父子”，则R的传递闭包即为关系：x是y的祖先；再如，集合X为空港的集合，而关系xRy为“从空港x到空港y有直航”，则R的传递闭包是：可能经一次或多次航行从x飞到y以一个表示两点间直接关系的矩阵R，通过Floyd算法，求出其传递闭包（即每两点存在的直接或间接关系）传递闭包19传递闭包，即在离散数学中，在集合X上的二元关POJ-366020有n头牛比赛，m种比赛结果，求一共有多少头牛的排名被确定了。其中如果a战胜b，b战胜c，则也可以说a战胜c，即可以传递胜负。求能确定排名的牛的数目。POJ-366020有n头牛比赛，m种比赛结果，求一共有多少POJ-366021如果一头牛被x头牛打败，打败了y头牛，且x+y=n-1，则这头牛的排名被确定了。则我们只要确定任意两头牛的胜负关系，再遍历所有牛的状态，判断x+y是否等于n-1，将满足这个条件的牛数目加起来即为所求解。将其确定胜负过程抽象为传递闭包，对原矩阵跑Floyd。传递闭包中矩阵上点的入度和出度即为胜负次数。POJ-366021如果一头牛被x头牛打败，打败了y头牛，且最短路问题的扩展与应用Supportingtexthere.Whenyoucopy&paste,choose"keeptextonly"option./03最短路问题的扩展与应用Supportingtexther差分约束系统23差分约束系统是线性规划问题的一种：给出一系列形如x–y<=b的不等式约束，问是否有满足条件的解，或求最小/最大解。原理

差分约束系统的解法利用到了单源最短路径问题中的三角形不等式。对于图论的最短路径，有：对于d(v)<=d(u)+w(u,v)

移项得：d(v)–d(u)<=w(u,v)

通过这一性质，即可将差分约束系统转化为最短路问题求解。差分约束系统23差分约束系统是线性规划问题的一种：差分约束系统242.建图

(1)求最小值

对于d(v)–d(u)>=

w(u,v)

从u到v连接一条权重为w(u,v)的边，建图跑最长路

(2)求最大值

对于d(v)–d(u)<=w(u,v)

从u到v连接一条权重为w(u,v)的边，建图跑最短路注意题目本身所给条件需要连的边；如果图不连通，需要加一个超级源点S，到任意顶点的距离为0，并从该点出发。虚点并不引入负圈，故设置负圈之后最短路仍然存在，并且每个约束仍然满足。一般采用SPFA对差分约束系统求解（有负圈边，并可能出现负环）。差分约束系统242.建图Thanks

Thanks

最短路径2019/3/29最短路径2019/3/29单源最短路径 Dijkstra算法及堆优化 Bellman-Ford算法 SPFA算法任意两点间的最短路 Folyd算法

应用：传递闭包最短路问题的扩展与应用

差分约束系统

CONTENTS单源最短路径CONTENTS单源最短路径SSSP,SingleSourceShortestPathProblem/01单源最短路径SSSP,/01单源最短路径问题29给定一张带权图以及一个起点S,终点T，求S到T的最短路径。单源最短路径问题4给定一张带权图以及一个起点S,终点T，求SDijkstra算法30适用于正权图的单源最短路径问题。算法流程：定义源点为S，数组dis[x]为源点S到x的最短路径初始化dis数组为INF,并令dis[S]=0遍历数组，找到未访问点中dis[x]最小值的下标x，将x点标记为已访问松弛原理，遍历与x直接相邻的点y，更新dis[y]的最小值重复第2,3步，直到所有点都已被访问Dijkstra算法5适用于正权图的单源最短路径问题。松弛原理、三角不等式31if(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算法32intdijkstra(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]; //未访问点中dis最小值 vis[x]=1; for(inty=0;y<n;y++)dis[y]=min(dis[y],dis[x]+w[x][y]); //松弛操作 } returndis[t];}复杂度为O(n^2).朴素Dijkstra算法7intdijkstra(intDijkstra算法的优化33朴素Dijkstra算法通过O(n)遍历dis数组实现每次找到未访问的最小值结点x，重复n次操作，复杂度为O(n^2)考虑优化过程中每次寻找dis值最小值的过程以dis值为key维护小顶堆，每次取堆顶结点x，对其相邻节点进行松弛操作总复杂度为O((n+m)logn)，在稀疏图中作用比较明显structnode{intu,dis;booloperator<(constnode&no)const{returndis>no.dis;}};Dijkstra算法的优化8朴素Dijkstra算法通过O(堆优化Dijkstra34voiddijkstra(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]});}}}}堆优化Dijkstra9voiddijkstra(int带负权边的最短路径问题35基于贪心性质，Dijkstra算法不能处理带负权边的最短路问题。对于可能负权边的图上的最短路径，我们引入Bellman-Ford算法求解。带负权边的最短路径问题10基于贪心性质，Dijkstra算法Bellman-Ford算法36Bellman-Ford算法基于动态规划，反复使用已有的边来更新最短距离，算法的核心思想是松弛。即if(dis[v]<dis[u]+map[u][v])dis[v]=dis[u]+map[u][v]，与dijkstra算法相同如果没有负权回路，Bellman-Ford算法应该会在n-1次松弛后结束如果有负权回路，第n次操作仍然会成功，Bellman-Ford算法就是利用这个性质判定负环。算法流程：定义源点为S，数组dis[x]为源点S到x的最短路径初始化dis数组为INF,并令dis[S]=0对于每条边(u,v),如果dis[u]!=INF且dis[v]>dis[u]+map[u][v]，更新dis[v]重复步骤2n-1次或直到某次中不再更新，进入步骤4对于每条边(u,v),如果dis[u]!=INF且dis[v]>dis[u]+map[u][v]，则存在负权回路复杂度为O(n*m)Bellman-Ford算法11Bellman-Ford算法Bellman-Ford算法37boolbellmanFord(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为起点的所有边进行更新 { 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++) //判断负环 { 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算法380.关于SPFA它死了 ——NOI2018在非负权边的单源最短路径问题中，不要使用SPFA

请使用稳定O(nlogn)的堆优化Dijkstra

在含负权边的最短路径问题中，SPFA的复杂度最坏情况下复杂度等同于Bellman-Ford为什么

如何看待SPFA算法已死这种说法？

如何卡SPFA？

SPFA算法130.关于SPFASPFA算法39SPFA算法是在Bellman-Ford算法基础上进行改进的一种算法，使其能够在计算带负边权图的单源最短路径的情况下，时间复杂度大幅度降低。算法流程：初始化dis数组为INF,并令dis[S]=0,新建队列，讲源点S入队，标记S已在队列中；取出队首结点u，标记出队，对u出队的次数进行检查，如果大于n，说明出现负环，算法结束否则，遍历x所连接的边，如果边k的另一端的节点v可以更新（松弛原理），则更新dis[v]并检查v是否在队列中，如果不在，加入队列重复执行步骤2，直到队列为空SPFA算法14SPFA算法是在Bellman-Ford算法SPFA算法40boolspfa(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; //存在负环for(inti=head[u];~i;i=edge[i].nex){ //更新相邻结点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){任意两点间的最短路Supportingtexthere.Whenyoucopy&paste,choose"keeptextonly"option./02任意两点间的最短路Supportingtexthere.Floyd算法42F[i][j]=min(F[i][j],F[i][k]+F[k][j]);这个算法是RobertW.Floyd和StephanWarshall在1962年各自独立发表的Floyd算法17Floyd算法43for(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]);在设定边权之前，需要初始化F[i][j]=i==j?0:

INF;Floyd算法基于动态规划的思想，用于求解任意两点间的最短路问题，复杂度为O(n^3)Floyd算法18for(inti=1;i<=n传递闭包44传递闭包，即在离散数学中，在集合X上的二元关系R的传递闭包是包含R的X上