最短路径问题

作者:lucifer1004
链接:https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/solution/zui-duan-lu-jing-suan-fa-bfs0-1bfsdijkstra-by-luci/
来源: 力扣 (LeetCode)
著作权归作者所有. 商业转载请联系作者获得授权, 非商业转载请注明出处.

大佬写的题解就是不一样, 基于这个题目: 1368. 使网格图至少有一条有效路径的最小代价

我自己磕磕绊绊通过 BFS 做出来, 但是对整个全局的把握还是差了点

最短路径问题

所谓最短路径问题, 就是对于图 $G(V, E)$, 寻找从 $u\in V$ 到 $v\in V$ 的最短距离. 最短路径的算法有很多, 包括 Dijkstra, Floyd, Bellman-Ford, SPFA 等.

Dijkstra 算法

Dijkstra 算法是求取单源最短路径的常用算法, 其基本思想是每次用当前未拓展且具有最小权值的点来更新源点到其余顶点的距离. Dijkstra 算法的时间复杂度包含两个部分: 找到最小节点并将其移除的用时 $T_{extract\_min}$, 以及更新某一节点权值的用时 $T_{decrease\_key}$. 因为每个节点最多充当一次最小节点, 而每条边最多参与一次更新, 算法整体的时间复杂度可以表示为

$$
\Theta(V)\cdot T_{extract\_min}+\Theta(E)\cdot T_{decrease\_key}
$$

数据结构	$T_{extract\_min}$	$T_{decrease\_key}$	总时间复杂度
数组	$O(V)$	$O(1)$	$O(V^2+E)$
优先队列 (小根堆)	$O(\log V)$	$O(\log V)$	$O((V+E)\log V)$
Fibonacci 堆	均摊$O(\log V)$	均摊$O(1)$	均摊$O(V\log V + E)$

由于 Fibonacci 堆实现较为复杂, 各语言标准库未提供实现 (C++ 的 Boost 库实现了这一数据结构), 并且其实际运行效率与优先队列相比的优势并不明显, 所以基于优先队列的实现是 Dijkstra 算法最常见的实现方式.

需要注意的是, Dijkstra 算法在图中存在负环的情况下不适用! 对于无向图来说, 只要有一条负边, 就构成了一个两节点的负环, 所以在无向图中只要有负边就不能使用 Dijkstra 算法.

SPFA

如果一个节点已经在队列中, 其实就没有必要将其再次入队了. 这是 SPFA 算法的基本思想. 可以看到, 与上面的 BFS 方法相比, 就是增加了一个 $in$ 数组来判断当前节点是否已经在队列中.

SPFA 算法是一个十分依赖于数据的算法. 在特定的数据下, SPFA 会退化为 Bellman-Ford, 时间复杂度为 $O(V\cdot E)$. 一般的编程竞赛中, 涉及到最短路径的题目, 都会有专门卡 SPFA 的数据, 所以一般情况下还是使用 Dijkstra 算法. 本题的测试数据相对较弱, BFS 和 SPFA 都可以顺利通过, 甚至 SPFA 的运行时间还要长于 BFS(修改 $in$ 数组状态带来了额外的开销).

SPFA 的好处是可以判断负环. 我们可以用一个数组记录每个顶点的入队次数, 如果有顶点的入队次数超过了 $V$ 次, 则代表图中存在负环.