最短路径的三种算法以及路径还原与负圈判断
图的基础,最短路径的几种解答
单源最短路: Bellman-Ford & Dijkstra 及其简单优化 以及负圈的判断
多源最短路:Floyd-Warshall 算法的简单理解
路径还原问题
算法代码及思路主要参考:《挑战程序设计竞赛》
在此之前读者应对图已经有基础的概念,以及图的邻接表 & 邻接矩阵的表示方法
Bellman-Ford
单源最短路问题是固定一个起点,然后求这个点到其他各个顶点的最短路(最小权值和)
设起点 s 到其他顶点 i 的距离为 d[i] 则很容易可以得到下面这个结论: \[ d[i] = min\{d[j] + edge(j,i)\} \quad edge(j,i) \in E \] 设置初始状态 d[s] = 0 else d[i] = INF 然后只要在循环里不断更新这些值
如果不再更新说明所有路都已达到最短 代码如下:
1 | struct Edge{ int from, to, cost;}; // 定义从点from指向to权值为cost的边 |
如果图中不存在 s 可达的负圈,那么最短路不会经过一个顶点两次,也就是说 最多通过 V-1 条边,也可以这样理
解,每一次更新都会有更短的路径产生,那么在 V 个点的图中,两个点的最远距离只能是 V-1 条边,所以循环最多
只会执行 V-1 次,这个特性将是我们判断是否存在负圈的重要性质
所以我们也可以将上面的代码简单化为:
1 | void Bellman_Ford(int s) // 不存在负圈的情况 |
很容易可以看出来 Bellman 算法的复杂度为 O(V*E)
负圈的判断
在这里,首先要明确负圈(负权环)和负权边的区别
负圈是指一条环状路径上的综合权值为负的,负权边是指权值为负数的边,在算法中如果图是无向图的话,
负权边和负圈是等价的。如下图:也就是在A与B之间形成了一个环,这个环的权值为-2
所以在无向图中负边的存在也就是负圈的存在。所以Bellman主要是可以用来判断有向图中是否存在负圈。
只要存在了负圈,那么 Bellman 的松弛操作(也就是那个每次更新的内容)将会永远的执行下去。
相当于没走一个这个负圈总的权值(路径长度)就会减少。但是我们上面已经得到在不存在负圈的图中最多执行 V-1 次循环,所以我们只要判断在第V次仍然更新了,那么就存在负圈了。代码只要更改一点点就行:
1 | void Bellman_Ford(int s) // 不存在负圈的情况 |
Dijkstra
我们先考虑不存在负边的情况,在 Bellman 算法中每一次都要全部遍历所有的边,而且如果d[i]本身不是最短路径
那么进行那个松弛操作之后的 d[i] 依然不是最短,所以可以对此进行优化:
找到最短路径已经确定的顶点,更新从他出发相邻顶点的最短距离
从此不需要在更新上面已经确定的哪些顶点(即不需要遍历)
这就衍生出了 Dijkstra 算法。上面两点用图来描述就是:
假设初始点为 A 首先 AC < AB
很清楚的我们可以得出结论 AC 就是A到C的最短路径,因为如果从 AB 方向走的话,AB >AC 而且我们的图是没有负边的,所以 BD > 0 也就是说 AB + BD.... > AC 是必然成立的。 所以 A->C 的最短路径已经确定了,之后就需要再去管C点了。算法总的描述如下:
在最开始时,只有起点的最短距离是确定的(而且所有点都未曾使用)。而在尚未使用的顶点中,距离d[i]最小的顶点就是最短距离已经确定的顶点。因为不存在负边,所以 d[i] 不会在以后的更新中变小。这就是 Dijkstra 算法
代码如下:
1 | int cost[MAXN][MAXN]; // cost[i][j] 表示从i到j之间的权值(不存在是为INF) |
简单的优化
上面代码的时间复杂度是 O(V2) , 我们可以通过堆(优先队列)降为O(E*log(V))
上面有一个操作是找到距离最小的点和标记是否使用,这个就可以使用堆来优化
代码如下:
1 | typedef pair<int,int> P; // first 是最短距离 second 是顶点编号 |
Floyd-Warshall
Floyd算法简单暴力,主要用于求多源最短路径(任意两个点的最短路径)
核心代码十分短小精悍
1 | int d[MAXN][MAXN]; // d[u][v] 表示从u -> v的权值 不存在的时候为0 |
十分暴力复杂度可想而知O(V3)
那么这几行代码是什么意思呢? 这其实还是 DP
我们用 d[k+1][i][j] 来表示只使用 0~k和 i,j 顶点的情况下的最短路
初始状态为 d[0][i][j] = cost[i][j] 所以我们可以得到下面这个式子: \[ d[k][i][j] = \begin{cases} d[k-1][i][j] (不经过点K)\\ d[k-1][i][k] + d[k-1][k][j] (经过K点)\\ \end{cases} = min(d[k-1][i][j],d[k-1][i][k] + d[k-1][k][j]) \] 当然 我们可以稍微优化一下,时间以及到极限了,我们可以想办法把空间复杂度降下来
也就是我们上面那个形式,也就是为什么 K 必须放在最外面的原因
我们观察三维的那个式子与K相关的就只有 K 与 K-1 所以我们可以进行降维操作
也就是当K=s的时候,在执行状态压缩之前 d[i][j] 的值存都是的 d[k-1][i][j]
也就是将上一个状态动态保存起来了 所以才有上面的简短的代码
路径还原
最后的问题就是当我们知道最短路径多少的时候,难免有时候需要知道该怎么走才有这条最短路径呢
用 Dijkstra 来演示路径还原 其他的算法也都可以用这个来解决
在此算法中满足 d[j] = d[k] + cost[k][j]的点K我们称为j的前驱结点,也就是在到j之前必须经过点K
我们用一个数组 prev 来存相应节点的前驱结点,不断寻找前驱结点就可以找到最短路了,不过这是从后往前找,最后需要反转一下得到最后的答案。
示例代码如下: 注意第25行
1 | int cost[MAXN][MAXN]; // cost[i][j] 表示从i到j之间的权值(不存在是为INF) |
The end !!!