中北大学ACM-ICPC课程《最短路》

最短路径问题12-计算机科学与技术武宽wukuan_youngboy@2023/2/5中北大学ACM-ICPC集训队1什么是最短路径问题？

在图中的某一顶点（源点）到达另一个顶点（终点）的路径权值代价最小的一条路径。这条路径称之为最短路径（ShortPath）。

给定一个图G(V,E)，V是顶点集合，E是边集合，每一条边有一个权值c，给定一个起始点S和终止点D，求从S出发走到D的权值最小路径，即为最短路径先回忆一下：WhatisGraph？WhatisPath？2023/2/5中北大学ACM-ICPC集训队2图的存储2023/2/5中北大学ACM-ICPC集训队3

那么，面对最短路径这个问题，你又什么好的想法？可以大胆的说出来。

用前几次课的知识是否能解决？

思考一下2023/2/5中北大学ACM-ICPC集训队4还有没有人记得DFS，BFS？

what？

什么是dfs，bfs？

不会的的同学请自行脑补。

假设大家都会了，我们继

续~2023/2/5中北大学ACM-ICPC集训队5

应该可以想到：

DFS（深度优先搜索）得到的结果是图上的一条路径，是任意的。

BFS（广度优先搜索）可以得到图的最短路径，但前提是所有路径的权值相同。

这是我们想要的结果吗？2023/2/5中北大学ACM-ICPC集训队6

显然，我们的要求要更高一点。

但dfs与bfs确实是对图进行所有遍历的一个很好的方法，不会的同学希望下去可以下点功夫。

然后我们引入今天的正题，即对于一个常规的图如何求出我们想要的最短路径。2023/2/5中北大学ACM-ICPC集训队7ShortPath算法具体的形式包括：

确定起点的最短路径问题：即已知起始结点，求最短路径的问题。

确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。

全局最短路径问题：求图中所有的最短路径。2023/2/5中北大学ACM-ICPC集训队8

单源路径的最短路问题：给定一个有n个点的带权有向图，问从指定的起点开始，到其他所有点的最短路径。

1，不断利用松弛操作的Bellman-Ford算法2，利用贪婪技术的Dijkstra算法

3，基于Bellman-Ford优化的SPFA算法

4，Dijkstra的堆优化算法2023/2/5中北大学ACM-ICPC集训队9单源最短路径问题1265341284533111034单源最短路径问题带权图中一个点到另一个点的最短路径一定唯一存在？有路径通达且没有“负权回路”则一定存在不一定唯一单源最短路径是否一定能构成一棵树？如果源点到其他所有点的最短路径都存在，则一定能找到一棵以指定的起点为根的树（边的方向总是从父亲指向儿子）2023/2/5中北大学ACM-ICPC集训队11单源最短路径问题12653412845-33111034

Bellman-Ford算法

如果边权可以为负值，那么可以使用Bellman-Ford算法求解单源最短路径问题。2023/2/5中北大学ACM-ICPC集训队13Bellman-Ford算法算法流程：初始化所有点的dist值为+∞，起点的dist值为0检查所有边uv，用u点的dist值与这条边的权值之和更新v点的dist值。即对所有的边执行一次松弛操作。若此步骤中某个点的dist值更新了，那么可以说此步骤是“有收获的”直到上一轮步骤2没有收获，或步骤2已经重复了n轮，否则再重复一次步骤2。若最后一轮步骤2仍旧是有收获的，那么说明起点能够到达一个负权回路，否则目标就已经达成了。

2023/2/5中北大学ACM-ICPC集训队14什么是松弛操作？

2023/2/5中北大学ACM-ICPC集训队15RELAX操作代码下面看看松弛操作的一些引理

2023/2/5中北大学ACM-ICPC集训队16

2023/2/5中北大学ACM-ICPC集训队17

知道什么是松弛操作后，来看看Bellman-Ford算法吧~。2023/2/5中北大学ACM-ICPC集训队18Bellman-Ford算法的证明证明：如果起点能够到达某个负权回路，那么显然，步骤2总是会有收获。如果起点无法到达一个负权回路，那么当所有点的dist值到达最低值时，步骤2就不再有收获了。而一条最短路径一定没有环，即一条最短路径经过的边数一定不会超过n-1（经过了所有其他的点），所以n-1轮后，任何一个点作为终点的最短路径一定已经求得。时间复杂度显然是O(ne)

2023/2/5中北大学ACM-ICPC集训队19Dijkstra算法如果边权没有负值，可以用Dijkstra算法求解单源最短路径问题。

在学习算法的同时思考下为什么存在这个限制条件？2023/2/5中北大学ACM-ICPC集训队20Dijkstra算法算法流程：初始化所有点的dist值为+∞，起点的dist值为0从所有点中找到未被标记的dist值最小的点x，将x点标记检查所有x引出的边，用x点的dist值与这条边的权值之和更新这条边指向的点的dist值（“松弛操作”）重复步骤2和3直到所有点都被标记2023/2/5中北大学ACM-ICPC集训队21Dijkstra算法1265341284533111034dist:0dist:+∞dist:+∞dist:+∞dist:+∞dist:+∞dist:1dist:10dist:3dist:3dist:5dist:2dist:9

Dijkstra算法一个点的dist值就是“已知的从起点到达它的最短路径长度”如果记下每个点的dist值最后一次更新是由哪条边的松弛操作完成的，这条边就是“已知的从起点到达它的最短路径的最后一条边”一个点被标记也就意味着“这个点的dist值已经不可能再被更新”，即“起点到它的最短路径已经求得”

2023/2/5中北大学ACM-ICPC集训队23Dijkstra算法还记得前面说到过的迪杰斯特拉算法是基于什么思想的嘛？

贪婪技术！又称贪心法！朴素的Dijkstra算法的时间复杂度为O(n^2)。2023/2/5中北大学ACM-ICPC集训队24 Bellman-Ford优化的SPFA算法算法流程：初始化所有点的dist值为+∞，起点的dist值为0，将起点加入一个“待检查点”的队列q从队列q的队首中取出一个节点x，对x引出的所有边执行松弛操作，若某个点的dist值被更新了且这个点不在队列q中，则将其加入队尾重复步骤2直到某个点入队超过n次或队列为空

2023/2/5中北大学ACM-ICPC集训队25Bellman-Ford优化的SPFA算法有理论能够证明，SPFA算法的平均时间复杂度为O(e)。但是有可能退化，最坏会到O(en)。比较适合于稀疏图中求解单源最短路径。如果不用队列，改用栈可以么？

2023/2/5中北大学ACM-ICPC集训队26Dijkstra算法的堆优化如果所有点的dist值用一个堆来维护，“更新某个点的dist值”和“寻找dist值最小的点”就可以在O(logn)的时间复杂度内完成。总时间复杂度就变成了O(elogn)，其中e为图中的边数WHF！！这么多东西有木有很凌乱？那什么是堆？2023/2/5中北大学ACM-ICPC集训队27堆？英文名heap。知道吧？其实跟优先队列是一样的道理~WTF！！什么是优先队列？嗯，优先队列嘛。很简单英文名：priorityqueue这下都清楚了吧？2023/2/5中北大学ACM-ICPC集训队28

堆是一种支持高效查询的数据结构。

堆中的某个节点的值总是不大于或不小于其父节点的值。

堆总是一颗完全树。可将堆看做一个完全二叉树。

优先队列实际上就是队列在堆上的实现。

堆根据其比较关系可以分为大顶堆跟小顶堆两种 STL中提供的priority_queue默认是大顶堆，可以通过自己重载运算符来实现小顶堆的优先队列。

2023/2/5中北大学ACM-ICPC集训队29堆

堆所支持的两种操作：1，向堆中插入一个新的元素2，取出对顶元素

根据堆依建于完全二叉树的特性，堆中的这两种操作都可以在O(logn)的时间复杂度内完成。

有关堆的知识就提到这里，有兴趣继续了解证明的同学可以去查阅相关资料2023/2/5中北大学ACM-ICPC集训队30

单源最短路径问题2023/2/5中北大学ACM-ICPC集训队31又一个思考

如果图中存在负权回路，还能不能求最短路？

那能不能判断出来呢？Bellman-FordorSPFA2023/2/5中北大学ACM-ICPC集训队32

任意点对最短路径问题给定一个有n个点的带权有向图，问任意两个点之间的最短路径长度。2023/2/5中北大学ACM-ICPC集训队33

Floyd算法代码如下（w最初是图的邻接矩阵，算法结束后是任意点对间的最短路径长度）：fork=1tondo fori=1tondo forj=1tondo if(w[i,k]+w[k,j]<w[i,j]) w[i,j]=w[i,k]+w[k,j]2023/2/5中北大学ACM-ICPC集训队34fork=1tondo //此时的w[x,y]为：x到y的“中途只能

//经过1..k-1这些点的”最短路径长度

//下面的二重循环则是求“中途只能

//经过1..k这些点的”最短路径长度

fori=1tondo forj=1tondo if(w[i,k]+w[k,j]<w[i,j]) w[i,j]=w[i,k]+w[k,j]在w[i,j]被更新时记下其因哪个k被更新，将之存储在mid[i,j]中，则mid[i,j]就是i到j的最短路径中经过的编号最大的点，由此可以还原出任意点对间的具体的最短路。

2023/2/5中北大学ACM-ICPC集训队35Floyd算法2023/2/5中北大学ACM-ICPC集训队36Floyd算法如果有负权边但没有负权回路，Floyd算法还是正确的么？答案是依然正确。但是Floyd算法没法判断图中是否有负权回路存在。时间复杂度显然是O(n^3)的。

2023/2/5中北大学ACM-ICPC集训队37Floyd算法如果图中有负权回路存在，Floyd算法最后得到的会是什么？如果要求图（可能是无向图）的最小环，Floyd算法可以给你什么启示么？2023/2/5中北大学ACM-ICPC集训队38Floyd算法如果要求次短路径，甚至第k短路径呢？如果这个图存在负权回路，但要求每个点不走两次的最短路径呢？2023/2/5中北大学ACM-ICPC集训队39ClassOver谢谢大家！相应的习题课安排在下周六上午8:30地点在acm-icpc实验室内。若时间发生变更，会在交流群，新浪微博，人人主页挂出通知20