这哪里刷的是 LeetCode，刷的是打工人的人生啊！

大家好，我是吴师兄。

昨天训练营里面大家在聊天，突然有个同学发了下面这个图片。

不禁有些感慨：10 年前只要会写个快速排序就能进大厂，现在却要刷几百题才行，和图片主人公一样的遭遇， 这哪里刷的是 LeetCode，刷的是打工人的人生啊 ！

里面聊到了 KMP 算法和 RK 算法，和 BF 算法一起，三者都适用于字符串匹配。

KMP算法解决了字符串匹配问题中的一个核心挑战，即如何高效地在一个大文本中查找模式串的出现位置。通过预处理阶段构建next数组，KMP算法能够巧妙地利用之前匹配的信息，避免了不必要的重复比较，大幅提高了匹配效率。

这种通过记录部分匹配信息来加速算法的思想，在算法设计中十分常见。

实际上，类似的优化策略也在图论中的经典问题——最短路径问题中得到了应用。

图论中的最短路径问题涉及在一个图中寻找两个顶点之间的最短路径。

与字符串匹配问题不同，最短路径问题的输入是一组顶点和边，目标是找到一条花费最小的路径。

然而，与KMP算法利用之前的信息减少重复比较类似，许多最短路径算法同样依赖于某种形式的“信息累积”来提高计算效率。

例如，Dijkstra算法作为最短路径问题的代表性算法之一，依靠一种贪心策略，每次从当前未处理的节点中选择最短路径节点，并不断更新其他节点的最短路径信息。这样的做法确保了在每一步中，算法都在局部最优的基础上逐步逼近全局最优解，从而避免了对无效路径的重复计算。

Dijkstra算法和KMP算法虽然处理的是截然不同的领域，但它们的核心思想都在于如何通过精心设计的数据结构和步骤，使得问题的求解更加高效。这种利用历史信息或部分计算结果来减少重复工作的策略，在计算机科学中具有广泛的应用场景。

正如KMP算法通过next数组加速字符串匹配一样，Dijkstra算法通过优先队列等数据结构加速路径搜索，为我们展示了如何通过巧妙的算法设计来解决复杂问题。

最短路问题概述

最短路问题（Shortest Path Problem）是图论中一个经典的问题，旨在找到从一个顶点到另一个顶点的最短路径。

所给定的图可以是有向图（directed graph）也可以是无向图（undirected graph），并且边可以有权重（weights），即每条边有一个数值表示从一个顶点到另一个顶点的距离或成本。

最短路问题的常见变种包括：

1. 单源最短路径问题 ：找到从图中某个特定顶点到所有其他顶点的最短路径。
2. 单对最短路径问题 ：找到从图中某个特定顶点到另一个特定顶点的最短路径。
3. 全源最短路径问题 ：找到图中每对顶点之间的最短路径。

解决最短路问题通常有包含以下算法

1、Dijkstra算法：

• 定义 ：用于解决单源最短路径问题，适用于边权重非负的图。
• 原理 ：通过贪心策略，逐步选择具有最小估计距离的顶点，并更新其邻接顶点的距离。
• 时间复杂度 ：O((V + E) log V)，其中 V 是顶点数，E 是边数。

2、Bellman-Ford算法：

• 定义 ：用于解决单源最短路径问题，可以处理负权重的边。
• 原理 ：通过对所有边进行多次松弛操作，逐步逼近最短路径。
• 时间复杂度 ：O(VE)，其中 V 是顶点数，E 是边数。

3、Floyd算法：

• 定义 ：用于解决 全源最短路径问题 。
• 原理 ：通过动态规划的方式，逐步考虑每个顶点作为中间点，更新所有顶点对之间的最短路径。
• 时间复杂度 ：O(V^3)，其中 V 是顶点数。

本篇讲解主要介绍Dijkstra算法的原理以及应用

带非负边权的图的单源最短路径

对于以下无向图，我们能够看到图中包含了若干节点以及节点之间的边权

这里的边权可以简单理解为两个节点之间的距离

大部分题目（但不是绝对的）会用一个外层长度为 m ，内层长度为 3 的二维数组 edges ，来表无向图。

其中 m 是整个图的边数， edges[i] = [start_i, end_i, w_i] ，表示在第 i 条边中， start_i 节点和 end_i 节点之间的距离为 w_i 。

譬如，上述无向图可以用以下二维数组 edges 来表示

edges = [
[0, 1, 2],
[0, 4, 8],
[1, 2, 3],
[1, 4, 2],
[2, 3, 1],
[3, 4, 1]
]

有几点需要注意：

1. m = len(edges) = 6 是该无向图的边数
2. 边 edges[i] 在 edges 中的顺序并不重要
3. 对于无向图而言，每一条边的起点 start_i 和终点 end_i 的顺序也不重要
4. 如果是一个有向图，可能存在一条边的起点和终点互换则边权值不相等的情况出现（在实际生活中表现为两点之间的路径存在单行道、红灯停留时间等等）

假设我们现在需要一个储存数据的结构，通过该结构能够快速查询图中从 某个给定的源点出发 ，到任意一个点的最短距离，那么这个结构应该如何设计？

当我们想查询从源点到任意一个节点的最短距离，我们需要另一个节点的编号。因此容易想到直接构建一个一维数组或者哈希表。

假设这个给定的源点是节点 0 。

我们可以把这个一维数组或者一维哈希表称为 dist ，其中索引表示终点的节点编号。

dist 是 distance 的缩写

如果我们要查询源点 0 到任意一个节点 node 的最短路径，我们直接通过查找 dist[node] 的值就可以得到。

容易注意到数组或哈希表 dist 存在以下特点

1. 如果所有节点均连通，那么 dist 的长度为 n 。 n 为所有节点数。
2. 如果源点为 s ，那么存在 dist[s] = 0 成立，表示从节点 s 到节点 s 无需做任何移动，其最短距离为 0 。

Dijkstra算法解决单源最短路问题

截止到目前，我们已经知道，解决 单源最短路问题 ，要求我们得到的结果就是这个 dist 。

接下来努力的方向就是如何找到这个 dist 。

而Dijkstra算法就是基于贪心思想，通过多次选择下一个最近节点，找到这个 dist 的过程。

dist 数组初始化

由于我们需要根据迭代逐步获得 dist 数组的结果，显然可以将 dist 初始化为均为正无穷 inf 或者一个极大的数。

INF = 100000
dist = [INF] * n

贪心地进行 dist 数组迭代

以下图为例，假设已经知道 0->1 的最短路径是 2 。

那么下一步 我们要扩大从源点 0 出发能够到达的区域 ，我们会如何进行选择？

如果我们把 0 和 1 两个节点看作是一个 整体区域 ，那么下一步可以选择的边有 0->4 ， 1->4 ， 1->2 。

如果选择 0->4 ，那么到达 4 总花费的权重为 8 。

如果选择 1->4 ，那么到达 4 总花费的权重为 4 （除了从 1->4 本身的权重 2 ，还要算上 0->1 的权重 2 )。

如果选择 1->2 ，那么到达 2 总花费的权重为 5 （除了从 1->2 本身的权重 3 ，还要算上 0->1 的权重 2 )。

贪心地思考这个问题，我们有两个方向的考虑。

1. 如果是在 0->4 和 1->4 中选出一条边，我们一定会选择 1->4 ，因为这样可以使得到达节点 4 所花费的权重更低，这样符合最短路问题的定义。
2. 如果是在 1->4 和 1->2 中选出一条边，我们也一定会选择 1->4 ，因为我们并不清楚加上节点 4 之后，是否存在包含了节点 4 的路径能够使得从源点出发到 2 的路径更短。

举个例子：如果此时图中存在 4->2 这条边且其权重为 0 ，那么 0->1->4->2 的总花费为4，比 0->1->2 的总花费 5 要更低。

综上，我们发现选择 1->4 这条权重为 2 的边，能够扩大当前区域且使得到达节点 4 的路径是最短的。

所以我们可以考虑，制定这样的贪心策略。

当我们已经计算完毕 k 个节点的最短路，要进一步考虑第 k+1 个节点时，我们总是会 在未访问过的那 n-k 个节点中，选择到达后总花费权重最小的那个节点来作为扩大区域的节点 。

优先队列的引入

上述过程中，所谓 区域扩大 这件事情，实际上和BFS过程非常类似。

回忆BFS算法，我们用一个队列来维护该过程，队列中储存了若干尚未遍历过的节点。

如果从区域扩大的角度来思考BFS，在 while 循环中，我们每次都会弹出队列中的队头元素，来作为 当前节点 。

而当前节点的（尚未检查过的）近邻点，都会再次加入队列中。

Dijkstra算法也是类似。每一次扩大区域，纳入新的节点后，都会引入一些新的边。

换言之，我们需要用一个类似队列的结构， 来储存每一个新节点的近邻点的情况 。

那么，我们如何能够做到， 每一次扩大区域时，都能选出使得到达后总花费权重最小的节点呢 ？

很显然这里涉及到了一个优先级的问题，所以我们考虑 使用优先队列 （或者堆），来代替队列储存节点情况。

dist 数组完整迭代过程

考虑一个小根堆 heap ，堆中储存若干二元组 (time, node) ，表示从源点 s 出发，经过某些路径，到达 node 的路径花费为 time 。

显然，最开始的区域只包含源点 s ，所以我们可以这样初始化 heap 。

heap = [(0, s)]

以上述本文的例子为例， heap 中存入 (0, 0) 。

将堆顶元素 (0, 0) 弹出，考虑节点 0 的两个其近邻点 1 和 4 。

到达 1 所花费的权重为 0+2=2 ，将 (2, 1) 存入堆中。

到达 4 所花费的权重为 0+8=8 ，将 (8, 4) 存入堆中。

将堆顶元素 (2, 1) 弹出。表示到达节点 1 的最短路径为 2 。

显然，当我们进行扩大区域的节点选择时候，会贪心地选择节点 1 作为下一个节点。

我们修改 dist 数组中节点 1 对应的最短距离为 2 。

考虑节点 1 的两个近邻点 2 和 4 。由于到达节点 1 的最短路径为 2 。

经过 1 到达 2 所花费的权重为 2+3=5 ，将 (5, 2) 存入堆中。

经过 1 到达 4 所花费的权重为 2+2=4 ，将 (4, 4) 存入堆中。

将堆顶元素 (4, 4) 弹出。表示到达节点 4 的最短路径为 4 。

显然，当我们进行扩大区域的节点选择时候，会贪心地选择节点 4 作为下一个节点。

我们修改 dist 数组中节点 4 对应的最短距离为 4 。

考虑节点 4 的一个近邻点 3 。由于到达节点 4 的最短路径为 4 。

经过 4 到达 3 所花费的权重为 4+1=5 ，将 (5, 3) 存入堆中。

将堆顶元素 (5, 2) 弹出。表示到达节点 2 的最短路径为 5 。

在这一步中，到达节点 2 和节点 3 的距离均为 5 ，其实选择其中任意一个都是正确的。但由于我们小根堆中的元素是二元组，当第一个值 time 相等时，会根据第二个值 node 来进行大小排序。因此此处选择 (5, 2) 。

显然，当我们进行扩大区域的节点选择时候，会贪心地选择节点 2 作为下一个节点。

我们修改 dist 数组中节点 2 对应的最短距离为 5 。

考虑节点 2 的一个近邻点 3 。由于到达节点 2 的最短路径为 5 。

经过 2 到达 3 所花费的权重为 6+1=5 ，将 (6, 3) 存入堆中。

将堆顶元素 (5, 3) 弹出。表示到达节点 3 的最短路径为 5 。

我们修改 dist 数组中节点 3 对应的最短距离为 5 。

此时已经完成了所有节点的最短路径的计算。

节点 3 的引入没有带来更多新增的近邻节点，因此不再更新堆。

注意到，虽然已经找到了所有节点的最短路径，但此时堆中（可能）还存在一些元素。

但显然，由于我们使用小根堆维护上述过程， 每次都贪心地选择当前路径最短的节点来作为新的节点 。

因此堆中的元素中的路径长度，一定不会小于 dist 数组中的对应值。

剩余操作只需要将 heap 中的元素全部弹出即可。

类似BFS，我们可以写出如下的代码。

Dijkstra算法完整代码

Python

# 导入堆操作的库，heappush用于将元素压入堆中，heappop用于从堆中弹出最小元素
from heapq import heappush, heappop  
# 导入默认值字典，用于存储图的邻接表
from collections import defaultdict
# 设置一个非常大的值，表示尚未访问的节点距离  
INF = 100000  

# 构建使用Dijkstra算法计算从源点s出发到达其他所有点的最短路径数组
# s是源点，n是节点数量，edges是边列表，每个边由三元组(a, b, w)表示，表示a到b的权重为w
def Dijkstra(n, edges, s):
    # 初始化距离数组dist，将所有节点的初始距离设置为INF（无穷大）
    dist = [INF] * n  

    # 初始化邻接表，默认值为列表
    neighbor_dic = defaultdict(list)  

    # 构建邻接表，图中每个节点都与其邻居节点及边的权重进行关联
    for a, b, w in edges:
        # a -> b的边，权重为w
        neighbor_dic[a].append((b, w))  
        # 如果是无向图，b -> a的边，权重同样为w
        neighbor_dic[b].append((a, w))      # 如果是有向图，则这一行不需要写

    # 初始化堆，将源点s的距离（0）和源点加入堆中
    heap = [(0, s)]  
    
    # 进行Dijkstra算法过程，退出循环的条件为heap为空
    while heap:
        # 弹出堆中距离源点最近的节点及其距离
        cur_time, cur_node = heappop(heap)  

        # 如果当前节点的距离比记录的距离更大
        # 说明已经有更短的路径经过该节点，跳过该节点
        if cur_time > dist[cur_node]:
            continue

        # 更新当前节点的最短距离
        dist[cur_node] = cur_time  

        # 遍历当前节点的所有邻居节点
        for next_node, weight in neighbor_dic[cur_node]:
            next_time = cur_time + weight  # 计算从当前节点到邻居节点的距离
            # 如果从当前节点到邻居节点的距离比已知的最短距离更短，邻居节点加入堆中
            if next_time                 # 将更新后的距离和邻居节点压入堆中
                heappush(heap, (next_time, next_node))  

    return dist  # 返回从源点到所有节点的最短距离


# 初始化n和edges数组，以及源点s，可以自行进行修改和调整
n = 5

edges = [
[0, 1, 2],
[0, 4, 8],
[1, 2, 3],
[1, 4, 2],
[2, 3, 1],
[3, 4, 1]
]

s = 0

# 调用Dijkstra函数得到dist最小距离数组，输出结果
dist = Dijkstra(n, edges, s)
print(dist)

Java

import java.util.*;

// 构建使用Dijkstra算法计算从源点s出发到达其他所有点的最短路径数组
public class Dijkstra {

    static final int INF = 100000;  // 设置一个非常大的值，表示尚未访问的节点距离

    public static int[] dijkstra(int n, int[][] edges, int s) {
        // 初始化距离数组dist，将所有节点的初始距离设置为INF（无穷大）
        int[] dist = new int[n];
        Arrays.fill(dist, INF);

        // 初始化邻接表，默认值为ArrayList
        Mapint[]>> neighborDic = new HashMap<>();
        for (int i = 0; i             neighborDic.put(i, new ArrayList<>());
        }

        // 构建邻接表，图中每个节点都与其邻居节点及边的权重进行关联
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1], w = edge[2];
            // a -> b的边，权重为w
            neighborDic.get(a).add(new int[]{b, w});
            // 如果是无向图，b -> a的边，权重同样为w
            neighborDic.get(b).add(new int[]{a, w});  // 如果是有向图，则这一行不需要写
        }

        // 初始化优先队列，将源点s的距离（0）和源点加入队列
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        heap.offer(new int[]{0, s});

        // 进行Dijkstra算法过程，退出循环的条件为队列为空
        while (!heap.isEmpty()) {
            // 弹出队列中距离源点最近的节点及其距离
            int[] cur = heap.poll();
            int curTime = cur[0], curNode = cur[1];

            // 如果当前节点的距离比记录的距离更大
            // 说明已经有更短的路径经过该节点，跳过该节点
            if (curTime > dist[curNode]) {
                continue;
            }

            // 更新当前节点的最短距离
            dist[curNode] = curTime;

            // 遍历当前节点的所有邻居节点
            for (int[] neighbor : neighborDic.get(curNode)) {
                int nextNode = neighbor[0], weight = neighbor[1];
                int nextTime = curTime + weight;  // 计算从当前节点到邻居节点的距离

                // 如果从当前节点到邻居节点的距离比已知的最短距离更短，更新该距离并将邻居节点加入队列
                if (nextTime                     // 将更新后的距离和邻居节点压入队列
                    heap.offer(new int[]{nextTime, nextNode});
                }
            }
        }

        return dist;  // 返回从源点到所有节点的最短距离
    }

    public static void main(String[] args) {
        // 初始化n和edges数组，以及源点s，可以自行进行修改和调整
        int n = 5;

        int[][] edges = {
            {0, 1, 2},
            {0, 4, 8