求最短路径的基本算法

date

Jan 29, 2023

slug

short-path-problem

status

Published

简介

最短路径问题要求我们给出点与点之间的最短路径，根据问题的分类一共有 5 种解决该类问题的方法。

本文将依次介绍每种算法的思想、时间复杂度、适用场景。

问题分类

最短路问题分为两类：

单源最短路：求两个点之间的最短路径，一般是 1 到 n 号点

多源汇最短路：求任意两个点之间的最短路径

而单源最短路问题，根据边的不同，又有一些需要注意的地方：

所有边权都是正数：这种情况是最常见的，用 dijkstra 就能求解

边权存在负数：此时 dijkstra 无法求解，只能使用 BF 或者 SPFA 算法求解

图的存储

邻接矩阵

最简单的存储方式

N是点数，一般不会太大，用于存储稀疏图

邻接表

又称为链式前向星

单源最短路问题算法

dijkstra 算法

该算法的思想是：

维护一个点集，每一轮找到一个离当前点集最近的一个点t，然后将t加入到点集中，同时用这个最近点去尝试更新其它未遍历点的距离，遍历n - 1轮即可得到答案。

伪代码：

经过上面的计算，dist[n] 就是最终答案了。

朴素版 dijkstra

朴素版的 dijkstra 基本上是伪代码的实现，代码如下：

时间复杂度：，n是点数，m是边数

有关时间复杂度的计算可以参考这篇文章： Dijkstra算法时间复杂度分析

适用场景：稠密图，即点少但边多的场景，因此可以用邻接矩阵来存储图

堆优化版 dijkstra

在朴素版 dijkstra 中，下面的步骤：

寻找距离最小的点，这个操作可以用堆来优化。具体做法是小根堆来存储当前距离最小的点，其它步骤相同

需要注意的是，堆里面允许冗余点存在，比如{4, 3}，{2, 3}，{7, 3}这几个组合是允许同时存在的。

st 的含义是点是否被处理过，因此只有在从堆中弹出的时候才标记 st[t] = true

时间复杂度：

适用场景：稀疏图，点多边少

一旦图中存在负权边，dijkstra 算法就失效了，只能使用 BF 算法或者 SPFA 算法求解

BF 算法

思想：

迭代 n 次，每次遍历所有边，尝试去更新dist数组。这样得到的dist数组就是最终结果了

伪代码：

实现：

时间复杂度：

适用场景：图中存在负权边

SPFA 算法

从 BF 算法中我们可以观察这个条件：

何时才能更新 dist[b] 呢？当然是只有 dist[a] 发生变动的时候才能更新了。

SPFA 的思想也很简单，当一个点被更新的时候，才去更新它的所有出边。

这样就避免每次都遍历所有边尝试去更新最短距离了。

代码：

需要注意的地方是：st 记录的是点是否存在队列中，所以在入队的时候要标记st[j] = true ，而出队的时候要修改st[j] = false

时间复杂度：一般，最差

适用场景：存在负权边

负权回路

首先介绍一个概念，叫做负权回路，如下图所示

图中2，3，4组成了一个负权回路。

当负权回路处于源点和目标点的路径上时，必然无法求出最短路径。因为每经过一次负权回路，边权就-1。

对比BF算法和SPFA算法我们可以发现，上面这种情况发生的时候，BF算法迭代n次就停止，不会发生死循环，而SPFA会发生死循环。

对于这种情况，SPFA可以做一些改进，检测出是否有上面情况的存在。

具体做法是，使用cnt数组来记录经过的点数，如果到某个点经过点数≥n，那么根据抽屉原理，此时有n+1个点，但是最多图中有n个点，所以必然存在2个点相同，因此图中存在负权回路。

对比 SPFA 和堆优化 dijkstra

堆优化 dijkstra

思想：使用小根堆来存储最小距离的点，遍历它的所有出边，尝试优化 dist

时间复杂度：O(nlogm)

核心代码：

st的作用：标记是否被处理过

SPFA

思想：使用队列来存储被更新的点，优化它的所有出边

时间复杂度：O(n)，最差O(nm)

核心代码：

st的作用：标记是否存在队列中

可以发现上面两个版本的思想非常相似，区别仅仅在于：

堆优化dijkstra使用小根堆来保证弹出的点是目前距离最小的点，而SPFA只需要获得被更新过的点即可。

一般我们都可以用 SPFA 来解决单源最短路径问题，只有被卡的时候，才考虑堆优化版 dijkstra。

Floyd 算法

如果是要求任意两个点之间的最短路径的话，就考虑用 floyd 算法了，这个算法很暴力：

时间复杂度：O(n^3)

需要注意的是，先枚举中间点k，再枚举左右端点i和j

总结

单源最短路径：优先考虑SPFA，被卡再考虑堆优化版dijkstra

多源最短路径：Floyd

参考

AcWing 算法基础课