10.8-10.15并查集-最短路径算法

本文最后更新于 2024年10月21日 早上

小记：Date：10\11 ,FRI , 重阳节。

晚上喝蛋白粉三勺喝不耐受了（头一次喝到腹泻呕吐的，呕吐那一下胃绞的是真疼），加上晚上也吃多了，再不敢这么喝了。又是发烧又是脱水md，下次记得常备海之盐及时补盐！主食记得吃小米粥、香蕉！

10.8

并查集理论基础

并查集常用来解决连通性问题。

大白话就是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。

并查集主要有两个功能：

  • 将两个元素添加到一个集合中。
  • 判断两个元素在不在同一个集合

原理讲解

从代码层面，我们如何将两个元素添加到同一个集合中呢。

此时有录友会想到：可以把他放到同一个数组里或者set或者map 中，这样就表述两个元素在同一个集合。

那么问题来了，对这些元素分门别类，可不止一个集合，可能是很多集合，成百上千，那么要定义这么多个数组吗？

有录友想，那可以定义一个二维数组。

但如果我们要判断两个元素是否在同一个集合里的时候 我们又能怎么办？只能把二维数组都遍历一遍。

而且每当想添加一个元素到某集合的时候，依然需要把把二维数组都遍历一遍，才知道要放在哪个集合里。

这仅仅是一个粗略的思路，如果沿着这个思路去实现代码，非常复杂，因为管理集合还需要很多逻辑。

那么我们来换一个思路来看看。

我们将三个元素A，B，C （分别是数字）放在同一个集合，其实就是将三个元素连通在一起，如何连通呢。

只需要用一个一维数组来表示，即：father[A] = B，father[B] = C 这样就表述 A 与 B 与 C连通了（有向连通图）。

代码如下：

1
2
3
4
5
6
7
// 将v，u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

可能有录友想，这样我可以知道 A 连通 B，因为 A 是索引下标，根据 father[A]的数值就知道 A 连通 B。那怎么知道 B 连通 A呢？

我们的目的是判断这三个元素是否在同一个集合里，知道 A 连通 B 就已经足够了。

这里要讲到寻根思路，只要 A ，B，C 在同一个根下就是同一个集合。

给出A元素，就可以通过father[A] = B，father[B] = C，找到根为 C。

给出B元素，就可以通过father[B] = C，找到根也为为 C，说明 A 和 B 是在同一个集合里。 大家会想第一段代码里find函数是如何实现的呢？其实就是通过数组下标找到数组元素，一层一层寻根过程，代码如下：

1
2
3
4
5
// 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u; // 如果根就是自己，直接返回
    else return find(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找
}

如何表示 C 也在同一个元素里呢？ 我们需要father[C] = C，即 C 的根也为C，这样就方便表示 A，B，C 都在同一个集合里了。

所以father数组初始化的时候要 father[i] = i，默认自己指向自己。

代码如下：

1
2
3
4
5
6
// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}

如何判断两个元素是否在同一个集合里，如果通过 find函数 找到 两个元素属于同一个根的话，那么这两个元素就是同一个集合，代码如下：

1
2
3
4
5
6
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

路径压缩

在实现 find 函数的过程中，我们知道，通过递归的方式，不断获取father数组下标对应的数值，最终找到这个集合的根。

搜索过程像是一个多叉树中从叶子到根节点的过程，如图：

img

如果这棵多叉树高度很深的话，每次find函数去寻找根的过程就要递归很多次。

我们的目的只需要知道这些节点在同一个根下就可以，所以对这棵多叉树的构造只需要这样就可以了，如图：

img

除了根节点其他所有节点都挂载根节点下，这样我们在寻根的时候就很快，只需要一步，

如果我们想达到这样的效果，就需要 路径压缩，将非根节点的所有节点直接指向根节点。 那么在代码层面如何实现呢？

我们只需要在递归的过程中，让 father[u]接住 递归函数find(father[u])的返回结果。

因为find函数向上寻找根节点，father[u] 表述 u 的父节点，那么让father[u]直接获取 find函数 返回的根节点，这样就让节点 u 的父节点 变成根节点。

代码如下，注意看注释，路径压缩就一行代码：

1
2
3
4
5
// 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u;
    else return father[u] = find(father[u]); // 路径压缩
}

以上代码在C++中，可以用三元表达式来精简一下，代码如下：

1
2
3
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}

相信不少录友在学习并查集的时候，对上面这三行代码实现的 find函数 很熟悉，但理解上却不够深入，仅仅知道这行代码很好用，不知道这里藏着路径压缩的过程。

所以对于算法初学者来说，直接看精简代码学习是不太友好的，往往忽略了很多细节。

代码模板

那么此时并查集的模板就出来了， 整体模板C++代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

通过模板，我们可以知道，并查集主要有三个功能。

  1. 寻根。函数：find(int u)，也就是判断这个节点的祖先节点是哪个
  2. 将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
  3. 判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点

常见误区

这里估计有录友会想，模板中的 join 函数里的这段代码：

1
2
3
u = find(u); // 寻找u的根
v = find(v); // 寻找v的根
if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回

与 isSame函数的实现是不是重复了？ 如果抽象一下呢，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    if (isSame(u, v)) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

这样写可以吗？ 好像看出去没问题，而且代码更精简了。

其实这么写是有问题的，在join函数中 我们需要寻找 u 和 v 的根，然后再进行连线在一起，而不是直接 用 u 和 v 连线在一起。

举一个例子：

1
2
join(1, 2);
join(3, 2);

此时构成的图是这样的：

img

此时问 1，3是否在同一个集合，我们调用 join(1, 2); join(3, 2); 很明显本意要表示 1，3是在同一个集合。

但我们来看一下代码逻辑，当我们调用 isSame(1, 3)的时候，find(1) 返回的是1，find(3)返回的是3。 return 1 == 3 返回的是false，代码告诉我们 1 和 3 不在同一个集合，这明显不符合我们的预期，所以问题出在哪里？

问题出在我们精简的代码上，即 join 函数 一定要先 通过find函数寻根再进行关联。

如果find函数是这么实现，再来看一下逻辑过程。

1
2
3
4
5
6
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

分别将这两对元素加入集合。

1
2
join(1, 2);
join(3, 2);

当执行join(3, 2)的时候，会先通过find函数寻找 3的根为3，2的根为1 （第一个join(1, 2)，将2的根设置为1），所以最后是将1 指向 3。

构成的图是这样的：

img

因为在join函数里，我们有find函数进行寻根的过程，这样就保证元素 1，2，3在这个有向图里是强连通的。

此时我们在调用 isSame(1, 3)的时候，find(1) 返回的是3，find(3) 返回的也是3，return 3 == 3 返回的是true，即告诉我们 元素 1 和 元素3 是 在同一个集合里的。

模拟过程

（凸显途径合并的过程，每一个join都要画图）

不少录友在接触并查集模板之后，用起来很娴熟，因为模板确实相对固定，但是对并查集内部数据组织方式以及如何判断是否是同一个集合的原理很模糊。

通过以上讲解之后，我再带大家一步一步去画一下，并查集内部数据连接方式。

1、join(1, 8);

img

2、join(3, 8);

img

有录友可能想，join(3, 8) 在图中为什么 将 元素1 连向元素 3 而不是将 元素 8 连向 元素 3 呢？

这一点 我在 「常见误区」标题下已经详细讲解了，因为在join(int u, int v)函数里 要分别对 u 和 v 寻根之后再进行关联。

3、join(1, 7);

img

4、join(8, 5);

img

这里8的根是3，那么 5 应该指向 8 的根 3，这里的原因，我们在上面「常见误区」已经讲过了。 但 为什么 图中 8 又直接指向了 3 了呢？

因为路经压缩了

即如下代码在寻找根的过程中，会有路径压缩，减少 下次查询的路径长度。

1
2
3
4
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

5、join(2, 9);

img

6、join(6, 9);

img

这里为什么是 2 指向了 6，因为 9的根为 2，所以用2指向6。

大家看懂这个有向图后，相信应该知道如下函数的返回值了。

1
2
cout << isSame(8, 7) << endl;
cout << isSame(7, 2) << endl;

返回值分别如下，表示，8 和 7 是同一个集合，而 7 和 2 不是同一个集合。

1
2
true
false

拓展

在「路径压缩」讲解中，我们知道如何靠压缩路径来缩短查询根节点的时间。

其实还有另一种方法：按秩（rank）合并。

rank表示树的高度，即树中结点层次的最大值。

例如两个集合（多叉树）需要合并，如图所示：

img

树1 rank 为2，树2 rank 为 3。那么合并两个集合，是 树1 合入 树2，还是 树2 合入 树1呢？

我们来看两个不同方式合入的效果。

img

这里可以看出，树2 合入 树1 会导致整棵树的高度变的更高，而 树1 合入 树2 整棵树的高度 和 树2 保持一致。

所以在 join函数中如何合并两棵树呢？

一定是 rank 小的树合入 到 rank大 的树，这样可以保证最后合成的树rank 最小，降低在树上查询的路径长度。

按秩合并的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构
vector<int> rank = vector<int> (n, 1); // 初始每棵树的高度都为1

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
        rank[i] = 1; // 也可以不写
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : find(father[u]);// 注意这里不做路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根

    if (rank[u] <= rank[v]) father[u] = v; // rank小的树合入到rank大的树
    else father[v] = u;

    if (rank[u] == rank[v] && u != v) rank[v]++; // 如果两棵树高度相同，则v的高度+1，因为上面 if (rank[u] <= rank[v]) father[u] = v; 注意是 <=
}

可以注意到在上面的模板代码中，我是没有做路径压缩的，因为一旦做路径压缩，rank记录的高度就不准了，根据rank来判断如何合并就没有意义。

也可以在 路径压缩的时候，再去实时修生rank的数值，但这样在代码实现上麻烦了不少，关键是收益很小。

其实我们在优化并查集查询效率的时候，只用路径压缩的思路就够了，不仅代码实现精简，而且效率足够高。

按秩合并的思路并没有将树形结构尽可能的扁平化，所以在整理效率上是没有路径压缩高的。

说到这里可能有录友会想，那在路径压缩的代码中，只有查询的过程 即 find 函数的执行过程中会有路径压缩，如果一直没有使用find函数，是不是相当于这棵树就没有路径压缩，导致查询效率依然很低呢？

大家可以再去回顾使用路径压缩的 并查集模板，在isSame函数 和join函数中，我们都调用了 find 函数来进行寻根操作。

也就是说，无论使用并查集模板里哪一个函数（除了init函数），都会有路径压缩的过程，第二次访问相同节点的时候，这个节点就是直连根节点的，即 第一次访问的时候它的路径就被压缩了。

所以这里推荐大家直接使用路径压缩的并查集模板就好，但按秩合并的优化思路我依然给大家讲清楚，有助于更深一步理解并查集的优化过程。

复杂度分析

这里对路径压缩版并查集来做分析。

空间复杂度：O(n) ，申请一个father数组。

关于时间复杂度，如果想精确表达出来需要繁琐的数学证明，就不在本篇讲解范围内了，大家感兴趣可以自己去深入研究。

这里做一个简单的分析思路。

路径压缩后的并查集时间复杂度在O(logn)与O(1)之间，且随着查询或者合并操作的增加，时间复杂度会越来越趋于O(1)。

了解到这个程度对于求职面试来说就够了。

在第一次查询的时候，相当于是n叉树上从叶子节点到根节点的查询过程，时间复杂度是logn，但路径压缩后，后面的查询操作都是O(1)，而join 函数 和isSame函数 里涉及的查询操作也是一样的过程。

107. 寻找存在的路径

题目描述

给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。

你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。

输入描述

第一行包含两个正整数 N 和 M，N 代表节点的个数，M 代表边的个数。

后续 M 行，每行两个正整数 s 和 t，代表从节点 s 与节点 t 之间有一条边。

最后一行包含两个正整数，代表起始节点 source 和目标节点 destination。

输出描述

输出一个整数，代表是否存在从节点 source 到节点 destination 的路径。如果存在，输出 1；否则，输出 0。

输入示例
1
2
3
4
5
6
5 4
1 2
1 3
2 4
3 4
1 4
输出示例
1
1
提示信息

img

数据范围：

1 <= M, N <= 100。

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

套入本题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
using namespace std;

//int n; // 节点数量
//vector<int> father = vector<int> (101, 0); // 按照节点大小定义数组大小

vector<int> father = vector<int>(105 , 0);

// 并查集初始化
void init() {
    for (int i = 1; i <= n; i++)  father[i] = i;
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

int main(){
    int N , M , s , t,  a , b;
    cin >> N >> M;
    init();
    while(M --){
        cin >> s >> t;
        join(s , t);
    }
    cin >> a >> b;
    if (isSame(a , b))  cout << 1;
    else  cout << 0;
    
    return 0;
}

本题错误原因：忘记init()，在输入N ，M后应立即初始化。

108. 冗余连接

题目描述

有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（其实就是一个线形图），如图：

img

现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图：

img

先请你找出冗余边，删除后，使该图可以重新变成一棵树。

输入描述

第一行包含一个整数 N，表示图的节点个数和边的个数。

后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

输出描述

输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

输入示例
1
2
3
4
3
1 2
2 3
1 3
输出示例
1
1 3
提示信息

img

图中的 1 2，2 3，1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边，所以输出结果为 1 3

数据范围：

1 <= N <= 1000.

思路：

题目说是无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树（即：只有一个根节点）。

如果有多个答案，则返回二维数组中最后出现的边。

那么我们就可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。

如图所示，节点 a 和节点 b 不在同一个集合，那么就可以将两个 节点连在一起。

img

如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。

如图所示：

img

已经判断 节点 a 和 节点 b 在在同一个集合（同一个根），如果将 节点 a 和 节点 b 连在一起就一定会出现环。

这个思路清晰之后，代码就很好写了。

并查集C++代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<vector>

using namespace std;

vector<int> father = vector<int>(1005 , 0);

void init(){
  for (int i = 0; i < 1005; i++) {
     father[i] = i;
  }
}

int find(int u){
  return u == father[u] ? u : father[u] = find(father[u]);
}

//v -> u
void join(int u , int v){
  u = find(u);
  v = find(v);
  if(u == v)  return;
  father[v] = u;
}

bool isSame(int u , int v){
  u = find(u);
  v = find(v);
  return u == v;
}

int main(){
    int N , s , t;
    cin >> N;
    init();
    while(N --){
        cin >> s >> t;
        if (isSame(s , t))  cout << s << " "<< t;
        else join(s , t);
    }
    return 0;
}

误区

题目要求 “请删除标准输入中最后出现的那条边” ，不少录友疑惑，这代码分明是遇到在同一个根的两个节点立刻就返回了，怎么就求出 最后出现的那条边 了呢。

有这种疑惑的录友是 认为发现一条冗余边后，后面还可能会有一条冗余边。

其实并不会。

题目是在 树的基础上 添加一条边，所以冗余边仅仅是一条。

到这一条可能靠前出现，可能靠后出现。

例如，题目输入示例：

输入示例

1
2
3
4
3
1 2
2 3
1 3

图：

img

输出示例

1 3

当我们从前向后遍历，优先让前面的边连上，最后判断冗余边就是 1 3。

如果我们从后向前便利，优先让后面的边连上，最后判断的冗余边就是 1 2。

题目要求“请删除标准输入中最后出现的那条边”，所以 1 3 这条边才是我们要求的。

H：109. 冗余连接II

题目描述

有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图：

img

现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：

img

输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。

输入描述

第一行输入一个整数 N，表示有向图中节点和边的个数。

后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边

输出描述

输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。

输入示例
1
2
3
4
3
1 2
1 3
2 3
输出示例
1
2 3
提示信息

img

在删除 2 3 后有向图可以变为一棵合法的有向树，所以输出 2 3

数据范围：

1 <= N <= 1000.

思路

本题与 108.冗余连接 类似，但本题是一个有向图，有向图相对要复杂一些。

本题的本质是 ：有一个有向图，是由一颗有向树 + 一条有向边组成的 （所以此时这个图就不能称之为有向树），现在让我们找到那条边 把这条边删了，让这个图恢复为有向树。

还有“若有多条边可以删除，请输出标准输入中最后出现的一条边”，这说明在两条边都可以删除的情况下，要删顺序靠后的边！

我们来想一下 有向树的性质，如果是有向树的话，只有根节点入度为0，其他节点入度都为1（因为该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点）。

所以情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了。

如图：

img

找到了节点3 的入度为2，删 1 -> 3 或者 2 -> 3 。选择删顺序靠后便可。但入度为2 还有一种情况

情况二，只能删特定的一条边，如图：

img

节点3 的入度为 2，但在删除边的时候，只能删 这条边（节点1 -> 节点3），如果删这条边（节点4 -> 节点3），那么删后本图也不是有向树了（因为找不到根节点）。

综上，如果发现入度为2的节点，我们需要判断 删除哪一条边，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边。

情况三： 如果没有入度为2的点，说明 图中有环了（注意是有向环）。

如图：

img

对于情况三，删掉构成环的边就可以了。

代码

把每条边记录下来，并统计节点入度：

1
2
3
4
5
6
7
8
9
int s, t;
vector<vector<int>> edges;
cin >> n;
vector<int> inDegree(n + 1, 0); // 记录节点入度
for (int i = 0; i < n; i++) {
    cin >> s >> t;
    inDegree[t]++;
    edges.push_back({s, t});
}

前两种入度为2的情况，一定是删除指向入度为2的节点的两条边其中的一条，如果删了一条，判断这个图是一个树，那么这条边就是答案。

同时注意要从后向前遍历，因为如果两条边删哪一条都可以成为树，就删最后那一条。

说明：edges 是一个 vector>，其中每个edges[i] 是一个包含两个整数的向量 {s, t}，分别表示从节点 s 指向节点 t 的一条边。

  • edges[i][0] 表示起点 s。
  • edges[i][1] 表示终点 t。

例如：如果你输入的边是 (2, 3)，那么 edges[i][1] 的值就是 3,egdes[i] [0] = 2

如果 vec.size() > 0，意味着有至少一个入度为2的边。会首先尝试删除 vec[0] 对应的边（即倒序查找的最后一条入度为2的边）。

如果删除 vec[0] 后图变成树（isTreeAfterRemoveEdge 返回 true），那么就输出 vec[0] 对应的边。

如果删除 vec[0] 不行，则尝试删除 vec[1]，输出第二条入度为2的边。

因为n个节点n条边，入度为2 的边只可能为0 ，1 ， 2条。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
// 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边。

for (int i = n - 1; i >= 0; i--) {
    if (inDegree[edges[i][1]] == 2) {
        vec.push_back(i);//储存的是边的起点
    }
}
if (vec.size() > 0) {
    // 放在vec里的边已经按照倒序放的，所以这里就优先删vec[0]这条边
    if (isTreeAfterRemoveEdge(edges, vec[0])) {
        cout << edges[vec[0]][0] << " " << edges[vec[0]][1];
    } else {
        cout << edges[vec[1]][0] << " " << edges[vec[1]][1];
    }
    return 0;
}

再来看情况三，明确没有入度为2的情况，那么一定有向环，找到构成环的边就是要删除的边。

可以定义一个函数，代码如下：

1
2
// 在有向图里找到删除的那条边，使其变成树 
void getRemoveEdge(const vector<vector<int>>& edges)

大家应该知道了，我们要解决本题要实现两个最为关键的函数：

  • isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树
  • getRemoveEdge() 确定图中一定有了有向环，那么要找到需要删除的那条边

此时就用到并查集了。

isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树： 将所有边的两端节点分别加入并查集，遇到要删除的边则跳过，如果遇到即将加入并查集的边的两端节点本来就在并查集了，说明构成了环。

如果顺利将所有边的两端节点（除了要删除的边）加入了并查集，则说明 删除该条边 还是一个有向树。

getRemoveEdge()确定图中一定有了有向环，那么要找到需要删除的那条边： 将所有边的两端节点分别加入并查集，如果遇到即将加入并查集的边的两端节点 本来就在并查集了，说明构成了环。

本题C++代码如下：（详细注释了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> father (1001, 0);
// 并查集初始化
void init() {
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return ;
    father[v] = u;
}
// 判断 u 和 v是否找到同一个根
bool same(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 在有向图里找到删除的那条边，使其变成树
void getRemoveEdge(const vector<vector<int>>& edges) {
    init(); // 初始化并查集
    for (int i = 0; i < n; i++) { // 遍历所有的边
        if (same(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
            cout << edges[i][0] << " " << edges[i][1];
            return;
        } else {
            join(edges[i][0], edges[i][1]);
        }
    }
}

// 删一条边之后判断是不是树
bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {
    init(); // 初始化并查集
    for (int i = 0; i < n; i++) {
        if (i == deleteEdge) continue;
        if (same(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
            return false;
        }
        join(edges[i][0], edges[i][1]);
    }
    return true;
}

int main() {
    int s, t;
    vector<vector<int>> edges;
    cin >> n;
    vector<int> inDegree(n + 1, 0); // 记录节点入度
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        inDegree[t]++;
        edges.push_back({s, t});
    }

    vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
    // 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边
    for (int i = n - 1; i >= 0; i--) {
        if (inDegree[edges[i][1]] == 2) {
            vec.push_back(i);
        }
    }
    // 情况一、情况二
    if (vec.size() > 0) {
        // 放在vec里的边已经按照倒叙放的，所以这里就优先删vec[0]这条边
        if (isTreeAfterRemoveEdge(edges, vec[0])) {
            cout << edges[vec[0]][0] << " " << edges[vec[0]][1];
        } else {
            cout << edges[vec[1]][0] << " " << edges[vec[1]][1];
        }
        return 0;
    }

    // 处理情况三
    // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
    getRemoveEdge(edges);
}

10/9

prim算法精讲

题目描述

在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。

不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。

给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。

输入描述

第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。

接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。

输出描述

输出联通所有岛屿的最小路径总距离

输入示例
1
2
3
4
5
6
7
8
9
10
11
12
7 11
1 2 1
1 3 1
1 5 2
2 6 1
2 4 2
2 3 2
3 4 1
4 5 1
5 6 2
5 7 1
6 7 1
输出示例
1
6
提示信息

数据范围：
2 <= V <= 10000;
1 <= E <= 100000;
0 <= val <= 10000;

如下图，可见将所有的顶点都访问一遍，总距离最低是6.

img

本题是最小生成树的模板题，那么我们来讲一讲最小生成树。

最小生成树 可以使用prim算法 也可以使用kruskal算法计算出来。

最小生成树是所有节点的最小连通子图， 即：以最小的成本（边的权值）将图中所有节点链接到一起。

图中有n个节点，那么一定可以用 n - 1 条边将所有节点连接到一起。

那么如何选择 这 n-1 条边 就是 最小生成树算法的任务所在。

例如本题示例中的无向有权图为：

img

那么在这个图中，如何选取 n-1 条边 使得 图中所有节点连接到一起，并且边的权值和最小呢？

（图中为n为7，即7个节点，那么只需要 n-1 即 6条边就可以讲所有顶点连接到一起）

prim算法 是从节点的角度 采用贪心的策略 :每次寻找距离 最小生成树最近的节点 并加入到最小生成树中。

prim算法核心就是三步，我称为prim三部曲，大家一定要熟悉这三步，代码相对会好些很多：

  1. 选距离生成树最近节点
  2. 最近节点加入生成树
  3. 更新非生成树节点到生成树的距离（即更新minDist数组）

现在录友们会对这三步很陌生，不知道这是干啥的，没关系，下面将会画图举例来带大家把这prim三部曲理解到位。

在prim算法中，有一个数组特别重要，这里我起名为：minDist。

刚刚我有讲过 “每次寻找距离 最小生成树最近的节点 并加入到最小生成树中”，那么如何寻找距离最小生成树最近的节点呢？这就用到了 minDist 数组， 它用来作什么呢？

minDist数组 用来记录 每一个节点距离最小生成树的最近距离。 理解这一点非常重要，这也是 prim算法最核心要点所在，很多录友看不懂prim算法的代码，都是因为没有理解透 这个数组的含义。

接下来，我们来通过一步一步画图，来带大家巩固 prim三部曲 以及 minDist数组 的作用。

（示例中节点编号是从1开始，所以为了让大家看的不晕，minDist数组下标我也从 1 开始计数，下标0 就不使用了，这样 下标和节点标号就可以对应上了，避免大家搞混）

初始状态

minDist 数组 里的数值初始化为 最大数，因为本题 节点距离不会超过 10000，所以 初始化最大数为 10001就可以。

相信这里录友就要问了，为什么这么做？

现在 还没有最小生成树，默认每个节点距离最小生成树是最大的，这样后面我们在比较的时候，发现更近的距离，才能更新到 `minDist `数组上。

如图：

img

开始构造最小生成树

1、第一步：选距离生成树最近节点

选择距离最小生成树最近的节点，加入到最小生成树，刚开始还没有最小生成树，所以随便选一个节点加入就好（因为每一个节点一定会在最小生成树里，所以随便选一个就好），那我们选择节点1 （符合遍历数组的习惯，第一个遍历的也是节点1）

2、第二步：最近节点加入生成树

此时 节点1 已经算最小生成树的节点。

3、第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

接下来，我们要更新所有节点距离最小生成树的距离，如图：

img

注意下标0，我们就不管它了，下标 1 与节点 1 对应，这样可以避免大家把节点搞混。

此时所有非生成树的节点距离 最小生成树（节点1）的距离都已经跟新了 。

  • 节点2 与 节点1 的距离为1，比原先的 距离值10001小，所以更新`minDist[2]`。
  • 节点3 和 节点1 的距离为1，比原先的 距离值10001小，所以更新`minDist[3]`。
  • 节点5 和 节点1 的距离为2，比原先的 距离值10001小，所以更新`minDist[5]`。

注意图中我标记了minDist``数组里更新的权值，是哪两个节点之间的权值，例如`minDist[2] =1 `，这个 1 是 节点1 与 节点2 之间的连线，清楚这一点对最后我们记录 最小生成树的权值总和很重要。

（我在后面依然会不断重复 prim三部曲，可能基础好的录友会感觉有点啰嗦，但也是让大家感觉这三部曲求解的过程）

继续更新

1、prim三部曲，第一步：选距离生成树最近节点

选取一个距离 最小生成树（节点1） 最近的非生成树里的节点，节点2，3，5 距离 最小生成树（节点1） 最近，选节点 2（其实选 节点3或者节点2都可以，距离一样的）加入最小生成树。

2、prim三部曲，第二步：最近节点加入生成树

此时 节点1 和 节点2，已经算最小生成树的节点。

3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

接下来，我们要更新节点距离最小生成树的距离，如图：

img

此时所有非生成树的节点距离 最小生成树（节点1、节点2）的距离都已经跟新了 。

  • 节点3 和 节点2 的距离为2，和原先的距离值1 小，所以不用更新。
  • 节点4 和 节点2 的距离为2，比原先的距离值10001小，所以更新`minDist[4]`。
  • 节点5 和 节点2 的距离为10001（不连接），所以不用更新。
  • 节点6 和 节点2 的距离为1，比原先的距离值10001小，所以更新`minDist[6]`。

继续

1、prim三部曲，第一步：选距离生成树最近节点

选择一个距离 最小生成树（节点1、节点2） 最近的非生成树里的节点，节点3，6 距离 最小生成树（节点1、节点2） 最近，选节点3 （选节点6也可以，距离一样）加入最小生成树。

2、prim三部曲，第二步：最近节点加入生成树

此时 节点1 、节点2 、节点3 算是最小生成树的节点。

3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

接下来更新节点距离最小生成树的距离，如图：

img

所有非生成树的节点距离 最小生成树（节点1、节点2、节点3 ）的距离都已经跟新了 。

  • 节点 4 和 节点 3的距离为 1，和原先的距离值 2 小，所以更新minDist[4]为1。

上面为什么我们只比较 节点4 和 节点3 的距离呢？

因为节点3加入 最小生成树后，非生成树节点 只有 节点 4 和 节点3是链接的，所以需要重新更新一下 节点4距离最小生成树的距离，其他节点距离最小生成树的距离 都不变。

继续

1、prim三部曲，第一步：选距离生成树最近节点

继续选择一个距离 最小生成树（节点1、节点2、节点3） 最近的非生成树里的节点，为了巩固大家对 minDist数组的理解，这里我再啰嗦一遍：

img

从数组里我们能看出来，非生成树节点 4 和 节点 6 距离 生成树最近。

任选一个加入生成树，我们选 节点4（选节点6也行） 。

注意，我们根据 minDist数组，选取距离 生成树 最近的节点 加入生成树，那么 minDist数组里记录的其实也是 最小生成树的边的权值（我在图中把权值对应的是哪两个节点也标记出来了）。

如果大家不理解，可以跟着我们下面的讲解，看 minDist数组的变化， minDist数组 里记录的权值对应的哪条边。

理解这一点很重要，因为 最后我们要求 最小生成树里所有边的权值和。

2、prim三部曲，第二步：最近节点加入生成树

此时 节点1、节点2、节点3、节点4 算是 最小生成树的节点。

3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

接下来更新节点距离最小生成树的距离，如图：

img

minDist数组已经更新了 所有非生成树的节点距离 最小生成树（节点1、节点2、节点3、节点4 ）的距离 。

  • 节点 5 和 节点 4的距离为 1，和原先的距离值 2 小，所以更新minDist[5]为1。

继续

1、prim三部曲，第一步：选距离生成树最近节点

继续选距离 最小生成树（节点1、节点2、节点3、节点4 ）最近的非生成树里的节点，只有 节点 5 和 节点6。

选节点5 （选节点6也可以）加入 生成树。

2、prim三部曲，第二步：最近节点加入生成树

节点1、节点2、节点3、节点4、节点5 算是 最小生成树的节点。

3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

接下来更新节点距离最小生成树的距离，如图：

img

minDist数组已经更新了 所有非生成树的节点距离 最小生成树（节点1、节点2、节点3、节点4 、节点5）的距离 。

  • 节点 6 和 节点 5 距离为 2，比原先的距离值 1 大，所以不更新
  • 节点 7 和 节点 5 距离为 1，比原先的距离值 10001小，更新 minDist[7]

最后一步

1、prim三部曲，第一步：选距离生成树最近节点

继续选距离 最小生成树（节点1、节点2、节点3、节点4 、节点5）最近的非生成树里的节点，只有 节点 6 和 节点7。

2、prim三部曲，第二步：最近节点加入生成树

选节点6 （选节点7也行，距离一样的）加入生成树。

3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

节点1、节点2、节点3、节点4、节点5、节点6 算是 最小生成树的节点 ，接下来更新节点距离最小生成树的距离，如图：

img

这里就不在重复描述了，大家类推，最后，节点7加入生成树，如图：

img

最后

最后我们就生成了一个 最小生成树， 绿色的边将所有节点链接到一起，并且 保证权值是最小的，因为我们在更新 minDist 数组的时候，都是选距离 最小生成树最近的点 加入到树中。

讲解上面的模拟过程的时候，我已经强调多次minDist``数组 是记录了 所有非生成树节点距离生成树的最小距离。

最后，minDist数组 也就是记录的是最小生成树所有边的权值。

我在图中，特别把 每条边的权值对应的是哪两个节点 标记出来（例如minDist`[7] = 1`，对应的是节点5 和 节点7之间的边，而不是节点6和节点7），为了就是让大家清楚，minDist``里的每一个值 对应的是哪条边。

那么我们要求最小生成树里边的权值总和 就是 把 最后的`minDist `数组 累加一起。

以下代码，我对 prim三部曲，做了重点注释，大家根据这三步，就可以 透彻理解prim。

注：<climits> 是 C++ 标准库中的一个头文件，提供了与整数类型相关的限制和特性。它定义了一组常量，描述了各种整数类型（如 char、int、long 等）的最小值、最大值和其他相关属性。这些常量来自 C 标准库的 <limits.h> 头文件。

程序中用到了INT_MAX：int 类型的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<vector>
#include <climits>

using namespace std;
int main() {
    int v, e;
    int x, y, k;
    cin >> v >> e;
    // 填一个默认最大值，题目描述val最大为10000
    vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));
    while (e--) {
        cin >> x >> y >> k;
        // 因为是双向图，所以两个方向都要填上
        grid[x][y] = k;
        grid[y][x] = k;

    }
    // 所有节点到最小生成树的最小距离
    vector<int> `minDist`(v + 1, 10001);

    // 这个节点是否在树里
    vector<bool> isInTree(v + 1, false);

    // 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起
    for (int i = 1; i < v; i++) {

        // 1、prim三部曲，第一步：选距离生成树最近节点
        int cur = -1; // 选中哪个节点 加入最小生成树
        int minVal = INT_MAX;
        for (int j = 1; j <= v; j++) { // 1 - v，顶点编号，这里下标从1开始
            //  选取最小生成树节点的条件：
            //  （1）不在最小生成树里
            //  （2）距离最小生成树最近的节点
            if (!isInTree[j] &&  `minDist`[j] < minVal) {
                minVal = `minDist`[j];
                cur = j;
            }
        }
        // 2、prim三部曲，第二步：最近节点（cur）加入生成树
        isInTree[cur] = true;

        // 3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新`minDist`数组）
        // cur节点加入之后， 最小生成树加入了新的节点，那么所有节点到 最小生成树的距离（即`minDist`数组）需要更新一下
        // 由于cur节点是新加入到最小生成树，那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢
        for (int j = 1; j <= v; j++) {
            // 更新的条件：
            // （1）节点是 非生成树里的节点
            // （2）与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小
            // 很多录友看到自己 就想不明白什么意思，其实就是 cur 是新加入 最小生成树的节点，那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入，需要更新一下数据了
            if (!isInTree[j] && grid[cur][j] < `minDist`[j]) {
                `minDist`[j] = grid[cur][j];
            }
        }
    }
    // 统计结果
    int result = 0;
    for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边
        result += `minDist`[i];
    }
    cout << result << endl;

}

时间复杂度为 O(n^2)，其中 n 为节点数量。

拓展

上面讲解的是记录了最小生成树 所有边的权值，如果让打印出来 最小生成树的每条边呢？ 或者说 要把这个最小生成树画出来呢？

此时我们就需要把 最小生成树里每一条边记录下来。

此时有两个问题：

  1. 用什么结构来记录
  2. 如何记录

如果记录边，其实就是记录两个节点就可以，两个节点连成一条边。

如何记录两个节点呢？

我们使用一维数组就可以记录。parent[节点编号] = 节点编号， 这样就把一条边记录下来了。（当然如果节点编号非常大，可以考虑使用map）

使用一维数组记录是有向边，不过我们这里不需要记录方向，所以只关注两条边是连接的就行。

parent数组初始化代码：

1
vector<int> parent(v + 1, -1);

接下来就是第二个问题，如何记录？

我们再来回顾一下 prim三部曲，

  1. 第一步，选距离生成树最近节点
  2. 第二步，最近节点加入生成树
  3. 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

大家先思考一下，我们是在第几步，可以记录 最小生成树的边呢？

在本面上半篇 我们讲解过：“我们根据 minDist数组，选组距离 生成树 最近的节点 加入生成树，那么 minDist数组里记录的其实也是 最小生成树的边的权值。”

既然 minDist数组 记录了 最小生成树的边，是不是就是在更新 minDist数组 的时候，去更新parent数组来记录一下对应的边呢。

所以 在 prim三部曲中的第三步，更新 parent数组，代码如下：

1
2
3
4
5
6
for (int j = 1; j <= v; j++) {
    if (!isInTree[j] && grid[cur][j] < `minDist`[j]) {
        `minDist`[j] = grid[cur][j];
        parent[j] = cur; // 记录最小生成树的边 （注意数组指向的顺序很重要）
    }
}

代码中注释中，我强调了 数组指向的顺序很重要。 因为不少录友在这里会写成这样： parent[cur] = j 。

这里估计大家会疑惑了，parent[节点编号A] = 节点编号B， 就表示A 和 B 相连，我们这里就不用在意方向，代码中 为什么 只能 parent[j] = cur 而不能 parent[cur] = j 这么写呢？

如果写成 parent[cur] = j，在 for 循环中，有多个 j 满足要求， 那么parent[cur]就会被反复覆盖，因为 cur 是一个固定值。

举个例子，cur = 1， 在 for循环中，可能 就 j = 2， j = 3，j =4 都符合条件，那么本来应该记录 节点1 与 节点 2、节点3、节点4相连的。

如果 parent[cur] = j 这么写，最后更新的逻辑是 parent[1] = 2, parent[1] = 3， parent[1] = 4， 最后只能记录 节点1 与节点 4 相连，其他相连情况都被覆盖了。

如果这么写 parent[j] = cur， 那就是 parent[2] = 1, parent[3] = 1， parent[4] = 1 ，这样 才能完整表示出 节点1 与 其他节点都是链接的，才没有被覆盖。

主要问题也是我们使用了一维数组来记录。

如果是二维数组，来记录两个点链接，例如 parent[节点编号A] [节点编号B] = 1 ，parent[节点编号B] [节点编号A] = 1，来表示 节点A 与 节点B 相连，那就没有上面说的这个注意事项了，当然这么做的话，就是多开辟的内存空间。

以下是输出最小生成树边的代码，不算最后输出， 就额外添加了两行代码，我都注释标记了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<vector>
#include <climits>

using namespace std;
int main() {
    int v, e;
    int x, y, k;
    cin >> v >> e;
    vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));
    while (e--) {
        cin >> x >> y >> k;
        grid[x][y] = k;
        grid[y][x] = k;
    }

    vector<int> `minDist`(v + 1, 10001);
    vector<bool> isInTree(v + 1, false);

    //加上初始化
    vector<int> parent(v + 1, -1);

    for (int i = 1; i < v; i++) {
        int cur = -1;
        int minVal = INT_MAX;
        for (int j = 1; j <= v; j++) {
            if (!isInTree[j] &&  `minDist`[j] < minVal) {
                minVal = `minDist`[j];
                cur = j;
            }
        }

        isInTree[cur] = true;
        for (int j = 1; j <= v; j++) {
            if (!isInTree[j] && grid[cur][j] < `minDist`[j]) {
                `minDist`[j] = grid[cur][j];

                parent[j] = cur; // 记录边
            }
        }
    }
    // 输出 最小生成树边的链接情况
    for (int i = 1; i <= v; i++) {
        cout << i << "->" << parent[i] << endl;
    }
}

按照本题示例，代码输入如下：

1
2
3
4
5
6
7
1->-1
2->1
3->1
4->3
5->4
6->2
7->5

注意，这里是无向图，我在输出上添加了箭头仅仅是为了方便大家看出是边的意思。

大家可以和我们本题最后生成的最小生成树的图 去对比一下 边的链接情况：

img

绿色的边 是最小生成树，和我们的 输出完全一致。

总结

此时我就把prim算法讲解完毕了，我们再来回顾一下。

关于 prim算法，我自创了三部曲，来帮助大家理解：

  1. 选距离生成树最近节点
  2. 最近节点加入生成树
  3. 更新非生成树节点到生成树的距离（即更新minDist数组）

大家只要理解这三部曲， prim算法 至少是可以写出一个框架出来，然后在慢慢补充细节，这样不至于 自己在写prim的时候 两眼一抹黑 完全凭感觉去写。 这也为什么很多录友感觉 prim算法比较难，而且每次学会来，隔一段时间 又不会写了，主要是 没有一个纲领。

理解这三部曲之后，更重要的 就是理解minDist``数组。

minDist数组 是prim算法的灵魂，它帮助 prim算法完成最重要的一步，就是如何找到 距离最小生成树最近的点。

再来帮大家回顾minDist``数组 的含义：记录 每一个节点距离最小生成树的最近距离。

理解 minDist数组 ，至少大家看prim算法的代码不会懵。

也正是 因为 minDist数组 的作用，我们根据 minDist数组，选取距离 生成树 最近的节点 加入生成树，那么 minDist数组里记录的其实也是 最小生成树的边的权值。

所以我们求 最小生成树的权值和 就是 计算后的 minDist数组数值总和。

最后我们拓展了如何求 最小生成树 的每一条边，其实 添加的代码很简单，主要是理解 为什么使用 parent数组 来记录边 以及 在哪里 更新parent数组。

同时，因为使用一维数组，数组的下标和数组 如何赋值很重要，不要搞反，导致结果被覆盖。

kruskal算法精讲

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。

kruscal的思路：

  • 边的权值排序，因为要优先选最小的边加入到生成树里
  • 遍历排序后的边
    • 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
    • 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

下面我们画图举例说明kruscal的工作过程。

依然以示例中，如下这个图来举例。

img

将图中的边按照权值有小到大排序，这样从贪心的角度来说，优先选 权值小的边加入到 最小生成树中。

排序后的边顺序为[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]

(1,2) 表示节点1 与 节点2 之间的边。权值相同的边，先后顺序无所谓。

开始从头遍历排序后的边。

  1. 选边(1,2)，节点1 和 节点2不在同一个集合，所以生成树可以添加边(1,2)，并将 节点1，节点2 放在同一个集合。

img

  1. 选边(4,5)，节点4 和 节点 5 不在同一个集合，生成树可以添加边(4,5) ，并将节点4，节点5 放到同一个集合。

img

大家判断两个节点是否在同一个集合，就看图中两个节点是否有绿色的粗线连着就行

（这里在强调一下，以下选边是按照上面排序好的边的数组来选择的）

  1. 选边(1,3)，节点1 和 节点3 不在同一个集合，生成树添加边(1,3)，并将节点1，节点3 放到同一个集合。

img

  1. 选边(2,6)，节点2 和 节点6 不在同一个集合，生成树添加边(2,6)，并将节点2，节点6 放到同一个集合。

img

  1. 选边(3,4)，节点3 和 节点4 不在同一个集合，生成树添加边(3,4)，并将节点3，节点4 放到同一个集合。

img

  1. 选边(6,7)，节点6 和 节点7 不在同一个集合，生成树添加边(6,7)，并将 节点6，节点7 放到同一个集合。

img

  1. 选边(5,7)，节点5 和 节点7 在同一个集合，不做计算。

    选边(1,5)，两个节点在同一个集合，不做计算。

​ 后面遍历 边(3,2)，(2,4)，(5,6) 同理，都因两个节点已经在同一集合，不做计算。

此时 我们就已经生成了一个最小生成树，即：

img

在上面的讲解中，看图的话 大家知道如何判断 两个节点 是否在同一个集合（是否有绿色的线连在一起），以及如何把两个节点加入集合（就在图中把两个节点连上）

但在代码中，如果将两个节点加入同一个集合，又如何判断两个节点是否在同一个集合呢？

这里就涉及到我们之前讲解的并查集

我们在并查集开篇的时候就讲了，并查集主要就两个功能：

  • 将两个元素添加到一个集合中
  • 判断两个元素在不在同一个集合

大家发现这正好符合Kruskal算法的需求，这也是为什么 我要先讲并查集，再讲 Kruskal。

本题代码如下，已经详细注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// l,r为 边两边的节点，val为边的数值
struct Edge {
    int l, r, val;
};

// 节点数量
int n = 10001;
// 并查集标记节点关系的数组
vector<int> father(n, -1); // 节点编号是从1开始的，n要大一些

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}

// 并查集的查找操作
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 并查集的加入集合
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

int main() {

    int v, e;
    int v1, v2, val;
    vector<Edge> edges;
    int result_val = 0;
    cin >> v >> e;
    while (e--) {
        cin >> v1 >> v2 >> val;
        edges.push_back({v1, v2, val});
    }

    // 执行Kruskal算法
    // 按边的权值对边进行从小到大排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.val < b.val;
    });

    // 并查集初始化
    init();

    // 从头开始遍历边
    for (Edge edge : edges) {
        // 并查集，搜出两个节点的祖先
        int x = find(edge.l);
        int y = find(edge.r);

        // 如果祖先不同，则不在同一个集合
        if (x != y) {
            result_val += edge.val; // 这条边可以作为生成树的边
            join(x, y); // 两个节点加入到同一个集合
        }
    }
    cout << result_val << endl;
    return 0;
}

时间复杂度：nlogn （快排） + logn （并查集） ，所以最后依然是nlogn 。n为边的数量。

拓展一

如果题目要求将最小生成树的边输出的话，应该怎么办呢？

Kruskal算法 输出边的话，相对prim要容易很多，因为Kruskal本来就是直接操作边，边的结构自然清晰，不用像 prim一样 需要再将节点连成线输出边 （因为prim是对节点操作，而 Kruskal是对边操作，这是本质区别）

本题中，边的结构为：

1
2
3
struct Edge {
    int l, r, val;
};

那么我们只需要找到 在哪里把生成树的边保存下来就可以了。

当判断两个节点不在同一个集合的时候，这两个节点的边就加入到最小生成树， 所以添加边的操作在这里：

1
2
3
4
5
6
7
vector<Edge> result; // 存储最小生成树的边
// 如果祖先不同，则不在同一个集合
if (x != y) {
    result.push_back(edge); // 记录最小生成树的边
    result_val += edge.val; // 这条边可以作为生成树的边
    join(x, y); // 两个节点加入到同一个集合
}

整体代码如下，为了突出重点，我仅仅将 打印最小生成树的部分代码注释了，大家更容易看到哪些改动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int l, r, val;
};


int n = 10001;

vector<int> father(n, -1); 

void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}

int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); 
}

void join(int u, int v) {
    u = find(u); 
    v = find(v); 
    if (u == v) return ; 
    father[v] = u;
}

int main() {

    int v, e;
    int v1, v2, val;
    vector<Edge> edges;
    int result_val = 0;
    cin >> v >> e;
    while (e--) {
        cin >> v1 >> v2 >> val;
        edges.push_back({v1, v2, val});
    }

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.val < b.val;
    });

    vector<Edge> result; // 存储最小生成树的边

    init();

    for (Edge edge : edges) {

        int x = find(edge.l);
        int y = find(edge.r);


        if (x != y) {
            result.push_back(edge); // 保存最小生成树的边
            result_val += edge.val; 
            join(x, y);
        }
    }

    // 打印最小生成树的边
    for (Edge edge : result) {
        cout << edge.l << " - " << edge.r << " : " << edge.val << endl;
    }

    return 0;
}

按照题目中的示例，打印边的输出为：

1
2
3
4
5
6
1 - 2 : 1
1 - 3 : 1
2 - 6 : 1
3 - 4 : 1
4 - 5 : 1
5 - 7 : 1

大家可能发现 怎么和我们 模拟画的图不一样，差别在于 代码生成的最小生成树中 节点5 和 节点7相连的。

img

其实造成这个差别 是对边排序的时候 权值相同的边先后顺序的问题导致的，无论相同权值边的顺序是什么样的，最后都能得出最小生成树，最小生成树不唯一。

拓展二

此时我们已经讲完了 Kruskal 和 prim 两个解法来求最小生成树。

什么情况用哪个算法更合适呢。

Kruskal与prim的关键区别在于，prim维护的是节点的集合，而 Kruskal维护的是边的集合。 如果 一个图中，节点多，但边相对较少，那么使用Kruskal 更优。

有录友可能疑惑，一个图里怎么可能节点多，边却少呢？

节点未必一定要连着边那， 例如 这个图，大家能明显感受到边没有那么多对吧，但节点数量 和 上述我们讲的例子是一样的。

img

为什么边少的话，使用 Kruskal更优呢？

因为 Kruskal是对边进行排序的后 进行操作是否加入到最小生成树。

边如果少，那么遍历操作的次数就少。

在节点数量固定的情况下，图中的边越少，Kruskal 需要遍历的边也就越少。

而 prim 算法是对节点进行操作的，节点数量越少，prim算法效率就越优。

所以在 稀疏图中，用Kruskal更优。 在稠密图中，用prim算法更优。

总结

边数量较少为稀疏图，接近或等于完全图（所有节点皆相连）为稠密图

Prim算法 时间复杂度为$ O(n^2)$，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。

Kruskal算法 时间复杂度 为$ nlogn$，其中n 为边的数量，适用稀疏图。

拓扑排序

117.软件构建

题目描述

某个大型软件项目的构建系统拥有 N 个文件，文件编号从 0 到 N - 1，在这些文件中，某些文件依赖于其他文件的内容，这意味着如果文件 A 依赖于文件 B，则必须在处理文件 A 之前处理文件 B （0 <= A, B <= N - 1）。请编写一个算法，用于确定文件处理的顺序。

输入描述

第一行输入两个正整数 N, M。表示 N 个文件之间拥有 M 条依赖关系。

后续 M 行，每行两个正整数 S 和 T，表示 T 文件依赖于 S 文件。

输出描述

输出共一行，如果能处理成功，则输出文件顺序，用空格隔开。

如果不能成功处理（相互依赖），则输出 -1。

输入示例
1
2
3
4
5
5 4
0 1
0 2
1 3
2 4
输出示例
1
0 1 2 3 4
提示信息

文件依赖关系如下：

img

所以，文件处理的顺序除了示例中的顺序，还存在

0 2 4 1 3

0 2 1 3 4

等等合法的顺序。

数据范围：

0 <= N <= 10 ^ 5

1 <= M <= 10 ^ 9

每行末尾无空格。

本题是拓扑排序的经典题目。一聊到 拓扑排序，一些录友可能会想这是排序，不会想到这是图论算法。

其实拓扑排序是经典的图论问题。

先说说 拓扑排序的应用场景。

大学排课，例如 先上A课，才能上B课，上了B课才能上C课，上了A课才能上D课，等等一系列这样的依赖顺序。 问给规划出一条 完整的上课顺序。

拓扑排序在文件处理上也有应用，我们在做项目安装文件包的时候，经常发现 复杂的文件依赖关系， A依赖B，B依赖C，B依赖D，C依赖E 等等。

如果给出一条线性的依赖顺序来下载这些文件呢？

有录友想上面的例子都很简单啊，我一眼能给排序出来。

那如果上面的依赖关系是一百对呢，一千对甚至上万个依赖关系，这些依赖关系中可能还有循环依赖，你如何发现循环依赖呢，又如果排出线性顺序呢。

所以 拓扑排序就是专门解决这类问题的。

概括来说，给出一个 有向图，把这个有向图转成线性的排序 就叫拓扑排序。

当然拓扑排序也要检测这个有向图 是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的。

所以拓扑排序也是图论中判断有向无环图的常用方法。

拓扑排序的思路

拓扑排序指的是一种 解决问题的大体思路， 而具体算法，可能是广搜也可能是深搜。

大家可能发现 各式各样的解法，纠结哪个是拓扑排序？

其实只要能在把 有向无环图 进行线性排序 的算法 都可以叫做 拓扑排序。

实现拓扑排序的算法有两种：卡恩算法（BFS）和DFS

卡恩算法（BFS）:卡恩1962年提出这种解决拓扑排序的思路

一般来说我们只需要掌握 BFS （广度优先搜索）就可以了，清晰易懂，如果还想多了解一些，可以再去学一下 DFS 的思路，但 DFS 不是本篇重点。

接下来我们来讲解BFS的实现思路。

以题目中示例为例如图：

img

做拓扑排序的话，如果肉眼去找开头的节点，一定能找到 节点0 吧，都知道要从节点0 开始。

但为什么我们能找到 节点0呢，因为我们肉眼看着 这个图就是从 节点0出发的。

作为出发节点，它有什么特征？

节点0 的入度 为0 出度为2， 也就是 没有边指向它，而它有两条边是指出去的。

节点的入度表示 有多少条边指向它，节点的出度表示有多少条边 从该节点出发。

所以当我们做拓扑排序的时候，应该优先找 入度为 0 的节点，只有入度为0，它才是出发节点。 理解以上内容很重要！

接下来我给出 拓扑排序的过程，其实就两步：

  1. 找到入度为0 的节点，加入结果集
  2. 将该节点从图中移除

循环以上两步，直到 所有节点都在图中被移除了。

结果集的顺序，就是我们想要的拓扑排序顺序 （结果集里顺序可能不唯一）

模拟过程

用本题的示例来模拟这一过程：

1、找到入度为0 的节点，加入结果集

img

2、将该节点从图中移除

img

1、找到入度为0 的节点，加入结果集

img

这里大家会发现，节点1 和 节点2 入度都为0， 选哪个呢？

选哪个都行，所以这也是为什么拓扑排序的结果是不唯一的。

2、将该节点从图中移除

img

1、找到入度为0 的节点，加入结果集

img

节点2 和 节点3 入度都为0，选哪个都行，这里选节点2

2、将该节点从图中移除

img

后面的过程一样的，节点3 和 节点4，入度都为0，选哪个都行。

最后结果集为： 0 1 2 3 4 。当然结果不唯一的。

判断有环

如果有 有向环怎么办呢？例如这个图：

img

这个图，我们只能将入度为0 的节点0 接入结果集。

之后，节点1、2、3、4 形成了环，找不到入度为0 的节点了，所以此时结果集里只有一个元素。

那么如果我们发现结果集元素个数 不等于 图中节点个数，我们就可以认定图中一定有 有向环！

这也是拓扑排序判断有向环的方法。

通过以上过程的模拟大家会发现这个拓扑排序好像不难，还有点简单。

写代码

理解思想后，确实不难，但代码写起来也不容易。

为了每次可以找到所有节点的入度信息，我们要在初始化的时候，就把每个节点的入度 和 每个节点的依赖关系做统计。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
cin >> n >> m;
vector<int> inDegree(n, 0); // 记录每个文件的入度
vector<int> result; // 记录结果
unordered_map<int, vector<int>> umap; // 记录文件依赖关系

while (m--) {
    // s->t，先有s才能有t
    cin >> s >> t;
    inDegree[t]++; // t的入度加一
    umap[s].push_back(t); // 记录s指向哪些文件
}

找入度为0 的节点，我们需要用一个队列放存放。

因为每次寻找入度为0的节点，不一定只有一个节点，可能很多节点入度都为0，所以要将这些入度为0的节点放到队列里，依次去处理。

代码如下：

1
2
3
4
5
queue<int> que;
for (int i = 0; i < n; i++) {
    // 入度为0的节点，可以作为开头，先加入队列
    if (inDegree[i] == 0) que.push(i);
}

开始从队列里遍历入度为0 的节点，将其放入结果集。

1
2
3
4
5
6
7
while (que.size()) {
    int  cur = que.front(); // 当前选中的节点
    que.pop();
    result.push_back(cur);
    // 将该节点从图中移除 

}

这里面还有一个很重要的过程，如何把这个入度为0的节点从图中移除呢？

首先我们为什么要把节点从图中移除？

为的是将 该节点作为出发点所连接的边删掉。

删掉的目的是什么呢？

要把 该节点作为出发点所连接的节点的 入度 减一。

如果这里不理解，看上面的模拟过程第一步：

img

这事节点1 和 节点2 的入度为 1。

将节点0删除后，图为这样：

img

那么 节点0 作为出发点 所连接的节点的入度 就都做了 减一 的操作。

此时 节点1 和 节点 2 的入度都为0， 这样才能作为下一轮选取的节点。

所以，我们在代码实现的过程中，本质是要将 该节点作为出发点所连接的节点的 入度 减一 就可以了，这样好能根据入度找下一个节点，不用真在图里把这个节点删掉。

该过程代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while (que.size()) {
    int  cur = que.front(); // 当前选中的节点
    que.pop();
    result.push_back(cur);
    // 将该节点从图中移除 
    vector<int> files = umap[cur]; //获取cur指向的节点
    if (files.size()) { // 如果cur有指向的节点
        for (int i = 0; i < files.size(); i++) { // 遍历cur指向的节点
            inDegree[files[i]] --; // cur指向的节点入度都做减一操作
            // 如果指向的节点减一之后，入度为0，说明是我们要选取的下一个节点，放入队列。
            if(inDegree[files[i]] == 0) que.push(files[i]); 
        }
    }

}

最后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {
    int m, n, s, t;
    cin >> n >> m;
    vector<int> inDegree(n, 0); // 记录每个文件的入度

    unordered_map<int, vector<int>> umap;// 记录文件依赖关系
    vector<int> result; // 记录结果

    while (m--) {
        // s->t，先有s才能有t
        cin >> s >> t;
        inDegree[t]++; // t的入度加一
        umap[s].push_back(t); // 记录s指向哪些文件
    }
    queue<int> que;
    for (int i = 0; i < n; i++) {
        // 入度为0的文件，可以作为开头，先加入队列
        if (inDegree[i] == 0) que.push(i);
        //cout << inDegree[i] << endl;
    }
    // int count = 0;
    while (que.size()) {
        int  cur = que.front(); // 当前选中的文件
        que.pop();
        //count++;
        result.push_back(cur);
        vector<int> files = umap[cur]; //获取该文件指向的文件
        if (files.size()) { // cur有后续文件
            for (int i = 0; i < files.size(); i++) {
                inDegree[files[i]] --; // cur的指向的文件入度-1
                if(inDegree[files[i]] == 0) que.push(files[i]);
            }
        }
    }
    if (result.size() == n) {
        for (int i = 0; i < n - 1; i++) cout << result[i] << " ";
        cout << result[n - 1];
    } else cout << -1 << endl;
   return 0;
}

10/10

dijkstra（朴素版）精讲

47.参加科学大会（第六期模拟笔试）

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。

小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。

小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。

输入描述

第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。

接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。

输出描述

输出一个整数，代表小明从起点到终点所花费的最小时间。

输入示例
1
2
3
4
5
6
7
8
9
10
7 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 2
4 5 3
2 6 4
5 7 4
6 7 9
输出示例
1
12
提示信息

能够到达的情况：

如下图所示，起始车站为 1 号车站，终点车站为 7 号车站，绿色路线为最短的路线，路线总长度为 12，则输出 12。

img

不能到达的情况：

如下图所示，当从起始车站不能到达终点车站时，则输出 -1。

img

数据范围：

1 <= N <= 500;
1 <= M <= 5000;

本题就是求最短路，最短路是图论中的经典问题即：给出一个有向图，一个起点，一个终点，问起点到终点的最短路径。

接下来，我们来详细讲解最短路算法中的dijkstra算法。

dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。

需要注意两点：

  • dijkstra 算法可以同时求 起点到所有节点的最短路径
  • 权值不能为负数

（这两点后面我们会讲到）

如本题示例中的图：

img

起点（节点1）到终点（节点7） 的最短路径是 图中 标记绿线的部分。

最短路径的权值为12。

其实dijkstra算法 和 我们之前讲解的prim算法思路非常接近，如果大家认真学过prim算法，那么理解 Dijkstra 算法会相对容易很多。（这也是我要先讲prim再讲dijkstra的原因）

dijkstra 算法 同样是贪心的思路，不断寻找距离 源点最近的没有访问过的节点。

这里我也给出 dijkstra三部曲：

  1. 第一步，选源点到哪个节点近且该节点未被访问过
  2. 第二步，该最近节点被标记访问过
  3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）

大家此时已经会发现，这和prim算法 怎么这么像呢。

我在prim算法讲解中也给出了三部曲。 prim 和dijkstra确实很像，思路也是类似的。

在dijkstra算法中，同样有一个数组很重要，起名为：minDist。minDist数组 用来记录 每一个节点距离源点的最小距离。

理解这一点很重要，也是理解dijkstra算法的核心所在。

我们先来画图看一下dijkstra的工作过程，以本题示例为例： （以下为朴素版dijkstra的思路）

（示例中节点编号是从1开始，所以为了让大家看的不晕，minDist数组下标我也从 1 开始计数，下标0 就不使用了，这样 下标和节点标号就可以对应上了，避免大家搞混）

模拟过程

0、初始化

minDist数组数值初始化为int最大值。

这里在强点一下 minDist数组的含义：记录所有节点到源点的最短路径，那么初始化的时候就应该初始为最大值，这样才能在后续出现最短路径的时候及时更新。

img

（图中，max 表示默认值，节点0 不做处理，统一从下标1 开始计算，这样下标和节点数值统一， 方便大家理解，避免搞混）

源点（节点1） 到自己的距离为0，所以 minDist[1] = 0。此时所有节点都没有被访问过，所以 visited数组都为0

以下为dijkstra 三部曲

1、选源点到哪个节点近且该节点未被访问过

源点距离源点最近，距离为0，且未被访问。

2、该最近节点被标记访问过

标记源点访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

更新 minDist数组，即：源点（节点1） 到 节点2 和 节点3的距离。

  • 源点到节点2的最短距离为1，小于原minDist[2]的数值max，更新minDist[2] = 1
  • 源点到节点3的最短距离为4，小于原minDist[3]的数值max，更新minDist[3] = 4

可能有录友问：为啥和 minDist[2] 比较？

再强调一下 minDist[2] 的含义，它表示源点到节点2的最短距离，那么目前我们得到了 源点到节点2的最短距离为1，小于默认值max，所以更新。 minDist[3]的更新同理

1、选源点到哪个节点近且该节点未被访问过

未访问过的节点中，源点到节点2距离最近，选节点2

2、该最近节点被标记访问过

节点2被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

更新 minDist数组，即：源点（节点1） 到 节点6 、 节点3 和 节点4的距离。

为什么更新这些节点呢？ 怎么不更新其他节点呢？

因为 源点（节点1）通过 已经计算过的节点（节点2） 可以链接到的节点 有 节点3，节点4和节点6.

更新 minDist数组：

  • 源点到节点6的最短距离为5，小于原minDist[6]的数值max，更新minDist[6] = 5
  • 源点到节点3的最短距离为3，小于原minDist[3]的数值4，更新minDist[3] = 3
  • 源点到节点4的最短距离为6，小于原minDist[4]的数值max，更新minDist[4] = 6

1、选源点到哪个节点近且该节点未被访问过

未访问过的节点中，源点距离哪些节点最近，怎么算的？

其实就是看 minDist数组里的数值，minDist 记录了 源点到所有节点的最近距离，结合visited数组筛选出未访问的节点就好。

从 上面的图，或者 从minDist数组中，我们都能看出 未访问过的节点中，源点（节点1）到节点3距离最近。

2、该最近节点被标记访问过

节点3被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

由于节点3的加入，那么源点可以有新的路径链接到节点4 所以更新minDist数组：

更新 minDist数组：

  • 源点到节点4的最短距离为5，小于原minDist[4]的数值6，更新minDist[4] = 5

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，有节点4 和 节点6，距离源点距离都是 5 （minDist[4] = 5，minDist[6] = 5） ，选哪个节点都可以。

2、该最近节点被标记访问过

节点4被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

由于节点4的加入，那么源点可以链接到节点5 所以更新minDist数组：

  • 源点到节点5的最短距离为8，小于原minDist[5]的数值max，更新minDist[5] = 8

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，是节点6，距离源点距离是 5 （minDist[6] = 5）

2、该最近节点被标记访问过

节点6 被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

由于节点6的加入，那么源点可以链接到节点7 所以 更新minDist数组：

  • 源点到节点7的最短距离为14，小于原minDist[7]的数值max，更新minDist[7] = 14

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，是节点5，距离源点距离是 8 （minDist[5] = 8）

2、该最近节点被标记访问过

节点5 被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

由于节点5的加入，那么源点有新的路径可以链接到节点7 所以 更新minDist数组：

  • 源点到节点7的最短距离为12，小于原minDist[7]的数值14，更新minDist[7] = 12

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，是节点7（终点），距离源点距离是 12 （minDist[7] = 12）

2、该最近节点被标记访问过

节点7 被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

节点7加入，但节点7到节点7的距离为0，所以 不用更新minDist数组

最后我们要求起点（节点1） 到终点 （节点7）的距离。

再来回顾一下minDist数组的含义：记录 每一个节点距离源点的最小距离。

那么起到（节点1）到终点（节点7）的最短距离就是 minDist[7] ，按上面举例讲解来说，minDist[7] = 12，节点1 到节点7的最短路径为 12。

路径如图：

img

在上面的讲解中，每一步 我都是按照dijkstra三部曲来讲解的，理解了这三部曲，代码也就好懂的。

代码实现

本题代码如下，里面的三部曲我都做了注释，大家按照我上面的讲 来看如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
    }

    int start = 1;
    int end = n;

    // 存储从源点到每个节点的最短距离
    std::vector<int> `minDist`(n + 1, INT_MAX);

    // 记录顶点是否被访问过
    std::vector<bool> visited(n + 1, false);

    `minDist`[start] = 0;  // 起始点到自身的距离为0

    for (int i = 1; i <= n; i++) { // 遍历所有节点

        int minVal = INT_MAX;
        int cur = 1;

        // 1、选距离源点最近且未访问过的节点
        for (int v = 1; v <= n; ++v) {
            if (!visited[v] && `minDist`[v] < minVal) {
                minVal = `minDist`[v];
                cur = v;
            }
        }

        visited[cur] = true;  // 2、标记该节点已被访问

        // 3、第三步，更新非访问节点到源点的距离（即更新`minDist`数组）
        for (int v = 1; v <= n; v++) {
            if (!visited[v] && grid[cur][v] != INT_MAX && `minDist`[cur] + grid[cur][v] < `minDist`[v]) {
                `minDist`[v] = `minDist`[cur] + grid[cur][v];
            }
        }

    }

    if (`minDist`[end] == INT_MAX) cout << -1 << endl; // 不能到达终点
    else cout << `minDist`[end] << endl; // 到达终点最短路径

}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$

debug方法

写这种题目难免会有各种各样的问题，我们如何发现自己的代码是否有问题呢？

最好的方式就是打日志，本题的话，就是将 minDist 数组打印出来，就可以很明显发现 哪里出问题了。

每次选择节点后，minDist数组的变化是否符合预期 ，是否和我上面讲的逻辑是对应的。

例如本题，如果想debug的话，打印日志可以这样写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
    }

    int start = 1;
    int end = n;

    std::vector<int> `minDist`(n + 1, INT_MAX);

    std::vector<bool> visited(n + 1, false);

    `minDist`[start] = 0;
    for (int i = 1; i <= n; i++) {

        int minVal = INT_MAX;
        int cur = 1;


        for (int v = 1; v <= n; ++v) {
            if (!visited[v] && `minDist`[v] < minVal) {
                minVal = `minDist`[v];
                cur = v;
            }
        }

        visited[cur] = true;

        for (int v = 1; v <= n; v++) {
            if (!visited[v] && grid[cur][v] != INT_MAX && `minDist`[cur] + grid[cur][v] < `minDist`[v]) {
                `minDist`[v] = `minDist`[cur] + grid[cur][v];
            }
        }

        // 打印日志：
        cout << "select:" << cur << endl;
        for (int v = 1; v <= n; v++) cout <<  v << ":" << `minDist`[v] << " ";
        cout << endl << endl;;

    }
    if (`minDist`[end] == INT_MAX) cout << -1 << endl;
    else cout << `minDist`[end] << endl;

}

打印后的结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
select:1
1:0 2:1 3:4 4:2147483647 5:2147483647 6:2147483647 7:2147483647

select:2
1:0 2:1 3:3 4:6 5:2147483647 6:5 7:2147483647

select:3
1:0 2:1 3:3 4:5 5:2147483647 6:5 7:2147483647

select:4
1:0 2:1 3:3 4:5 5:8 6:5 7:2147483647

select:6
1:0 2:1 3:3 4:5 5:8 6:5 7:14

select:5
1:0 2:1 3:3 4:5 5:8 6:5 7:12

select:7
1:0 2:1 3:3 4:5 5:8 6:5 7:12

打印日志可以和上面我讲解的过程进行对比，每一步的结果是完全对应的。

所以如果大家如果代码有问题，打日志来debug是最好的方法

如何求路径

如果题目要求把最短路的路径打印出来，应该怎么办呢？

这里还是有一些“坑”的，本题打印路径和 prim 打印路径是一样的，我在 prim算法精讲 【拓展】中 已经详细讲解了。

在这里就不再赘述。

打印路径只需要添加 几行代码， 打印路径的代码我都加上的日志，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
    }

    int start = 1;
    int end = n;

    std::vector<int> `minDist`(n + 1, INT_MAX);

    std::vector<bool> visited(n + 1, false);

    `minDist`[start] = 0; 

    //加上初始化
    vector<int> parent(n + 1, -1);

    for (int i = 1; i <= n; i++) {

        int minVal = INT_MAX;
        int cur = 1;

        for (int v = 1; v <= n; ++v) {
            if (!visited[v] && `minDist`[v] < minVal) {
                minVal = `minDist`[v];
                cur = v;
            }
        }

        visited[cur] = true;

        for (int v = 1; v <= n; v++) {
            if (!visited[v] && grid[cur][v] != INT_MAX && `minDist`[cur] + grid[cur][v] < `minDist`[v]) {
                `minDist`[v] = `minDist`[cur] + grid[cur][v];
                parent[v] = cur; // 记录边
            }
        }

    }

    // 输出最短情况
    for (int i = 1; i <= n; i++) {
        cout << parent[i] << "->" << i << endl;
    }
}

打印结果：

1
2
3
4
5
6
7
-1->1
1->2
2->3
3->4
4->5
2->6
5->7

对应如图：

img

出现负数

如果图中边的权值为负数，dijkstra 还合适吗？

看一下这个图： （有负权值）

img

节点1 到 节点5 的最短路径 应该是 节点1 -> 节点2 -> 节点3 -> 节点4 -> 节点5

那我们来看dijkstra求解的路径是什么样的，继续dijkstra 三部曲来模拟 ：（dijkstra模拟过程上面已经详细讲过，以下只模拟重要过程，例如如何初始化就省略讲解了）

初始化：

img

1、选源点到哪个节点近且该节点未被访问过

源点距离源点最近，距离为0，且未被访问。

2、该最近节点被标记访问过

标记源点访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

更新 minDist数组，即：源点（节点1） 到 节点2 和 节点3的距离。

  • 源点到节点2的最短距离为100，小于原minDist[2]的数值max，更新minDist[2] = 100
  • 源点到节点3的最短距离为1，小于原minDist[3]的数值max，更新minDist[3] = 1

1、选源点到哪个节点近且该节点未被访问过

源点距离节点3最近，距离为1，且未被访问。

2、该最近节点被标记访问过

标记节点3访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

由于节点3的加入，那么源点可以有新的路径链接到节点4 所以更新minDist数组：

  • 源点到节点4的最短距离为2，小于原minDist[4]的数值max，更新minDist[4] = 2

1、选源点到哪个节点近且该节点未被访问过

源点距离节点4最近，距离为2，且未被访问。

2、该最近节点被标记访问过

标记节点4访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

由于节点4的加入，那么源点可以有新的路径链接到节点5 所以更新minDist数组：

  • 源点到节点5的最短距离为3，小于原minDist[5]的数值max，更新minDist[5] = 3

1、选源点到哪个节点近且该节点未被访问过

源点距离节点5最近，距离为3，且未被访问。

2、该最近节点被标记访问过

标记节点5访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

节点5的加入，而节点5 没有链接其他节点， 所以不用更新minDist数组，仅标记节点5被访问过了

1、选源点到哪个节点近且该节点未被访问过

源点距离节点2最近，距离为100，且未被访问。

2、该最近节点被标记访问过

标记节点2访问过

3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：

img

至此dijkstra的模拟过程就结束了，根据最后的minDist数组，我们求 节点1 到 节点5 的最短路径的权值总和为 3，路径： 节点1 -> 节点3 -> 节点4 -> 节点5

通过以上的过程模拟，我们可以发现 之所以 没有走有负权值的最短路径 是因为 在 访问 节点 2 的时候，节点 3 已经访问过了，就不会再更新了。

那有录友可能会想： 我可以改代码逻辑啊，访问过的节点，也让它继续访问不就好了？

那么访问过的节点还能继续访问会不会有死循环的出现呢？控制逻辑不让其死循环？那特殊情况自己能都想清楚吗？（可以试试，实践出真知）

对于负权值的出现，大家可以针对某一个场景 不断去修改dijkstra的代码，但最终会发现只是 拆了东墙补西墙，对dijkstra的补充逻辑只能满足某特定场景最短路求解。

对于求解带有负权值的最短路问题，可以使用 Bellman-Ford 算法 ，我在后序会详细讲解。

dijkstra与prim算法的区别

这里再次提示，需要先看我的 prim算法精讲 ，否则可能不知道我下面讲的是什么。

大家可以发现 dijkstra的代码看上去 怎么和prim算法这么像呢。

其实代码大体不差，唯一区别在 三部曲中的 第三步： 更新minDist数组

因为prim是求 非访问节点到最小生成树的最小距离，而 dijkstra是求 非访问节点到源点的最小距离。

prim 更新 minDist数组的写法：

1
2
3
4
5
for (int j = 1; j <= v; j++) {
    if (!isInTree[j] && grid[cur][j] < `minDist`[j]) {
        `minDist`[j] = grid[cur][j];
    }
}

因为 minDist表示 节点到最小生成树的最小距离，所以 新节点cur的加入，只需要 使用 grid[cur] [j] ，grid[cur] [j] 就表示 cur 加入生成树后，生成树到 节点j 的距离。

dijkstra 更新 minDist数组的写法：

1
2
3
4
5
for (int v = 1; v <= n; v++) {
    if (!visited[v] && grid[cur][v] != INT_MAX && `minDist`[cur] + grid[cur][v] < `minDist`[v]) {
        `minDist`[v] = `minDist`[cur] + grid[cur][v];
    }
}

因为 minDist表示 节点到源点的最小距离，所以 新节点 cur 的加入，需要使用 源点到cur的距离 （minDist[cur]） + cur 到 节点 v 的距离 （grid[cur] [v]），才是 源点到节点v的距离。

此时大家可能不禁要想 prim算法 可以有负权值吗？

经验

  • prim算法可以处理负权值，但不应有负权环。
  • 最小生成树的性质依然适用，最终的树仍然是具有最小边权和的树。
  • Dijkstra算法不适合有负权边的图。
  • 应使用贝尔曼-福特算法来处理含有负权边的情况。

总结

本篇，我们深入讲解的dijkstra算法，详细模拟其工作的流程。

这里我给出了 dijkstra 三部曲来帮助大家理解 该算法，不至于 每次写dijkstra都是黑盒操作，没有框架没有章法。

在给出的代码中，我也按照三部曲的逻辑来给大家注释，只要理解这三部曲，即使过段时间 对dijkstra算法有些遗忘，依然可以写出一个框架出来，然后再去调试细节。

对于图论算法，一般代码都比较长，很难写出代码直接可以提交通过，都需要一个debug的过程，所以 学习如何debug 非常重要！

这也是我为什么 在本文中 单独用来讲解 debug方法。

本题求的是最短路径和是多少，同时我们也要掌握 如何把最短路径打印出来。

我还写了大篇幅来讲解负权值的情况， 只有画图带大家一步一步去 看 出现负权值 dijkstra的求解过程，才能帮助大家理解，问题出在哪里。

如果我直接讲：是因为访问过的节点不能再访问，导致错过真正的最短路，我相信大家都不知道我在说啥。

最后我还讲解了dijkstra和 prim 算法的相同与不同之处， 我在图论的讲解安排中先讲 prim算法再讲dijkstra是有目的的， 理解这两个算法的相同与不同之处 有助于大家学习的更深入。

而不是学了dijkstra就只看 dijkstra， 算法之间都是有联系的，多去思考算法之间的相互联系，会帮助大家思考的更深入，掌握的更彻底。

dijkstra（堆优化版）精讲

在上一篇中，我们讲解了朴素版的dijkstra，该解法的时间复杂度为 $O(n^2)$，可以看出时间复杂度只和 n （节点数量）有关系。

如果n很大的话，我们可以换一个角度来优先性能。

在讲解 最小生成树的时候，我们 讲了两个算法，prim算法（从点的角度来求最小生成树）、Kruskal算法（从边的角度来求最小生成树）

这么在n 很大的时候，也有另一个思考维度，即：从边的数量出发。

当 n 很大，边 的数量 也很多的时候（稠密图），那么上述解法没问题。

但 n 很大，边 的数量 很小的时候（稀疏图），是不是可以换成从边的角度来求最短路呢？

毕竟边的数量少。

有的录友可能会想，n （节点数量）很大，边不就多吗？ 怎么会边的数量少呢？

别忘了，谁也没有规定 节点之间一定要有边连接着，例如有一万个节点，只有一条边，这也是一张图。

了解背景之后，再来看 解法思路。

图的存储

首先是 图的存储。

关于图的存储 主流有两种方式： 邻接矩阵和邻接表

邻接矩阵

邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。

例如： grid[2] [5] = 6，表示 节点 2 链接 节点5 为有向图，节点2 指向 节点5，边的权值为6 （套在题意里，可能是距离为6 或者 消耗为6 等等）

如果想表示无向图，即：grid[2] [5] = 6，grid[5] [2] = 6，表示节点2 与 节点5 相互连通，权值为6。

如图：

img

在一个 n （节点数）为8 的图中，就需要申请 8 * 8 这么大的空间，有一条双向边，即：grid[2] [5] = 6，grid[5] [2] = 6

这种表达方式（邻接矩阵） 在 边少，节点多的情况下，会导致申请过大的二维数组，造成空间浪费。

而且在寻找节点链接情况的时候，需要遍历整个矩阵，即 $n * n$ 的时间复杂度，同样造成时间浪费。

邻接矩阵的优点：

  • 表达方式简单，易于理解
  • 检查任意两个顶点间是否存在边的操作非常快
  • 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

缺点：

  • 遇到稀疏图，会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费

邻接表

邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。

邻接表的构造如图：

img

这里表达的图是：

  • 节点1 指向 节点3 和 节点5
  • 节点2 指向 节点4、节点3、节点5
  • 节点3 指向 节点4，节点4指向节点1。

有多少边 邻接表才会申请多少个对应的链表节点。从图中可以直观看出 使用 数组 + 链表 来表达 边的链接情况 。

邻接表的优点：

  • 对于稀疏图的存储，只需要存储边，空间利用率高
  • 遍历节点链接情况相对容易

缺点：

  • 检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点链接其他节点的数量。
  • 实现相对复杂，不易理解

本题图的存储

接下来我们继续按照稀疏图的角度来分析本题。

在第一个版本的实现思路中，我们提到了三部曲：

  1. 第一步，选源点到哪个节点近且该节点未被访问过
  2. 第二步，该最近节点被标记访问过
  3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）

在第一个版本的代码中，这三部曲是套在一个 for 循环里，为什么？

因为我们是从节点的角度来解决问题。

三部曲中第一步（选源点到哪个节点近且该节点未被访问过），这个操作本身需要for循环遍历minDist 来寻找最近的节点。

同时我们需要 遍历所有 未访问过的节点，所以 我们从 节点角度出发，代码会有两层for循环，代码是这样的： （注意代码中的注释，标记两层for循环的用处）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for (int i = 1; i <= n; i++) { // 遍历所有节点，第一层for循环 

    int minVal = INT_MAX;
    int cur = 1;

    // 1、选距离源点最近且未访问过的节点 ， 第二层for循环
    for (int v = 1; v <= n; ++v) {
        if (!visited[v] &&` minDist`[v] < minVal) {
            minVal =` minDist`[v];
            cur = v;
        }
    }

    visited[cur] = true;  // 2、标记该节点已被访问

    // 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）
    for (int v = 1; v <= n; v++) {
        if (!visited[v] && grid[cur][v] != INT_MAX &&` minDist`[cur] + grid[cur][v] <` minDist`[v]) {
           ` minDist`[v] =` minDist`[cur] + grid[cur][v];
        }
    }

}

那么当从 边 的角度出发， 在处理 三部曲里的第一步（选源点到哪个节点近且该节点未被访问过）的时候 ，我们可以不用去遍历所有节点了。

而且 直接把 边（带权值）加入到 小顶堆（利用堆来自动排序），那么每次我们从 堆顶里 取出 边 自然就是 距离源点最近的节点所在的边。

这样我们就不需要两层for循环来寻找最近的节点了。

了解了大体思路，我们再来看代码实现。

首先是 如何使用 邻接表来表述图结构，这是摆在很多录友面前的第一个难题。

邻接表用 数组+链表 来表示，代码如下：（C++中 vector 为数组，list 为链表， 定义了 n+1 这么大的数组空间）

1
vector<list<int>> grid(n + 1);

不少录友，不知道 如何定义的数据结构，怎么表示邻接表的，我来给大家画一个图：

img

图中邻接表表示：

  • 节点1 指向 节点3 和 节点5
  • 节点2 指向 节点4、节点3、节点5
  • 节点3 指向 节点4
  • 节点4 指向 节点1

大家发现图中的边没有权值，而本题中 我们的边是有权值的，权值怎么表示？在哪里表示？

所以 在vector<list<int>> grid(n + 1); 中 就不能使用int了，而是需要一个键值对 来存两个数字，一个数表示节点，一个数表示 指向该节点的这条边的权值。

那么 代码可以改成这样： （pair 为键值对，可以存放两个int）

1
vector<list<pair<int,int>>> grid(n + 1);

举例来给大家展示 该代码表达的数据 如下：

img

  • 节点1 指向 节点3 权值为 1
  • 节点1 指向 节点5 权值为 2
  • 节点2 指向 节点4 权值为 7
  • 节点2 指向 节点3 权值为 6
  • 节点2 指向 节点5 权值为 3
  • 节点3 指向 节点4 权值为 3
  • 节点5 指向 节点1 权值为 10

这样 我们就把图中权值表示出来了。

但是在代码中 使用 pair<int, int> 很容易让我们搞混了，第一个int 表示什么，第二个int表示什么，导致代码可读性很差，或者说别人看你的代码看不懂。

那么 可以 定一个类 来取代 pair<int, int>

类（或者说是结构体）定义如下：

1
2
3
4
5
6
struct Edge {
    int to;  // 邻接顶点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};

这个类里有两个成员变量，有对应的命名，这样不容易搞混 两个int的含义。

所以 本题中邻接表的定义如下：

1
2
3
4
5
6
7
8
struct Edge {
    int to;  // 链接的节点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};

vector<list<Edge>> grid(n + 1); // 邻接表

（我们在下面的讲解中会直接使用这个邻接表的代码表示方式）

堆优化细节

其实思路依然是 dijkstra 三部曲：

  1. 第一步，选源点到哪个节点近且该节点未被访问过
  2. 第二步，该最近节点被标记访问过
  3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）

只不过之前是 通过遍历节点来遍历边，通过两层for循环来寻找距离源点最近节点。 这次我们直接遍历边，且通过堆来对边进行排序，达到直接选择距离源点最近节点。

先来看一下针对这三部曲，如果用 堆来优化。

那么三部曲中的第一步（选源点到哪个节点近且该节点未被访问过），我们如何选？

我们要选择距离源点近的节点（即：该边的权值最小），所以 我们需要一个 小顶堆 来帮我们对边的权值排序，每次从小顶堆堆顶 取边就是权值最小的边。

C++定义小顶堆，可以用优先级队列实现，代码如下：

1
2
3
4
5
6
7
8
9
// 小顶堆
class mycomparison {
public:
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};
// 优先队列中存放 pair<节点编号，源点到该节点的权值> 
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;

（pair<int, int>中 第二个int 为什么要存 源点到该节点的权值，因为 这个小顶堆需要按照权值来排序）

有了小顶堆自动对边的权值排序，那我们只需要直接从 堆里取堆顶元素（小顶堆中，最小的权值在上面），就可以取到离源点最近的节点了 （未访问过的节点，不会加到堆里进行排序）

所以三部曲中的第一步，我们不用 for循环去遍历，直接取堆顶元素：

1
2
// pair<节点编号，源点到该节点的权值>
pair<int, int> cur = pq.top(); pq.pop();

第二步（该最近节点被标记访问过） 这个就是将 节点做访问标记，和 朴素dijkstra 一样 ，代码如下：

1
2
// 2. 第二步，该最近节点被标记访问过
visited[cur.first] = true;

（cur.first 是指取 pair<int, int> 里的第一个int，即节点编号 ）

第三步（更新非访问节点到源点的距离），这里的思路 也是 和朴素dijkstra一样的。

但很多录友对这里是最懵的，主要是因为两点：

  • 没有理解透彻 dijkstra 的思路
  • 没有理解 邻接表的表达方式

我们来回顾一下 朴素dijkstra 在这一步的代码和思路（如果没看过我讲解的朴素版dijkstra，这里会看不懂）

1
2
3
4
5
6
// 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）
for (int v = 1; v <= n; v++) {
    if (!visited[v] && grid[cur][v] != INT_MAX &&` minDist`[cur] + grid[cur][v] <` minDist`[v]) {
       ` minDist`[v] =` minDist`[cur] + grid[cur][v];
    }
}

其中 for循环是用来做什么的？ 是为了 找到 节点cur 链接指向了哪些节点，因为使用邻接矩阵的表达方式 所以把所有节点遍历一遍。

而在邻接表中，我们可以以相对高效的方式知道一个节点链接指向哪些节点。

再回顾一下邻接表的构造（数组 + 链表）：

img

假如 加入的cur 是节点 2， 那么 grid[2] 表示的就是图中第二行链表。 （grid数组的构造我们在 上面 「图的存储」中讲过）

所以在邻接表中，我们要获取 节点cur 链接指向哪些节点，就是遍历 grid[cur节点编号] 这个链表。

这个遍历方式，C++代码如下：

1
for (Edge edge : grid[cur.first])

（如果不知道 Edge 是什么，看上面「图的存储」中邻接表的讲解）

cur.first 就是cur节点编号， 参考上面pair的定义： pair<节点编号，源点到该节点的权值>

接下来就是更新 非访问节点到源点的距离，代码实现和 朴素dijkstra 是一样的，代码如下：

1
2
3
4
5
6
7
8
// 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点，cur指向的节点为 edge
    // cur指向的节点edge.to，这条边的权值为 edge.val
    if (!visited[edge.to] &&` minDist`[cur.first] + edge.val <` minDist`[edge.to]) { // 更新minDist
       ` minDist`[edge.to] =` minDist`[cur.first] + edge.val;
        pq.push(pair<int, int>(edge.to,` minDist`[edge.to]));
    }
}

但为什么思路一样，有的录友能写出朴素dijkstra，但堆优化这里的逻辑就是写不出来呢？

主要就是因为对邻接表的表达方式不熟悉！

以上代码中，cur 链接指向的节点编号 为 edge.to， 这条边的权值为edge.val ，如果对这里模糊的就再回顾一下 Edge的定义：

1
2
3
4
5
6
struct Edge {
    int to;  // 邻接顶点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};

确定该节点没有被访问过，!visited[edge.to] ， 目前 源点到cur.first的最短距离（minDist） + cur.first到 edge.to的距离 （edge.val） 是否 小于 minDist已经记录的 源点到 edge.to 的距离 （minDist[edge.to]）

如果是的话，就开始更新操作。

即：

1
2
3
4
if (!visited[edge.to] &&` minDist`[cur.first] + edge.val <` minDist`[edge.to]) { // 更新minDist
   ` minDist`[edge.to] =` minDist`[cur.first] + edge.val;
    pq.push(pair<int, int>(edge.to,` minDist`[edge.to])); // 由于cur节点的加入，而新链接的边，加入到优先级队里中
}

同时，由于cur节点的加入，源点又有可以新链接到的边，将这些边加入到优先级队里中。

以上代码思路 和 朴素版dijkstra 是一样一样的，主要区别是两点：

  • 邻接表的表示方式不同
  • 使用优先级队列（小顶堆）来对新链接的边排序

代码实现

堆优化dijkstra完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std; 
// 小顶堆
class mycomparison {
public:
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};
// 定义一个结构体来表示带权重的边
struct Edge {
    int to;  // 邻接顶点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<list<Edge>> grid(n + 1);

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val; 
        // p1 指向 p2，权值为 val
        grid[p1].push_back(Edge(p2, val));

    }

    int start = 1;  // 起点
    int end = n;    // 终点

    // 存储从源点到每个节点的最短距离
    std::vector<int>` minDist`(n + 1, INT_MAX);

    // 记录顶点是否被访问过
    std::vector<bool> visited(n + 1, false); 
    
    // 优先队列中存放 pair<节点，源点到该节点的权值>
    priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;


    // 初始化队列，源点到源点的距离为0，所以初始为0
    pq.push(pair<int, int>(start, 0)); 
    
   ` minDist`[start] = 0;  // 起始点到自身的距离为0

    while (!pq.empty()) {
        // 1. 第一步，选源点到哪个节点近且该节点未被访问过 （通过优先级队列来实现）
        // <节点， 源点到该节点的距离>
        pair<int, int> cur = pq.top(); pq.pop();

        if (visited[cur.first]) continue;

        // 2. 第二步，该最近节点被标记访问过
        visited[cur.first] = true;

        // 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
        for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点，cur指向的节点为 edge
            // cur指向的节点edge.to，这条边的权值为 edge.val
            if (!visited[edge.to] &&` minDist`[cur.first] + edge.val <` minDist`[edge.to]) { // 更新minDist
               ` minDist`[edge.to] =` minDist`[cur.first] + edge.val;
                pq.push(pair<int, int>(edge.to,` minDist`[edge.to]));
            }
        }

    }

    if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点
    else cout <<` minDist`[end] << endl; // 到达终点最短路径
}
  • 时间复杂度：$O(ElogE)$ E 为边的数量
  • 空间复杂度：$O(N + E)$ N 为节点的数量

堆优化的时间复杂度 只和边的数量有关 ，和节点数无关，在 优先级队列中 放的也是边。

以上代码中，while (!pq.empty()) 里套了 for (Edge edge : grid[cur.first])

for 里 遍历的是 当前节点 cur 所连接边。

那 当前节点cur 所连接的边 也是不固定的， 这就让大家分不清，这时间复杂度究竟是多少？

其实 for (Edge edge : grid[cur.first]) 里最终的数据走向 是 给队列里添加边。

那么跳出局部代码，整个队列 一定是 所有边添加了一次，同时也弹出了一次。

所以边添加一次时间复杂度是 O(E)， while (!pq.empty()) 里每次都要弹出一个边来进行操作，在优先级队列（小顶堆）中 弹出一个元素的时间复杂度是 O(logE) ，这是堆排序的时间复杂度。

（当然小顶堆里 是 添加元素的时候 排序，还是 取数元素的时候排序，这个无所谓，时间复杂度都是O(E)，总之是一定要排序的，而小顶堆里也不会滞留元素，有多少元素添加 一定就有多少元素弹出）

所以 该算法整体时间复杂度为$ O（ElogE)$

网上的不少分析 会把 n （节点的数量）算进来，这个分析是有问题的，举一个极端例子，在n 为 10000，且是有一条边的 图里，以上代码，大家感觉执行了多少次？

while (!pq.empty()) 中的 pq 存的是边，其实只执行了一次。

所以该算法时间复杂度 和 节点没有关系。

至于空间复杂度，邻接表是 数组 + 链表， 数组的空间 是 N ，有E条边 就申请对应多少个链表节点，所以是 复杂度是 $N + E$

拓展

当然也有录友可能想 堆优化dijkstra 中 我为什么一定要用邻接表呢，我就用邻接矩阵 行不行 ？

也行的。

但正是因为稀疏图，所以我们使用堆优化的思路， 如果我们还用 邻接矩阵 去表达这个图的话，就是 一个高效的算法 使用了低效的数据结构，那么 整体算法效率 依然是低的。

如果还不清楚为什么要使用 邻接表，可以再看看上面 我在 「图的存储」标题下的讲解。

这里我也给出 邻接矩阵版本的堆优化dijkstra代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;
// 小顶堆
class mycomparison {
public:
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid[p1][p2] = val;
    }

    int start = 1;  // 起点
    int end = n;    // 终点

    // 存储从源点到每个节点的最短距离
    std::vector<int>` minDist`(n + 1, INT_MAX);

    // 记录顶点是否被访问过
    std::vector<bool> visited(n + 1, false);

    // 优先队列中存放 pair<节点，源点到该节点的距离>
    priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;


    // 初始化队列，源点到源点的距离为0，所以初始为0
    pq.push(pair<int, int>(start, 0));

   ` minDist`[start] = 0;  // 起始点到自身的距离为0

    while (!pq.empty()) {
        // <节点， 源点到该节点的距离>
        // 1、选距离源点最近且未访问过的节点
        pair<int, int> cur = pq.top(); pq.pop();

        if (visited[cur.first]) continue;

        visited[cur.first] = true; // 2、标记该节点已被访问

        // 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && grid[cur.first][j] != INT_MAX && (minDist[cur.first] + grid[cur.first][j] <` minDist`[j])) {
               ` minDist`[j] =` minDist`[cur.first] + grid[cur.first][j];
                pq.push(pair<int, int>(j,` minDist`[j]));
            }
        }
    }

    if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点
    else cout <<` minDist`[end] << endl; // 到达终点最短路径

}
  • 时间复杂度：O(E * (N + logE)) E为边的数量，N为节点数量
  • 空间复杂度：O(log(N^2))

while (!pq.empty()) 时间复杂度为 $E$ ，while 里面 每次取元素 时间复杂度 为$ logE$，和 一个for循环 时间复杂度 为 N 。

所以整体是 $E * (N + logE)$

总结

在学习一种优化思路的时候，首先就要知道为什么要优化，遇到了什么问题。

正如我在开篇就给大家交代清楚 堆优化方式的背景。

堆优化的整体思路和 朴素版是大体一样的，区别是 堆优化从边的角度出发且利用堆来排序。

很多录友别说写堆优化 就是看 堆优化的代码也看的很懵。

主要是因为两点：

  • 不熟悉邻接表的表达方式
  • 对dijkstra的实现思路还是不熟

这是我为什么 本篇花了大力气来讲解 图的存储，就是为了让大家彻底理解邻接表以及邻接表的代码写法。

至于 dijkstra的实现思路 ，朴素版 和 堆优化版本 都是 按照 dijkstra 三部曲来的。

理解了三部曲，dijkstra 的思路就是清晰的。

针对邻接表版本代码 我做了详细的 时间复杂度分析，也让录友们清楚，相对于 朴素版，时间都优化到哪了。

最后 我也给出了 邻接矩阵的版本代码，分析了这一版本的必要性以及时间复杂度。

至此通过 两篇dijkstra的文章，终于把 dijkstra 讲完了，如果大家对我讲解里所涉及的内容都吃透的话，详细对 dijkstra 算法也就理解到位了。

10/14

Bellman_ford 算法精讲

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。

城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v （单向图）。

输出描述

如果能够从城市 1 到连通到城市 n， 请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 “unconnected”。

输入示例
1
2
3
4
5
6
7
8
6 7
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5
输出示例
1
1
提示信息

img

示例中最佳路径是从 1 -> 2 -> 5 -> 6，路上的权值分别为 1 2 -2，最终的最低运输成本为 1 + 2 + (-2) = 1。

示例 2：

4 2
1 2 -1
3 4 -1

在此示例中，无法找到一条路径从 1 通往 4，所以此时应该输出 “unconnected”。

数据范围：

1 <= n <= 1000；
1 <= m <= 10000;

-100 <= v <= 100;

思路

本题依然是单源最短路问题，求 从 节点1 到节点n 的最小费用。 但本题不同之处在于边的权值是有负数了。

从 节点1 到节点n 的最小费用也可以是负数，费用如果是负数则表示运输的过程中 政府补贴大于运输成本。

在求单源最短路的方法中，使用dijkstra的话，则要求图中边的权值都为正数。

我们在 dijkstra朴素版 中专门有讲解：为什么有边为负数 使用dijkstra就不行了。

本题是经典的带负权值的单源最短路问题，此时就轮到Bellman_ford登场了，接下来我们来详细介绍Bellman_ford 算法 如何解决这类问题。

详细介绍

该算法是由 R.Bellman 和L.Ford 在20世纪50年代末期发明的算法，故称为Bellman_ford算法。

Bellman_ford算法的核心思想是对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。

什么叫做松弛

看到这里，估计大家都比较晕了，为什么是 n-1 次，那“松弛”这两个字究竟是个啥意思？我们先来说什么是 “松弛”。

《算法四》里面把这个操作叫做 “放松”， 英文版里叫做 “relax the edge”所以大家翻译过来，就是 “放松” 或者 “松弛” 。

但《算法四》没有具体去讲这个 “放松” 究竟是个啥？ 网上很多题解也没有讲题解里的 “松弛这条边，松弛所有边”等等 里面的 “松弛” 究竟是什么意思？

这里我给大家举一个例子，每条边有起点、终点和边的权值。例如一条边，节点A 到 节点B 权值为value，如图：

img

minDist[B] 表示到达B节点最小权值，minDist[B] 有哪些状态可以推出来？

状态一： minDist[A] + value 可以推出 minDist[B]

状态二： minDist[B]本身就有权值 （可能是其他边链接的节点B :例如节点C，以至于minDist[B]记录了其他边到minDist[B]的权值）

minDist[B] 应为如何取舍。本题我们要求最小权值，那么 这两个状态我们就取最小的。

1
if (minDist[B] >` minDist`[A] + value)` minDist`[B] =` minDist`[A] + value

也就是说，如果 通过 A 到 B 这条边可以获得更短的到达B节点的路径，即如果 minDist[B] > minDist[A] + value，那么我们就更新 minDist[B] = minDist[A] + value ，这个过程就叫做 “松弛” 。

以上讲了这么多，其实都是围绕以下这句代码展开：

1
if (minDist[B] >` minDist`[A] + value)` minDist`[B] =` minDist`[A] + value

这句代码就是 Bellman_ford算法的核心操作。

以上代码也可以这么写：minDist[B] = min(minDist[A] + value, minDist[B])

如果大家看过代码随想录的动态规划章节，会发现 无论是背包问题还是子序列问题，这段代码（递推公式）出现频率非常高的。

其实 Bellman_ford算法 也是采用了动态规划的思想，即：将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解。

那么为什么是 n - 1次 松弛呢？

这里要给大家模拟一遍 Bellman_ford 的算法才行，接下来我们来看看对所有边松弛 n - 1 次的操作是什么样的。

我们依然使用minDist数组来表达 起点到各个节点的最短距离，例如minDist[3] = 5表示起点到达节点3 的最小距离为5

模拟过程

初始化过程。起点为节点1， 起点到起点的距离为0，所以 minDist[1] 初始化为0

如图：

img

其他节点对应的minDist初始化为max，因为我们要求最小距离，那么还没有计算过的节点 默认是一个最大数，这样才能更新最小距离。

对所有边 进行第一次松弛： （什么是松弛，在上面我已经详细讲过）

以示例给出的所有边为例：

1
2
3
4
5
6
7
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5

接下来我们来松弛一遍所有的边。

边：节点5 -> 节点6，权值为-2 ，minDist[5] 还是默认数值max，所以不能基于 节点5 去更新节点6，如图：

img

（在复习一下，minDist[5] 表示起点到节点5的最短距离）

边：节点1 -> 节点2，权值为1 ，minDist[2] > minDist[1] + 1 ，更新 minDist[2] = minDist[1] + 1 = 0 + 1 = 1 ，如图：

img

边：节点5 -> 节点3，权值为1 ，minDist[5] 还是默认数值max，所以不能基于节点5去更新节点3 如图：

img

边：节点2 -> 节点5，权值为2 ，minDist[5] > minDist[2] + 2 （经过上面的计算minDist[2]已经不是默认值，而是 1），更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 ，如图：

img

边：节点2 -> 节点4，权值为-3 ，minDist[4] > minDist[2] + (-3)，更新 minDist[4] = minDist[2] + (-3) = 1 + (-3) = -2 ，如图：

img

边：节点4 -> 节点6，权值为4 ，minDist[6] > minDist[4] + 4，更新 minDist[6] = minDist[4] + 4 = -2 + 4 = 2

img

边：节点1 -> 节点3，权值为5 ，minDist[3] > minDist[1] + 5，更新 minDist[3] = minDist[1] + 5 = 0 + 5 = 5，如图：

img

以上是对所有边进行一次松弛之后的结果。

那么需要对所有边松弛几次才能得到 起点（节点1） 到终点（节点6）的最短距离呢？

对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。

上面的距离中，我们得到里 起点达到 与起点一条边相邻的节点2 和 节点3 的最短距离，分别是 minDist[2] 和 minDist[3]

这里有录友疑惑了 minDist[3] = 5，分明不是 起点到达 节点3 的最短距离，节点1 -> 节点2 -> 节点5 -> 节点3 这条路线 距离才是4。

注意我上面讲的是 对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离，这里 说的是 一条边相连的节点。

与起点（节点1）一条边相邻的节点，到达节点2 最短距离是 1，到达节点3 最短距离是5。

而 节点1 -> 节点2 -> 节点5 -> 节点3 这条路线 是 与起点 三条边相连的路线了。

所以对所有边松弛一次 能得到 与起点 一条边相连的节点最短距离。

那对所有边松弛两次 可以得到与起点 两条边相连的节点的最短距离。

那对所有边松弛三次 可以得到与起点 三条边相连的节点的最短距离，这个时候，我们就能得到到达节点3真正的最短距离，也就是 节点1 -> 节点2 -> 节点5 -> 节点3 这条路线。

那么再回归刚刚的问题，需要对所有边松弛几次才能得到 起点（节点1） 到终点（节点6）的最短距离呢？

节点数量为n，那么起点到终点，最多是 n-1 条边相连。

那么无论图是什么样的，边是什么样的顺序，我们对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离

其实也同时计算出了，起点 到达 所有节点的最短距离，因为所有节点与起点连接的边数最多也就是 n-1 条边。

截止到这里，Bellman_ford 的核心算法思路，大家就了解的差不多了。

共有两个关键点。

  • “松弛”究竟是个啥？
  • 为什么要对所有边松弛 n - 1 次 （n为节点个数） ？

那么Bellman_ford的解题解题过程其实就是对所有边松弛 n-1 次，然后得出得到终点的最短路径。

代码

理解上面讲解的内容，代码就更容易写了，本题代码如下：（详细注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid;

    // 将所有边保存起来
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid.push_back({p1, p2, val});

    }
    int start = 1;  // 起点
    int end = n;    // 终点

    vector<int>` minDist`(n + 1 , INT_MAX);
   ` minDist`[start] = 0;
    for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次
        for (vector<int> &side : grid) { // 每一次松弛，都是对所有边进行松弛
            int from = side[0]; // 边的出发点
            int to = side[1]; // 边的到达点
            int price = side[2]; // 边的权值
            // 松弛操作 
            //` minDist`[from] != INT_MAX 防止从未计算过的节点出发
            if (minDist[from] != INT_MAX &&` minDist`[to] >` minDist`[from] + price) { 
               ` minDist`[to] =` minDist`[from] + price;  
            }
        }
    }
    if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点
    else cout <<` minDist`[end] << endl; // 到达终点最短路径

}
  • 时间复杂度：$ O(N * E) $, N为节点数量，E为图中边的数量
  • 空间复杂度： $O(N)$ ，即 minDist 数组所开辟的空间

关于空间复杂度，可能有录友疑惑，代码中数组grid不也开辟空间了吗？ 为什么只算minDist数组的空间呢？

grid数组是用来存图的，这是题目描述中必须要使用的空间，而不是我们算法所使用的空间。

我们在讲空间复杂度的时候，一般都是说，我们这个算法所用的空间复杂度。

拓展

有录友可能会想，那我 松弛 n 次，松弛 n + 1次，松弛 2 * n 次会怎么样？

其实没啥影响，结果不会变的，因为 题目中说了 “同时保证道路网络中不存在任何负权回路” 也就是图中没有 负权回路（在有向图中出现有向环 且环的总权值为负数）。

那么我们只要松弛 n - 1次 就一定能得到结果，没必要在松弛更多次了。

这里有疑惑的录友，可以加上打印 minDist数组 的日志，尝试一下，看看松弛 n 次会怎么样。

你会发现 松弛 大于 n - 1次，minDist数组 就不会变化了。

这里我给出打印日志的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid;

    // 将所有边保存起来
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid.push_back({p1, p2, val});

    }
    int start = 1;  // 起点
    int end = n;    // 终点

    vector<int>` minDist`(n + 1 , INT_MAX);
   ` minDist`[start] = 0;
    for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次
        for (vector<int> &side : grid) { // 每一次松弛，都是对所有边进行松弛
            int from = side[0]; // 边的出发点
            int to = side[1]; // 边的到达点
            int price = side[2]; // 边的权值
            // 松弛操作
            //` minDist`[from] != INT_MAX 防止从未计算过的节点出发
            if (minDist[from] != INT_MAX &&` minDist`[to] >` minDist`[from] + price) {
               ` minDist`[to] =` minDist`[from] + price;
            }
        }
        cout << "对所有边松弛 " << i << "次" << endl;
        for (int k = 1; k <= n; k++) {
            cout <<` minDist`[k] << " ";
        }
        cout << endl;
    }
    if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点
    else cout <<` minDist`[end] << endl; // 到达终点最短路径

}

通过打日志，大家发现，怎么对所有边进行第二次松弛以后结果就 不再变化了，那根本就不用松弛 n - 1 ？

这是本题的样例的特殊性， 松弛 n-1 次 是保证对任何图 都能最后求得到终点的最小距离。

如果还想不明白 我再举一个例子，用以下测试用例再跑一下。

1
2
3
4
5
6
6 5
5 6 1
4 5 1
3 4 1
2 3 1
1 2 1

打印结果：

1
2
3
4
5
6
7
8
9
10
对所有边松弛 1次
0 1 2147483647 2147483647 2147483647 2147483647
对所有边松弛 2次
0 1 2 2147483647 2147483647 2147483647
对所有边松弛 3次
0 1 2 3 2147483647 2147483647
对所有边松弛 4次
0 1 2 3 4 2147483647
对所有边松弛 5次
0 1 2 3 4 5

你会发现到 n-1 次 才打印出最后的最短路结果。

关于上面的讲解，大家一定要多写代码去实验，验证自己的想法。

至于 负权回路 ，我在下一篇会专门讲解这种情况，大家有个印象就好。

总结

Bellman_ford 是可以计算 负权值的单源最短路算法。

其算法核心思路是对 所有边进行 n-1 次 松弛。弄清楚

  • 什么是 松弛？
  • 为什么要 n-1 次？ 对理解Bellman_ford 非常重要。

Bellman_ford 队列优化算法（又名SPFA）

背景

本题我们来系统讲解 Bellman_ford 队列优化算法 ，也叫SPFA算法（Shortest Path Faster Algorithm）。

SPFA的称呼来自 1994年西南交通大学段凡丁的论文，其实Bellman_ford 提出后不久 （20世纪50年代末期） 就有队列优化的版本，国际上不承认这个算法是是国内提出的。 所以国际上一般称呼 该算法为 Bellman_ford 队列优化算法（Queue improved Bellman-Ford）

大家知道以上来历，知道 SPFA和 Bellman_ford 队列优化算法 指的都是一个算法就好。

如果大家还不够了解 Bellman_ford 算法，强烈建议按照《代码随想录》的顺序学习，否则可能看不懂下面的讲解。

大家可以发现 Bellman_ford算法每次松弛 都是对所有边进行松弛。

但真正有效的松弛，是基于已经计算过的节点在做的松弛。

给大家举一个例子：

img

本图中，对所有边进行松弛，真正有效的松弛，只有松弛 边（节点1->节点2） 和 边（节点1->节点3） 。

而松弛 边（节点4->节点6） ，边（节点5->节点3）等等 都是无效的操作，因为 节点4 和 节点 5 都是没有被计算过的节点。

所以 Bellman_ford 算法 每次都是对所有边进行松弛，其实是多做了一些无用功。

只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了。

基于以上思路，如何记录 上次松弛的时候更新过的节点呢？

用队列来记录。（其实用栈也行，对元素顺序没有要求）

模拟过程

接下来来举例这个队列是如何工作的。

以示例给出的所有边为例：

1
2
3
4
5
6
7
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5

我们依然使用minDist数组来表达 起点到各个节点的最短距离，例如minDist[3] = 5 表示起点到达节点3 的最小距离为5

初始化，起点为节点1， 起点到起点的最短距离为0，所以minDist[1] 为 0。 将节点1 加入队列 （下次松弛从节点1开始）

img

从队列里取出节点1，松弛节点1 作为出发点连接的边（节点1 -> 节点2）和边（节点1 -> 节点3）

边：节点1 -> 节点2，权值为1 ，minDist[2] > minDist[1] + 1 ，更新 minDist[2] = minDist[1] + 1 = 0 + 1 = 1。

边：节点1 -> 节点3，权值为5 ，minDist[3] > minDist[1] + 5，更新 minDist[3] = minDist[1] + 5 = 0 + 5 = 5。

将节点2、节点3 加入队列，如图：

img

从队列里取出节点2，松弛节点2 作为出发点连接的边（节点2 -> 节点4）和边（节点2 -> 节点5）

边：节点2 -> 节点4，权值为1 ，minDist[4] > minDist[2] + (-3) ，更新 minDist[4] = minDist[2] + (-3) = 1 + (-3) = -2 。

边：节点2 -> 节点5，权值为2 ，minDist[5] > minDist[2] + 2 ，更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 。

将节点4，节点5 加入队列，如图：

img

从队列里出去节点3，松弛节点3 作为出发点连接的边。

因为没有从节点3作为出发点的边，所以这里就从队列里取出节点3就好，不用做其他操作，如图：

img

从队列中取出节点4，松弛节点4作为出发点连接的边（节点4 -> 节点6）

边：节点4 -> 节点6，权值为4 ，minDist[6] > minDist[4] + 4，更新 minDist[6] = minDist[4] + 4 = -2 + 4 = 2 。

将节点6加入队列

如图：

img

从队列中取出节点5，松弛节点5作为出发点连接的边（节点5 -> 节点3），边（节点5 -> 节点6）

边：节点5 -> 节点3，权值为1 ，minDist[3] > minDist[5] + 1 ，更新` minDist[3] =minDist[5] + 1 = 3 + 1 = 4`

边：节点5 -> 节点6，权值为-2 ，minDist[6] > minDist[5] + (-2) ，更新 minDist[6] = minDist[5] + (-2) = 3 - 2 = 1

如图，将节点3加入队列，因为节点6已经在队列里，所以不用重复添加

img

所以我们在加入队列的过程可以有一个优化，用visited数组记录已经在队列里的元素，已经在队列的元素不用重复加入

从队列中取出节点6，松弛节点6 作为出发点连接的边。

节点6作为终点，没有可以出发的边。

同理从队列中取出节点3，也没有可以出发的边

所以直接从队列中取出，如图：

img

这样我们就完成了基于队列优化的bellman_ford的算法模拟过程。

大家可以发现 基于队列优化的算法，要比bellman_ford 算法 减少很多无用的松弛情况，特别是对于边数众多的大图 优化效果明显。

了解了大体流程，我们再看代码应该怎么写。

在上面模拟过程中，我们每次都要知道 一个节点作为出发点连接了哪些节点。

如果想方便知道这些数据，就需要使用邻接表来存储这个图，如果对于邻接表不了解的话，可以看 kama0047.参会dijkstra堆 中 图的存储 部分。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;

struct Edge { //邻接表
    int to;  // 链接的节点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};


int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<list<Edge>> grid(n + 1); 

    vector<bool> isInQueue(n + 1); // 加入优化，已经在队里里的元素不用重复添加

    // 将所有边保存起来
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid[p1].push_back(Edge(p2, val));
    }
    int start = 1;  // 起点
    int end = n;    // 终点

    vector<int>` minDist`(n + 1 , INT_MAX);
   ` minDist`[start] = 0;

    queue<int> que;
    que.push(start); 

    while (!que.empty()) {

        int node = que.front(); que.pop();
        isInQueue[node] = false; // 从队列里取出的时候，要取消标记，我们只保证已经在队列里的元素不用重复加入
        for (Edge edge : grid[node]) {
            int from = node;
            int to = edge.to;
            int value = edge.val;
            if (minDist[to] >` minDist`[from] + value) { // 开始松弛
               ` minDist`[to] =` minDist`[from] + value; 
                if (isInQueue[to] == false) { // 已经在队列里的元素不用重复添加
                    que.push(to);
                    isInQueue[to] = true;
                }
            }
        }

    }
    if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点
    else cout <<` minDist`[end] << endl; // 到达终点最短路径
}

效率分析

队列优化版Bellman_ford 的时间复杂度 并不稳定，效率高低依赖于图的结构。

例如 如果是一个双向图，且每一个节点和所有其他节点都相连的话，那么该算法的时间复杂度就接近于 Bellman_ford 的$ O(N * E)$ N 为节点数量，E为边的数量。

在这种图中，每一个节点都会重复加入队列 n - 1次，因为 这种图中 每个节点 都有 n-1 条指向该节点的边，每条边指向该节点，就需要加入一次队列。（如果这里看不懂，可以在重温一下代码逻辑）

至于为什么 双向图且每一个节点和所有其他节点都相连的话，每个节点 都有 n-1 条指向该节点的边， 我再来举个例子，如图：

img

图中 每个节点都与其他所有节点相连，节点数n 为 4，每个节点都有3条指向该节点的边，即入度为3。

n为其他数值的时候，也是一样的。

当然这种图是比较极端的情况，也是最稠密的图。

所以如果图越稠密，则 SPFA的效率越接近与Bellman_ford。

反之，图越稀疏，SPFA的效率就越高。

一般来说，SPFA 的时间复杂度为 $O(K * N),k\in{(1,E)}$ ，因为 节点需要计入几次队列取决于 图的稠密度。

如果图是一条线形图且单向的话，每个节点的入度为1，那么只需要加入一次队列，这样时间复杂度就是$ O(N)$。

所以 SPFA 在最坏的情况下是 $O(N E)$，但 一般情况下 时间复杂度为 $O(K N)$。

尽管如此，以上分析都是 理论上的时间复杂度分析。

并没有计算 出队列 和 入队列的时间消耗。 因为这个在不同语言上 时间消耗也是不一定的。

以C++为例，以下两段代码理论上，时间复杂度都是 O(n) ：

1
2
3
for (long long i = 0; i < n; i++) {
    k++;
}
1
2
3
4
5
for (long long i = 0; i < n; i++) {
    que.push(i);
    que.front();
    que.pop();
}

在 MacBook Pro (13-inch, M1, 2020) 机器上分别测试这两段代码的时间消耗情况：

  • n = 10^4，第一段代码的时间消耗：1ms，第二段代码的时间消耗： 4 ms
  • n = 10^5，第一段代码的时间消耗：1ms，第二段代码的时间消耗： 13 ms
  • n = 10^6，第一段代码的时间消耗：4ms，第二段代码的时间消耗： 59 ms
  • n = 10^7，第一段代码的时间消耗: 24ms，第二段代码的时间消耗： 463 ms
  • n = 10^8，第一段代码的时间消耗: 135ms，第二段代码的时间消耗： 4268 ms

在这里就可以看出 出队列和入队列 其实也是十分耗时的。

SPFA（队列优化版Bellman_ford） 在理论上 时间复杂度更胜一筹，但实际上，也要看图的稠密程度，如果 图很大且非常稠密的情况下，虽然 SPFA的时间复杂度接近Bellman_ford，但实际时间消耗 可能是 SPFA耗时更多。

针对这种情况，我在后面题目讲解中，会特别加入稠密图的测试用例来给大家讲解。

拓展

这里可能有录友疑惑，while (!que.empty()) 队里里 会不会造成死循环？ 例如 图中有环，这样一直有元素加入到队列里？

其实有环的情况，要看它是 正权回路还是负权回路。

题目描述中，已经说了，本题没有 负权回路 。

如图：

img

正权回路 就是有环，但环的总权值为正数。

在有环且只有正权回路的情况下，即使元素重复加入队列，最后，也会因为 所有边都松弛后，节点数值（minDist数组）不在发生变化了 而终止。

（而且有重复元素加入队列是正常的，多条路径到达同一个节点，节点必要要选择一个最短的路径，而这个节点就会重复加入队列进行判断，选一个最短的）

在0094.城市间货物运输I 中我们讲过对所有边 最多松弛 n -1 次，就一定可以求出所有起点到所有节点的最小距离即 minDist数组。

即使再松弛n次以上， 所有起点到所有节点的最小距离（minDist数组） 不会再变了。

所以本题我们使用队列优化，有元素重复加入队列，也会因为最后minDist数组 不会在发生变化而终止。

节点再加入队列，需要有松弛的行为， 而 每个节点已经都计算出来 起点到该节点的最短路径，那么就不会有 执行这个判断条件if (minDist[to] > minDist[from] + value)，从而不会有新的节点加入到队列。

但如果本题有 负权回路，那情况就不一样了，我在下一题目讲解中，会重点讲解 负权回路 带来的变化。

bellman_ford之判断负权回路

城市间货物运输 II

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

然而，在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时，存在一种情况：图中可能出现负权回路。负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴，算法还需检测这种特殊情况。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。

城市 1 到城市 n 之间可能会出现没有路径的情况

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v。

输出描述

如果没有发现负权回路，则输出一个整数，表示从城市 1 到城市 n 的最低运输成本（包括政府补贴）。如果该整数是负数，则表示实现了盈利。如果发现了负权回路的存在，则输出 “circle”。如果从城市 1 无法到达城市 n，则输出 “unconnected”。

输入示例
1
2
3
4
5
4 4
1 2 -1
2 3 1
3 1 -1 
3 4 1
输出示例
1
circle
提示信息

路径中存在负权回路，从 1 -> 2 -> 3 -> 1，总权值为 -1，理论上货物运输商可以在该回路无限循环赚取政府补贴，所以输出 “circle” 表示已经检测出了该种情况。

数据范围：

1 <= n <= 1000；
1 <= m <= 10000;

-100 <= v <= 100;

思路

本题是 kama94.城市间货物运输I 延伸题目。

本题是要我们判断 负权回路，也就是图中出现环且环上的边总权值为负数。

如果在这样的图中求最短路的话， 就会在这个环里无限循环 （也是负数+负数 只会越来越小），无法求出最短路径。

所以对于 在有负权值的图中求最短路，都需要先看看这个图里有没有负权回路。

接下来我们来看 如何使用 bellman_ford 算法来判断 负权回路。

在 kama94.城市间货物运输I 中 我们讲了 bellman_ford 算法的核心就是一句话：对 所有边 进行 n-1 次松弛。 同时文中的 【拓展】部分， 我们也讲了 松弛n次以上 会怎么样？

在没有负权回路的图中，松弛 n 次以上 ，结果不会有变化。

但本题有 负权回路，如果松弛 n 次，结果就会有变化了，因为 有负权回路 就是可以无限最短路径（一直绕圈，就可以一直得到无限小的最短距离）。

那么每松弛一次，都会更新最短路径，所以结果会一直有变化。

以上为理论分析，接下来我们再画图举例。

我们拿题目中示例来画一个图：

img

图中 节点1 到 节点4 的最短路径是多少（题目中的最低运输成本） （注意边可以为负数的）

节点1 -> 节点2 -> 节点3 -> 节点4，这样的路径总成本为 -1 + 1 + 1 = 1

而图中有负权回路：

img

那么我们在负权回路中多绕一圈，我们的最短路径 是不是就更小了 （也就是更低的运输成本）

节点1 -> 节点2 -> 节点3 -> 节点1 -> 节点2 -> 节点3 -> 节点4，这样的路径总成本 (-1) + 1 + (-1) + (-1) + 1 + (-1) + 1 = -1

如果在负权回路多绕两圈，三圈，无穷圈，那么我们的总成本就会无限小， 如果要求最小成本的话，你会发现本题就无解了。

在 bellman_ford 算法中，松弛 n-1 次所有的边 就可以求得 起点到任何节点的最短路径，松弛 n 次以上，minDist数组（记录起到到其他节点的最短距离）中的结果也不会有改变 （如果对 bellman_ford 算法 不了解，也不知道minDist 是什么，建议详看上篇讲解kama94.城市间货物运输I）

而本题有负权回路的情况下，一直都会有更短的最短路，所以 松弛 第n次，minDist数组 也会发生改变。

那么解决本题的 核心思路，就是在 [kama94.城市间货物运输I]的基础上，再多松弛一次，看minDist数组 是否发生变化。

代码和 kama94.城市间货物运输I 基本是一样的，如下：（关键地方已注释）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid;

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid.push_back({p1, p2, val});

    }
    int start = 1;  // 起点
    int end = n;    // 终点

    vector<int>` minDist`(n + 1 , INT_MAX);
   ` minDist`[start] = 0;
    bool flag = false;
    for (int i = 1; i <= n; i++) { // 这里我们松弛n次，最后一次判断负权回路
        for (vector<int> &side : grid) {
            int from = side[0];
            int to = side[1];
            int price = side[2];
            if (i < n) {
                if (minDist[from] != INT_MAX &&` minDist`[to] >` minDist`[from] + price)` minDist`[to] =` minDist`[from] + price;
            } else { // 多加一次松弛判断负权回路
                if (minDist[from] != INT_MAX &&` minDist`[to] >` minDist`[from] + price) flag = true;

            }
        }

    }

    if (flag) cout << "circle" << endl;
    else if (minDist[end] == INT_MAX) {
        cout << "unconnected" << endl;
    } else {
        cout <<` minDist`[end] << endl;
    }
}
  • 时间复杂度： $O(N * E)$ , N为节点数量，E为图中边的数量
  • 空间复杂度： $O(N)$ ，即minDist 数组所开辟的空间

拓展

本题可不可 使用 队列优化版的bellman_ford（SPFA）呢？

上面的解法中，我们对所有边松弛了n-1次后，在松弛一次，如果出现minDist出现变化就判断有负权回路。

如果使用 SPFA 那么节点都是进队列的，那么节点进入队列几次后 足够判断该图是否有负权回路呢？

在 0094.城市间货物运输I-SPFA 中，我们讲过 在极端情况下，即：所有节点都与其他节点相连，每个节点的入度为n-1（n为节点数量），所以每个节点最多加入n-1 次队列。

那么如果节点加入队列的次数 超过了 n-1次 ，那么该图就一定有负权回路。

所以本题也是可以使用 SPFA 来做的。 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;

struct Edge { //邻接表
    int to;  // 链接的节点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};


int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<list<Edge>> grid(n + 1); // 邻接表

    // 将所有边保存起来
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid[p1].push_back(Edge(p2, val));
    }
    int start = 1;  // 起点
    int end = n;    // 终点

    vector<int>` minDist`(n + 1 , INT_MAX);
   ` minDist`[start] = 0;

    queue<int> que;
    que.push(start); // 队列里放入起点 
    
    vector<int> count(n+1, 0); // 记录节点加入队列几次
    count[start]++;

    bool flag = false;
    while (!que.empty()) {

        int node = que.front(); que.pop();

        for (Edge edge : grid[node]) {
            int from = node;
            int to = edge.to;
            int value = edge.val;
            if (minDist[to] >` minDist`[from] + value) { // 开始松弛
               ` minDist`[to] =` minDist`[from] + value;
                que.push(to);
                count[to]++; 
                if (count[to] == n) {// 如果加入队列次数超过 n-1次 就说明该图与负权回路
                    flag = true;
                    while (!que.empty()) que.pop();
                    break;
                }
            }
        }
    }

    if (flag) cout << "circle" << endl;
    else if (minDist[end] == INT_MAX) {
        cout << "unconnected" << endl;
    } else {
        cout <<` minDist`[end] << endl;
    }

}

10/15

bellman_ford之单源有限最短路

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请计算在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本。

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v。

最后一行包含三个正整数，src、dst、和 k，src 和 dst 为城市编号，从 src 到 dst 经过的城市数量限制。

输出描述

输出一个整数，表示从城市 src 到城市 dst 的最低运输成本，如果无法在给定经过城市数量限制下找到从 src 到 dst 的路径，则输出 “unreachable”，表示不存在符合条件的运输方案。

输入示例
1
2
3
4
5
6
7
8
9
6 7
1 2 1
2 4 -3
2 5 2
1 3 5
3 5 1
4 6 4
5 6 -2
2 6 1
输出示例
1
0
提示信息

从 2 -> 5 -> 6 中转一站，运输成本为 0。

1 <= n <= 1000；

1 <= m <= 10000;

-100 <= v <= 100;

思路：

本题为单源有限最短路问题，同样是 kama94.城市间货物运输I 延伸题目。

注意题目中描述是 最多经过 k 个城市的条件下，而不是一定经过k个城市，也可以经过的城市数量比k小，但要最短的路径。

在 kama94.城市间货物运输I 中我们讲了：对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。

节点数量为n，起点到终点，最多是 n-1 条边相连。 那么对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离。

（如果对以上讲解看不懂，建议详看 kama94.城市间货物运输I ）

本题是最多经过 k 个城市， 那么是 k + 1条边相连的节点。 这里可能有录友想不懂为什么是k + 1，来看这个图：

img

图中，节点1 最多已经经过2个节点 到达节点4，那么中间是有多少条边呢，是 3 条边对吧。

所以本题就是求：起点最多经过k + 1 条边到达终点的最短距离。

对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离，那么对所有边松弛 k + 1次，就是求 起点到达 与起点k + 1条边相连的节点的 最短距离。

注意： 本题是 kama94.城市间货物运输I 的拓展题，如果对bellman_ford 没有深入了解，强烈建议先看 kama94.城市间货物运输I 再做本题。

理解以上内容，其实本题代码就很容易了，bellman_ford 标准写法是松弛 n-1 次，本题就松弛 k + 1次就好。

此时我们可以写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 版本一
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int src, dst,k ,p1, p2, val ,m , n;
    
    cin >> n >> m;

    vector<vector<int>> grid;

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid.push_back({p1, p2, val});
    }

    cin >> src >> dst >> k;

    vector<int>` minDist`(n + 1 , INT_MAX);
   ` minDist`[src] = 0;
    for (int i = 1; i <= k + 1; i++) { // 对所有边松弛 k + 1次
        for (vector<int> &side : grid) {
            int from = side[0];
            int to = side[1];
            int price = side[2];
            if (minDist[from] != INT_MAX &&` minDist`[to] >` minDist`[from] + price)` minDist`[to] =` minDist`[from] + price;
        }

    }

    if (minDist[dst] == INT_MAX) cout << "unreachable" << endl; // 不能到达终点
    else cout <<` minDist`[dst] << endl; // 到达终点最短路径

}

以上代码 标准 bellman_ford 写法，松弛 k + 1次，看上去没什么问题。

但大家提交后，居然没通过！

这是为什么呢？

接下来我们拿这组数据来举例：

1
2
3
4
5
6
4 4
1 2 -1
2 3 1
3 1 -1
3 4 1
1 4 3

（注意上面的示例是有负权回路的，只有带负权回路的图才能说明问题）

负权回路是指一条道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。

正常来说，这组数据输出应该是 1，但以上代码输出的是 -2。

在讲解原因的时候，强烈建议大家，先把minDist数组打印出来，看看minDist数组是不是按照自己的想法变化的，这样更容易理解我接下来的讲解内容。 （一定要动手，实践出真实，脑洞模拟不靠谱）

打印的代码可以是这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int src, dst,k ,p1, p2, val ,m , n;
    
    cin >> n >> m;

    vector<vector<int>> grid;

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid.push_back({p1, p2, val});
    }

    cin >> src >> dst >> k;

    vector<int>` minDist`(n + 1 , INT_MAX);
   ` minDist`[src] = 0;
    for (int i = 1; i <= k + 1; i++) { // 对所有边松弛 k + 1次
        for (vector<int> &side : grid) {
            int from = side[0];
            int to = side[1];
            int price = side[2];
            if (minDist[from] != INT_MAX &&` minDist`[to] >` minDist`[from] + price)` minDist`[to] =` minDist`[from] + price;
        }
        // 打印` minDist` 数组 
        for (int j = 1; j <= n; j++) cout <<` minDist`[j] << " ";
        cout << endl;

    }

    if (minDist[dst] == INT_MAX) cout << "unreachable" << endl; // 不能到达终点
    else cout <<` minDist`[dst] << endl; // 到达终点最短路径

}

接下来，我按照上面的示例带大家 画图举例 对所有边松弛一次 的效果图。

起点为节点1， 起点到起点的距离为0，所以minDist[1] 初始化为0 ，如图：

img

其他节点对应的minDist初始化为max，因为我们要求最小距离，那么还没有计算过的节点 默认是一个最大数，这样才能更新最小距离。

当我们开始对所有边开始第一次松弛：

边：节点1 -> 节点2，权值为-1 ，minDist[2] >minDist[1] + (-1)，更新minDist[2] =minDist[1] + (-1) = 0 - 1 = -1 ，如图：

img

边：节点2 -> 节点3，权值为1 ，minDist[3] >minDist[2] + 1 ，更新minDist[3] =minDist[2] + 1 = -1 + 1 = 0 ，如图： img

边：节点3 -> 节点1，权值为-1 ，minDist[1] >minDist[3] + (-1)，更新minDist[1] = 0 + (-1) = -1 ，如图：

img

边：节点3 -> 节点4，权值为1 ，minDist[4] >minDist[3] + 1，更新minDist[4] = 0 + (1) = 1 ，如图(图误)：

img

以上是对所有边进行的第一次松弛，最后minDist数组为 ：-1 -1 0 1 ，（从下标1算起）

后面几次松弛我就不挨个画图了，过程大同小异，我直接给出minDist数组的变化：

所有边进行的第二次松弛，minDist数组为 ： -2 -2 -1 0 所有边进行的第三次松弛，minDist数组为 ： -3 -3 -2 -1 所有边进行的第四次松弛，minDist数组为 ： -4 -4 -3 -2 （本示例中k为3，所以松弛4次）

最后计算的结果minDist[4] = -2，即 起点到 节点4，最多经过 3 个节点的最短距离是 -2，但 正确的结果应该是 1，即路径：节点1 -> 节点2 -> 节点3 -> 节点4。

理论上来说，对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。

对所有边松弛两次，相当于计算 起点到达 与起点两条边相连的节点的最短距离。

对所有边松弛三次，以此类推。

但在对所有边松弛第一次的过程中，大家会发现，不仅仅 与起点一条边相连的节点更新了，所有节点都更新了。

而且对所有边的后面几次松弛，同样是更新了所有的节点，说明 至多经过k 个节点 这个限制 根本没有限制住，每个节点的数值都被更新了。这是为什么？

在上面画图距离中，对所有边进行第一次松弛，在计算 边（节点2 -> 节点3） 的时候，更新了 节点3。

img

理论上来说节点3 应该在对所有边第二次松弛的时候才更新。 这因为当时是基于已经计算好的 节点2（minDist[2]）来做计算了。

minDist[2]在计算边：（节点1 -> 节点2）的时候刚刚被赋值为 -1。

这样就造成了一个情况，即：计算minDist数组的时候，基于了本次松弛的minDist数值，而不是上一次 松弛时候minDist的数值。
所以在每次计算minDist 时候，要基于 对所有边上一次松弛的minDist 数值才行，所以我们要记录上一次松弛的minDist。

代码修改如下： （关键地方已经注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 版本二
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int src, dst,k ,p1, p2, val ,m , n;
    
    cin >> n >> m;

    vector<vector<int>> grid;

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid.push_back({p1, p2, val});
    }

    cin >> src >> dst >> k;

    vector<int>` minDist`(n + 1 , INT_MAX);
   ` minDist`[src] = 0;
    vector<int>` minDist`_copy(n + 1); // 用来记录上一次遍历的结果
    for (int i = 1; i <= k + 1; i++) {
       ` minDist`_copy =` minDist`; // 获取上一次计算的结果
        for (vector<int> &side : grid) {
            int from = side[0];
            int to = side[1];
            int price = side[2];
            // 注意使用` minDist`_copy 来计算` minDist` 
            if (minDist_copy[from] != INT_MAX &&` minDist`[to] >` minDist`_copy[from] + price) {  
               ` minDist`[to] =` minDist`_copy[from] + price;
            }
        }
    }
    if (minDist[dst] == INT_MAX) cout << "unreachable" << endl; // 不能到达终点
    else cout <<` minDist`[dst] << endl; // 到达终点最短路径

}
  • 时间复杂度： $O(K * E)$ , K为至多经过K个节点，E为图中边的数量
  • 空间复杂度： $O(N) $，即minDist 数组所开辟的空间

拓展一（边的顺序的影响）

其实边的顺序会影响我们每一次拓展的结果。

我来给大家举个例子。

我上面讲解中，给出的示例是这样的：

1
2
3
4
5
6
4 4
1 2 -1
2 3 1
3 1 -1
3 4 1
1 4 3

我将示例中边的顺序改一下，给成：

1
2
3
4
5
6
4 4
3 1 -1
3 4 1
2 3 1
1 2 -1
1 4 3

所构成是图是一样的，都是如下的这个图，但给出的边的顺序是不一样的。

img

再用版本一的代码是运行一下，发现结果输出是 1， 是对的。

img

分明刚刚输出的结果是 -2，是错误的，怎么 一样的图，这次输出的结果就对了呢？

其实这是和示例中给出的边的顺序是有关的，

我们按照修改后的示例再来模拟 对所有边的第一次拓展情况。

初始化：

img

边：节点3 -> 节点1，权值为-1 ，节点3还没有被计算过，节点1 不更新。

边：节点3 -> 节点4，权值为1 ，节点3还没有被计算过，节点4 不更新。

边：节点2 -> 节点3，权值为 1 ，节点2还没有被计算过，节点3 不更新。

边：节点1 -> 节点2，权值为 -1 ，minDist[2] >minDist[1] + (-1)，更新minDist[2] = 0 + (-1) = -1 ，如图：

img

以上是对所有边 松弛一次的状态。

可以发现 同样的图，边的顺序不一样，使用版本一的代码 每次松弛更新的节点也是不一样的。

而边的顺序是随机的，是题目给我们的，所以本题我们才需要 记录上一次松弛的minDist，来保障 每一次对所有边松弛的结果。

拓展二（本题本质）

那么前面讲解过的 94.城市间货物运输I 和 95.城市间货物运输II 也是bellman_ford经典算法，也没使用minDist_copy，怎么就没问题呢？

如果没看过我上面这两篇讲解的话，建议详细学习上面两篇，再看我下面讲的区别，否则容易看不懂。

94.城市间货物运输I， 是没有 负权回路的，那么 多松弛多少次，对结果都没有影响。

求 节点1 到 节点n 的最短路径，松弛n-1 次就够了，松弛 大于 n-1次，结果也不会变。

那么在对所有边进行第一次松弛的时候，如果基于 本次计算的minDist 来计算minDist （相当于多做松弛了），也是对最终结果没影响。

95.城市间货物运输II 是判断是否有 负权回路，一旦有负权回路， 对所有边松弛 n-1 次以后，在做松弛minDist 数值一定会变，根据这一点来判断是否有负权回路。

所以，95.城市间货物运输II 只需要判断minDist数值变化了就行，而minDist 的数值对不对，并不是我们关心的。

那么本题 为什么计算minDist一定要基于上次 的minDist 数值。

其关键在于本题的两个因素：

  • 本题可以有负权回路，说明只要多做松弛，结果是会变的。
  • 本题要求最多经过k个节点，对松弛次数是有限制的。

如果本题中 没有负权回路的测试用例， 那版本一的代码就可以过了，也就不用我费这么大口舌去讲解的这个坑了。

拓展三（SPFA）

本题也可以用 SPFA来做，关于SPFA ，已经在这里 0094.城市间货物运输I-SPFA 有详细讲解。

使用SPFA算法解决本题的时候，关键在于 如何控制松弛k次。

其实实现不难，但有点技巧，可以用一个变量 que_size记录每一轮松弛入队列的所有节点数量。

下一轮松弛的时候，就把队列里 que_size个节点都弹出来，就是上一轮松弛入队列的节点。

代码如下（详细注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;

struct Edge { //邻接表
    int to;  // 链接的节点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};


int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<list<Edge>> grid(n + 1); // 邻接表

    // 将所有边保存起来
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid[p1].push_back(Edge(p2, val));
    }
    int start, end, k;
    cin >> start >> end >> k;

    k++;

    vector<int> minDist(n + 1 , INT_MAX);
    vector<int> minDist_copy(n + 1); // 用来记录每一次遍历的结果

    minDist[start] = 0;

    queue<int> que;
    que.push(start); // 队列里放入起点

    int que_size;
    while (k-- && !que.empty()) {

        minDist_copy = minDist; // 获取上一次计算的结果
        que_size = que.size(); // 记录上次入队列的节点个数
        while (que_size--) { // 上一轮松弛入队列的节点，这次对应的边都要做松弛
            int node = que.front(); que.pop();
            for (Edge edge : grid[node]) {
                int from = node;
                int to = edge.to;
                int price = edge.val;
                if (minDist[to] > minDist_copy[from] + price) {
                    minDist[to] = minDist_copy[from] + price;
                    que.push(to);
                }
            }

        }
    }
    if (minDist[end] == INT_MAX) cout << "unreachable" << endl;
    else cout << minDist[end] << endl;

}

时间复杂度： $O(K * H) $ H 为不确定数，取决于 图的稠密度，但H 一定是小于等于 E 的

关于 SPFA的是时间复杂度分析，我在0094.城市间货物运输I-SPFA 有详细讲解

但大家会发现，以上代码大家提交后，怎么耗时这么多？

img

理论上，SPFA的时间复杂度不是要比 bellman_ford 更优吗？

怎么耗时多了这么多呢？

以上代码有一个可以改进的点，每一轮松弛中，重复节点可以不用入队列。

因为重复节点入队列，下次从队列里取节点的时候，该节点要取很多次，而且都是重复计算。

所以代码可以优化成这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;

struct Edge { //邻接表
    int to;  // 链接的节点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};


int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<list<Edge>> grid(n + 1); // 邻接表

    // 将所有边保存起来
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid[p1].push_back(Edge(p2, val));
    }
    int start, end, k;
    cin >> start >> end >> k;

    k++;

    vector<int> minDist(n + 1 , INT_MAX);
    vector<int> minDist_copy(n + 1); // 用来记录每一次遍历的结果

    minDist[start] = 0;

    queue<int> que;
    que.push(start); // 队列里放入起点

    int que_size;
    while (k-- && !que.empty()) {

        vector<bool> visited(n + 1, false); // 每一轮松弛中，控制节点不用重复入队列
        minDist_copy = minDist; 
        que_size = que.size(); 
        while (que_size--) { 
            int node = que.front(); que.pop();
            for (Edge edge : grid[node]) {
                int from = node;
                int to = edge.to;
                int price = edge.val;
                if (minDist[to] > minDist_copy[from] + price) {
                    minDist[to] = minDist_copy[from] + price;
                    if(visited[to]) continue; // 不用重复放入队列，但需要重复松弛，所以放在这里位置
                    visited[to] = true;
                    que.push(to);
                }
            }

        }
    }
    if (minDist[end] == INT_MAX) cout << "unreachable" << endl;
    else cout << minDist[end] << endl;
}

以上代码提交后，耗时情况：

img

大家发现 依然远比 bellman_ford 的代码版本 耗时高。

这又是为什么呢？

对于后台数据，我特别制作的一个稠密大图，该图有250个节点和10000条边， 在这种情况下， SPFA 的时间复杂度 是接近与 bellman_ford的。

但因为 SPFA 节点的进出队列操作，耗时很大，所以相同的时间复杂度的情况下，SPFA 实际上更耗时了。

这一点我在 0094.城市间货物运输I-SPFA 有分析，感兴趣的录友再回头去看看。

拓展四（能否用dijkstra）

本题能否使用 dijkstra 算法呢？

dijkstra 是贪心的思路 每一次搜索都只会找距离源点最近的非访问过的节点。

如果限制最多访问k个节点，那么 dijkstra 未必能在有限次就能到达终点，即使在经过k个节点确实可以到达终点的情况下。

这么说大家会感觉有点抽象，我用 dijkstra朴素版精讲 里的示例在举例说明： （如果没看过我讲的dijkstra朴素版精讲，建议去仔细看一下，否则下面讲解容易看不懂）

在以下这个图中，求节点1 到 节点7 最多经过2个节点 的最短路是多少呢？

img

最短路显然是：

img

最多经过2个节点，也就是3条边相连的路线：节点1 -> 节点2 -> 节点6-> 节点7

如果是 dijkstra 求解的话，求解过程是这样的： （下面是dijkstra的模拟过程，我精简了很多，如果看不懂，一定要先看dijkstra朴素版精讲）

初始化如图所示：

img

找距离源点最近且没有被访问过的节点，先找节点1

img

距离源点最近且没有被访问过的节点，找节点2：

img

距离源点最近且没有被访问过的节点，找到节点3：

img

距离源点最近且没有被访问过的节点，找到节点4：

img

此时最多经过2个节点的搜索就完毕了，但结果中minDist[7] （即节点7的结果）并没有被更。

那么 dijkstra 会告诉我们 节点1 到 节点7 最多经过2个节点的情况下是不可到达的。

通过以上模拟过程，大家应该能感受到 dijkstra 贪心的过程，正是因为 贪心，所以 dijkstra 找不到 节点1 -> 节点2 -> 节点6-> 节点7 这条路径。

总结

本题是单源有限最短路问题，也是 bellman_ford的一个拓展问题，如果理解bellman_ford 其实思路比较容易理解，但有很多细节。

例如 为什么要用minDist_copy 来记录上一轮 松弛的结果。 这也是本篇我为什么花了这么大篇幅讲解的关键所在。

接下来，还给大家做了四个拓展：

  • 边的顺序的影响
  • 本题的本质
  • SPFA的解法
  • 能否用dijkstra

学透了以上四个拓展，相信大家会对bellman_ford有更深入的理解。

Floyd 算法精讲

97.小明逛公园

题目描述

小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。

给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。

小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。 请你帮助小明计算出每个观景计划的最短路径长度。

输入描述

第一行包含两个整数 N, M, 分别表示景点的数量和道路的数量。

接下来的 M 行，每行包含三个整数 u, v, w，表示景点 u 和景点 v 之间有一条长度为 w 的双向道路。

接下里的一行包含一个整数 Q，表示观景计划的数量。

接下来的 Q 行，每行包含两个整数 start, end，表示一个观景计划的起点和终点。

输出描述

对于每个观景计划，输出一行表示从起点到终点的最短路径长度。如果两个景点之间不存在路径，则输出 -1。

输入示例
1
2
3
4
5
6
7
7 3
2 3 4
3 6 6
4 7 8
2
2 3
3 4
输出示例
1
2
4
-1
提示信息

从 2 到 3 的路径长度为 4，3 到 4 之间并没有道路。

1 <= N, M, Q <= 1000.

1 <= w <= 10000.

思路

本题是经典的多源最短路问题。

在这之前我们讲解过，dijkstra朴素版、dijkstra堆优化、Bellman算法、Bellman队列优化（SPFA） 都是单源最短路，即只能有一个起点。

而本题是多源最短路，即 求多个起点到多个终点的多条最短路径。

通过本题，我们来系统讲解一个新的最短路算法-Floyd 算法。

Floyd 算法对边的权值正负没有要求，都可以处理。

Floyd算法核心思想是动态规划。

例如我们再求节点1 到 节点9 的最短距离，用二维数组来表示即：grid[1] [9]，如果最短距离是10 ，那就是 grid[1] [9] = 10。

那 节点1 到 节点9 的最短距离 是不是可以由 节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成呢？

即 grid[1] [9] = grid[1] [5] + grid[5] [9]

节点1 到节点5的最短距离 是不是可以有 节点1 到 节点3的最短距离 + 节点3 到 节点5 的最短距离组成呢？

即 grid[1] [5] = grid[1] [3] + grid[3] [5]

以此类推，节点1 到 节点3的最短距离 可以由更小的区间组成。

那么这样我们是不是就找到了，子问题推导求出整体最优方案的递归关系呢。

节点1 到 节点9 的最短距离 可以由 节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成， 也可以有 节点1 到节点7的最短距离 + 节点7 到节点9的最短距离的距离组成。

那么选哪个呢？

是不是 要选一个最小的，毕竟是求最短路。

此时我们已经接近明确递归公式了。

之前在讲解动态规划的时候，给出过动规五部曲：

  • 确定dp数组（dp table）以及下标的含义
  • 确定递推公式
  • dp数组如何初始化
  • 确定遍历顺序
  • 举例推导dp数组

那么接下来我们还是用这五部来给大家讲解 Floyd。

1、确定dp数组（dp table）以及下标的含义

这里我们用 grid数组来存图，那就把dp数组命名为 grid。

grid[i] [j] [k] = m，表示 节点i 到 节点j 以[1…k] 集合为中间节点的最短距离为m。

可能有录友会想，凭什么就这么定义呢？

节点i 到 节点j 的最短距离为m，这句话可以理解，但 以[1…k]集合为中间节点就理解不辽了。

节点i 到 节点j 的最短路径中 一定是经过很多节点，那么这个集合用[1…k] 来表示。

你可以反过来想，节点i 到 节点j 中间一定经过很多节点，那么你能用什么方式来表述中间这么多节点呢？

所以 这里的k不能单独指某个节点，k 一定要表示一个集合，即[1…k] ，表示节点1 到 节点k 一共k个节点的集合。

2、确定递推公式

在上面的分析中我们已经初步感受到了递推的关系。

我们分两种情况：

  1. 节点i 到 节点j 的最短路径经过节点k
  2. 节点i 到 节点j 的最短路径不经过节点k

对于第一种情况，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]

节点i 到 节点k 的最短距离 是不经过节点k，中间节点集合为[1…k-1]，所以 表示为grid[i][k][k - 1]

节点k 到 节点j 的最短距离 也是不经过节点k，中间节点集合为[1…k-1]，所以表示为 grid[k][j][k - 1]

第二种情况，grid[i][j][k] = grid[i][j][k - 1]

如果节点i 到 节点j的最短距离 不经过节点k，那么 中间节点集合[1…k-1]，表示为 grid[i][j][k - 1]

因为我们是求最短路，对于这两种情况自然是取最小值。

即： grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

3、dp数组如何初始化

grid[i] [j] [k] = m，表示 节点i 到 节点j 以[1…k] 集合为中间节点的最短距离为m。

刚开始初始化k 是不确定的。

例如题目中只是输入边（节点2 -> 节点6，权值为3），那么grid[2] [6] [k] = 3，k需要填什么呢？

把k 填成1，那如何上来就知道 节点2 经过节点1 到达节点6的最短距离是多少 呢。

所以 只能 把k 赋值为 0，本题 节点0 是无意义的，节点是从1 到 n。

这样我们在下一轮计算的时候，就可以根据 grid[i] [j] [0]来计算 grid[i] [j] [1]，此时的 grid[i] [j] [1] 就是 节点i 经过节点1 到达 节点j 的最小距离了。

grid数组是一个三维数组，那么我们初始化的数据在 i 与 j 构成的平层，如图：

img

红色的 底部一层是我们初始化好的数据，注意：从三维角度去看初始化的数据很重要，下面我们在聊遍历顺序的时候还会再讲。

所以初始化代码：

1
2
3
4
5
6
7
vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));  // C++定义了一个三位数组，10005是因为边的最大距离是10^4

for(int i = 0; i < m; i++){
    cin >> p1 >> p2 >> val;
    grid[p1][p2][0] = val;
    grid[p2][p1][0] = val; // 注意这里是双向图
}

grid数组中其他元素数值应该初始化多少呢？

本题求的是最小值，所以输入数据没有涉及到的节点的情况都应该初始为一个最大数。

这样才不会影响，每次计算去最小值的时候 初始值对计算结果的影响。

所以grid数组的定义可以是：

1
2
// C++写法，定义了一个三位数组，10005是因为边的最大距离是10^4
vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));

4、确定遍历顺序

从递推公式：grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1]) 可以看出，我们需要三个for循环，分别遍历i，j 和k

而 k 依赖于 k - 1， i 和j 的到 并不依赖与 i - 1 或者 j - 1 等等。

那么这三个for的嵌套顺序应该是什么样的呢？

我们来看初始化，我们是把 k =0 的 i 和j 对应的数值都初始化了，这样才能去计算 k = 1 的时候 i 和 j 对应的数值。

这就好比是一个三维坐标，i 和j 是平层，而k 是 垂直向上 的。

遍历的顺序是从底向上 一层一层去遍历。

所以遍历k 的for循环一定是在最外面，这样才能一层一层去遍历。如图：

img

至于遍历 i 和 j 的话，for 循环的先后顺序无所谓。

代码如下：

1
2
3
4
5
6
7
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
        }
    }
}

有录友可能想，难道 遍历k 放在最里层就不行吗？

k 放在最里层，代码是这样：

1
2
3
4
5
6
7
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= n; k++) {
            grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
        }
    }
}

此时就遍历了 j 与 k 形成一个平面，i 则是纵面，那遍历 就是这样的：

img

而我们初始化的数据 是 k 为0， i 和 j 形成的平面做初始化，如果以 k 和 j 形成的平面去一层一层遍历，就造成了 递推公式 用不上上一轮计算的结果，从而导致结果不对（初始化的部分是 i 与j 形成的平面，在初始部分有讲过）。

我再给大家举一个测试用例

1
2
3
4
5
6
7
5 4
1 2 10
1 3 1
3 4 1
4 2 1
1
1 2

就是图：

img

求节点1 到 节点 2 的最短距离，运行结果是 10 ，但正确的结果很明显是3。

为什么呢？

因为 k 放在最里面，先就把 节点1 和 节点 2 的最短距离就确定了，后面再也不会计算节点 1 和 节点 2的距离，同时也不会基于 初始化或者之前计算过的结果来计算，即：不会考虑 节点1 到 节点3， 节点3 到节点 4，节点4到节点2 的距离。

造成这一原因，是 在三维立体坐标中， 我们初始化的是 i 和 i 在k 为0 所构成的平面，但遍历的时候 是以 j 和 k构成的平面以 i 为垂直方向去层次遍历。

而遍历k 的for循环如果放在中间呢，同样是 j 与k 行程一个平面，i 是纵面，遍历的也是这样：

img

同样不能完全用上初始化 和 上一层计算的结果。

根据这个情况再举一个例子：

1
2
3
4
5
5 2
1 2 1
2 3 10
1
1 3

图：

img

求 节点1 到节点3 的最短距离，如果k循环放中间，程序的运行结果是 -1，也就是不能到达节点3。

在计算 grid[i] [j] [k]的时候，需要基于 grid[i] [k] [k-1]和 grid[k] [j] [k-1]的数值。

也就是 计算 grid[1] [3] [2] （表示节点1 到 节点3，经过节点2） 的时候，需要基于 grid[1] [2] [1] 和 grid[2] [3] [1]的数值，而 我们初始化，只初始化了 k为0 的那一层。

造成这一原因 依然是 在三维立体坐标中， 我们初始化的是 i 和 j 在k 为0 所构成的平面，但遍历的时候 是以 j 和 k构成的平面以 i 为垂直方向去层次遍历。

很多录友对于 floyd算法的遍历顺序搞不懂，其实 是没有从三维的角度去思考，同时我把三维立体图给大家画出来，遍历顺序标出来，大家就很容易想明白，为什么 k 放在最外层 才能用上 初始化和上一轮计算的结果了。

5、举例推导dp数组

这里涉及到 三维矩阵，可以一层一层打印出来去分析，例如k=0 的这一层，k = 1的这一层，但一起把三维带数据的图画出来其实不太好画。

代码如下

以上分析完毕，最后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
#include <list>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));  // 因为边的最大距离是10^4
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2][0] = val;
        grid[p2][p1][0] = val; // 注意这里是双向图

    }
    // 开始 floyd
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
            }
        }
    }
    // 输出结果
    int z, start, end;
    cin >> z;
    while (z--) {
        cin >> start >> end;
        if (grid[start][end][n] == 10005) cout << -1 << endl;
        else cout << grid[start][end][n] << endl;
    }
}

空间优化

这里 我们可以做一下 空间上的优化，从滚动数组的角度来看，我们定义一个 grid[n + 1] [ n + 1] [2] 这么大的数组就可以，因为k 只是依赖于 k-1的状态，并不需要记录k-2，k-3，k-4 等等这些状态。

那么我们只需要记录 grid[i] [j] [1]和 grid[i] [j] [0]就好，之后就是 grid[i] [j] [1] 和 grid[i] [j] [0] 交替滚动。

在进一步想，如果本层计算（本层计算即k相同，从三维角度来讲） gird[i] [j] 用到了 本层中刚计算好的 grid[i] [k]会有什么问题吗？

如果 本层刚计算好的 grid[i] [k]比上一层 （即k-1层）计算的 grid[i] [k]小，说明确实有 i 到 k 的更短路径，那么基于 更小的 grid[i] [k]去计算 gird[i] [j] 没有问题。

如果 本层刚计算好的grid[i] [k] 比上一层 （即k-1层）计算的 grid[i] [k] 大， 这不可能，因为这样也不会做更新 grid[i] [k]的操作。

所以本层计算中，使用了本层计算过的 grid[i] [k] 和 grid[k] [j] 是没问题的。

那么就没必要区分，grid[i] [k] 和 grid[k] [j] 是 属于 k - 1 层的呢，还是 k 层的。

所以递归公式可以为：

1
grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);

基于二维数组的本题代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10005));  // 因为边的最大距离是10^4

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
        grid[p2][p1] = val; // 注意这里是双向图

    }
    // 开始 floyd
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
            }
        }
    }
    // 输出结果
    int z, start, end;
    cin >> z;
    while (z--) {
        cin >> start >> end;
        if (grid[start][end] == 10005) cout << -1 << endl;
        else cout << grid[start][end] << endl;
    }
}
  • 时间复杂度： $O(n^3)$
  • 空间复杂度：$O(n^2)$

总结

本期如果上来只用二维数组来讲的话，其实更容易，但遍历顺序那里用二维数组其实是讲不清楚的，所以我直接用三维数组来讲，目的是将遍历顺序这里讲清楚。

理解了遍历顺序才是floyd算法最精髓的地方。

floyd算法的时间复杂度相对较高，适合 稠密图且源点较多的情况。

如果是稀疏图，floyd是从节点的角度去计算了，例如 图中节点数量是 1000，就一条边，那 floyd的时间复杂度依然是 $O(n^3)$ 。

如果 源点少，其实可以 多次dijsktra 求源点到终点。

A * 算法精讲 （A star算法）

127.骑士的攻击

题目描述

在象棋中，马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，计算从起点到达目标点所需的最短步数。

棋盘大小 1000 x 1000（棋盘的 x 和 y 坐标均在 [1, 1000] 区间内，包含边界）

输入描述

第一行包含一个整数 n，表示测试用例的数量，1 <= n <= 100。

接下来的 n 行，每行包含四个整数 a1, a2, b1, b2，分别表示骑士的起始位置 (a1, a2) 和目标位置 (b1, b2)。

输出描述

输出共 n 行，每行输出一个整数，表示骑士从起点到目标点的最短路径长度。

输入示例
1
2
3
4
5
6
7
6
5 2 5 4
1 1 2 2
1 1 8 8
1 1 8 7
2 1 3 3
4 6 4 6
输出示例
1
2
3
4
5
6
2
4
6
5
1
0
提示信息

骑士移动规则如图，红色是起始位置，黄色是骑士可以走的地方。

img

思路

我们看到这道题目的第一个想法就是广搜，这也是最经典的广搜类型题目。

这里我直接给出广搜的C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int moves[1001][1001];
int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
void bfs(int a1,int a2, int b1, int b2)
{
	queue<int> q;
	q.push(a1);
	q.push(a2);
	while(!q.empty())
	{
		int m=q.front(); q.pop();
		int n=q.front(); q.pop();
		if(m == b1 && n == b2)
		break;
		for(int i=0;i<8;i++)
		{
			int mm=m + dir[i][0];
			int nn=n + dir[i][1];
			if(mm < 1 || mm > 1000 || nn < 1 || nn > 1000)
			continue;
			if(!moves[mm][nn])
			{
				moves[mm][nn]=moves[m][n]+1;
				q.push(mm);
				q.push(nn);
			}
		}
	}
}

int main()
{
    int n, a1, a2, b1, b2;
    cin >> n;
    while (n--) {
        cin >> a1 >> a2 >> b1 >> b2;
        memset(moves,0,sizeof(moves));
		bfs(a1, a2, b1, b2);
		cout << moves[b1][b2] << endl;
	}
	return 0;
}

提交后，大家会发现，超时了。

image-20241015155658040

因为本题地图足够大，且 n 也有可能很大，导致有非常多的查询。

我们来看一下广搜的搜索过程，如图，红色是起点，绿色是终点，黄色是要遍历的点，最后从 起点 找到 达到终点的最短路径是棕色。

img

可以看出 广搜中，做了很多无用的遍历， 黄色的格子是广搜遍历到的点。

这里我们能不能让遍历方向，向这终点的方向去遍历呢？

这样我们就可以避免很多无用遍历。

Astar

Astar 是一种 广搜的改良版。 有的是 Astar是 dijkstra 的改良版。

其实只是场景不同而已 我们在搜索最短路的时候， 如果是无权图（边的权值都是1） 那就用广搜，代码简洁，时间效率和 dijkstra 差不多 （具体要取决于图的稠密）

如果是有权图（边有不同的权值），优先考虑 dijkstra。

而 Astar 关键在于 启发式函数， 也就是影响 广搜或者 dijkstra 从 容器（队列）里取元素的优先顺序。

以下，我用BFS版本的A * 来进行讲解。

在BFS中，我们想搜索，从起点到终点的最短路径，要一层一层去遍历。

img

如果 使用A * 的话，其搜索过程是这样的，如图，图中着色的都是我们要遍历的点。

img

（上面两图中 最短路长度都是8，只是走的方式不同而已）

大家可以发现 BFS 是没有目的性的 一圈一圈去搜索， 而 A * 是有方向性的去搜索。

看出 A * 可以节省很多没有必要的遍历步骤。

为了让大家可以明显看到区别，我将 BFS 和 A * 制作成可视化动图，大家可以自己看看动图，效果更好。

地址：https://kamacoder.com/tools/knight.html

那么 A * 为什么可以有方向性的去搜索，它的如何知道方向呢？

其关键在于 启发式函数。

那么启发式函数落实到代码处，如果指引搜索的方向？

在本篇开篇中给出了BFS代码，指引 搜索的方向的关键代码在这里：

1
2
int m=q.front();q.pop();
int n=q.front();q.pop();

从队列里取出什么元素，接下来就是从哪里开始搜索。

所以 启发式函数 要影响的就是队列里元素的排序！

这是影响BFS搜索方向的关键。

对队列里节点进行排序，就需要给每一个节点权值，如何计算权值呢？

每个节点的权值为F，给出公式为：$F = G + H$

G：起点达到目前遍历节点的距离

F：目前遍历的节点到达终点的距离

起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离 就是起点到达终点的距离。

本题的图是无权网格状，在计算两点距离通常有如下三种计算方式：

  1. 曼哈顿距离，计算方式： $d = |x_1-x_2\ |+|y_1-y_2\ |$
  2. 欧氏距离（欧拉距离） ，计算方式：$d = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2 )} $
  3. 切比雪夫距离，计算方式：$d = \max{(|x_1 - x_2\ |, |y_1 - y_2\ |)}$

x1, x2 为起点坐标，y1, y2 为终点坐标 。

选择哪一种距离计算方式 也会导致 A * 算法的结果不同。

本题，采用欧拉距离才能最大程度体现 点与点之间的距离。

所以 使用欧拉距离计算 和 广搜搜出来的最短路的节点数是一样的。 （路径可能不同，但路径上的节点数是相同的）

我在制作动画演示的过程中，分别给出了曼哈顿、欧拉以及契比雪夫 三种计算方式下，A * 算法的寻路过程，大家可以自己看看看其区别。

动画地址：https://kamacoder.com/tools/knight.html

image-20241015160827303

image-20241015155952042

image-20241015161005848

计算出来 F 之后，按照 F 的 大小，来选去出队列的节点。

可以使用 优先级队列 帮我们排好序，每次出队列，就是F最小的节点。

实现代码如下：

（启发式函数 采用 欧拉距离计算方式）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int moves[1001][1001];
int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
int b1, b2;
// F = G + H
// G = 从起点到该节点路径消耗
// H = 该节点到终点的预估消耗

struct Knight{
    int x,y;
    int g,h,f;
    bool operator < (const Knight & k) const{  // 重载运算符， 从小到大排序
     return k.f < f;
    }
};

priority_queue<Knight> que;

int Heuristic(const Knight& k) { // 欧拉距离
    return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); // 统一不开根号，这样可以提高精度
}
void astar(const Knight& k)
{
    Knight cur, next;
	que.push(k);
	while(!que.empty())
	{
		cur=que.top(); que.pop();
		if(cur.x == b1 && cur.y == b2)
		break;
		for(int i = 0; i < 8; i++)
		{
			next.x = cur.x + dir[i][0];
			next.y = cur.y + dir[i][1];
			if(next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000)
			continue;
			if(!moves[next.x][next.y])
			{
				moves[next.x][next.y] = moves[cur.x][cur.y] + 1;

                // 开始计算F
				next.g = cur.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5
                next.h = Heuristic(next);
                next.f = next.g + next.h;
                que.push(next);
			}
		}
	}
}

int main()
{
    int n, a1, a2;
    cin >> n;
    while (n--) {
        cin >> a1 >> a2 >> b1 >> b2;
        memset(moves,0,sizeof(moves));
        Knight start;
        start.x = a1;
        start.y = a2;
        start.g = 0;
        start.h = Heuristic(start);
        start.f = start.g + start.h;
		astar(start);
        while(!que.empty()) que.pop(); // 队列清空
		cout << moves[b1][b2] << endl;
	}
	return 0;
}

复杂度分析

A * 算法的时间复杂度 其实是不好去量化的，因为他取决于 启发式函数怎么写。

  • 最坏情况下，A 退化成广搜，算法的时间复杂度 是 $O(n 2)$，n 为节点数量。

  • 最佳情况，是从起点直接到终点，时间复杂度为$ O(d*log{d})$，d 为起点到终点的深度。

因为在搜索的过程中也需要堆排序，所以是$ O(d*log{d})$。

实际上 A 的时间复杂度是介于 最优 和最坏 情况之间， 可以 非常粗略的认为 A 算法的时间复杂度是 $O(n*log{n}) $，n 为节点数量。

A * 算法的空间复杂度 $O(b ^ d)$ ,d 为起点到终点的深度，b 是 图中节点间的连接数量，本题因为是无权网格图，所以 节点间连接数量为 4。

拓展

如果本题大家使用曼哈顿距离 或者 切比雪夫距离 计算的话，可以提交试一试，有的最短路结果是并不是最短的。

原因也是 曼哈顿和 切比雪夫这两种计算方式在 本题的网格地图中，都没有体现出点到点的真正距离！

可能有些录友找到类似的题目，例如 poj 2243 (opens new window)，使用 曼哈顿距离 提交也过了， 那是因为题目中的地图太小了，仅仅是一张 8 * 8的地图，根本看不出来 不同启发式函数写法的区别。

A 算法 并不是一个明确的最短路算法，**A \ 算法搜的路径如何，完全取决于 启发式函数怎么写**。

A * 算法并不能保证一定是最短路，因为在设计 启发式函数的时候，要考虑 时间效率与准确度之间的一个权衡。

虽然本题中，A * 算法得到是最短路，也是因为本题 启发式函数 和 地图结构都是最简单的。

例如在游戏中，在地图很大、不同路径权值不同、有障碍 且多个游戏单位在地图中寻路的情况，如果要计算准确最短路，耗时很大，会给玩家一种卡顿的感觉。

而真实玩家在玩游戏的时候，并不要求一定是最短路，次短路也是可以的 （玩家不一定能感受出来，及时感受出来也不是很在意），只要奔着目标走过去 大体就可以接受。

所以 在游戏开发设计中，保证运行效率的情况下，A * 算法中的启发式函数 设计往往不是最短路，而是接近最短路的 次短路设计。

大家如果玩 LOL，或者 王者荣耀 可以回忆一下：如果 从很远的地方点击 让英雄直接跑过去 是 跑的路径是不靠谱的，所以玩家们才会在 距离英雄尽可能近的位置去点击 让英雄跑过去。

A * 的缺点

大家看上述 A 代码的时候，可以看到 我们想 队列里添加了很多节点，但真正从队列里取出来的 *仅仅是 靠启发式函数判断 距离终点最近的节点。

相对了 普通BFS，A * 算法只从 队列里取出 距离终点最近的节点。

那么问题来了，A 在一次路径搜索中，*大量不需要访问的节点都在队列里，会造成空间的过度消耗。

IDA * 算法 对这一空间增长问题进行了优化，关于 IDA *算法，本篇不再做讲解，感兴趣的录友可以自行找资料学习。

另外还有一种场景 是 A * 解决不了的。

如果题目中，给出 多个可能的目标，然后在这多个目标中 选择最近的目标，这种 A 就不擅长了， A 只擅长给出明确的目标 然后找到最短路径。

如果是多个目标找最近目标（特别是潜在目标数量很多的时候），可以考虑 Dijkstra ，BFS或者 Floyd。

最短路算法总结篇

至此已经讲解了四大最短路算法，分别是Dijkstra、Bellman_ford、SPFA 和 Floyd。

针对这四大最短路算法，我用了七篇长文才彻底讲清楚，分别是：

  • dijkstra朴素版
  • dijkstra堆优化版
  • Bellman_ford
  • Bellman_ford 队列优化算法（又名SPFA）
  • bellman_ford 算法判断负权回路
  • bellman_ford之单源有限最短路
  • Floyd 算法精讲
  • 启发式搜索：A * 算法

最短路算法比较复杂，而且各自有各自的应用场景，我来用一张表把讲过的最短路算法的使用场景都展现出来：

img

（因为A * 属于启发式搜索，和上面最短路算法并不是一类，不适合一起对比，所以没有放在一起）

可能有同学感觉：这个表太复杂了，我记也记不住。

其实记不住的原因还是对 这几个最短路算法没有深刻的理解。

这里我给大家一个大体使用场景的分析：

  1. 如果遇到单源且边为正数，直接Dijkstra。

至于 使用朴素版还是 堆优化版 还是取决于图的稠密度， 多少节点多少边算是稠密图，多少算是稀疏图，这个没有量化，如果想量化只能写出两个版本然后做实验去测试，不同的判题机得出的结果还不太一样。一般情况下，可以直接用堆优化版本。

  1. 如果遇到单源边可为负数，直接 Bellman-Ford，同样SPFA 还是 Bellman-Ford 取决于图的稠密度。一般情况下，直接用 SPFA。

  2. 如果有负权回路，优先 Bellman-Ford， 如果是有限节点最短路 也优先 Bellman-Ford，理由是写代码比较方便。

  3. 如果是遇到多源点求最短路，直接 Floyd。除非 源点特别少，且边都是正数，那可以 多次 Dijkstra 求出最短路径，但这种情况很少，一般出现多个源点了，就是想让你用 Floyd 了。

  4. 对于A ，由于其高效性，所以在实际工程应用中使用最为广泛 ，由于其 结果的不唯一性，也就是可能是次短路的特性，一般不适合作为算法题。游戏开发、地图导航、数据包路由等都广泛使用 A 算法。

图论总结篇

从深搜广搜 到并查集，从最小生成树到拓扑排序， 最后是最短路算法系列。

至此算上本篇，一共30篇文章，图论之旅就在此收官了。

在0098.所有可达路径 ，我们接触了两种图的存储方式，邻接表和邻接矩阵，掌握两种图的存储方式很重要。

图的存储方式也是大家习惯在核心代码模式下刷题 经常忽略的 知识点。因为在力扣上刷题不需要掌握图的存储方式。

深搜与广搜

在二叉树章节中，其实我们讲过了 深搜和广搜在二叉树上的搜索过程。

在图论章节中，深搜与广搜就是在图这个数据结构上的搜索过程。

深搜与广搜是图论里基本的搜索方法，大家需要掌握三点：

  • 搜索方式：深搜是可一个方向搜，不到黄河不回头。 广搜是围绕这起点一圈一圈的去搜。
  • 代码模板：需要熟练掌握深搜和广搜的基本写法。
  • 应用场景：图论题目基本上可以即用深搜也可用广搜，无疑是用哪个方便而已

注意事项

需要注意的是，同样是深搜模板题，会有两种写法。

在0099.岛屿的数量深搜.md 和 0105.有向图的完全可达性，涉及到dfs的两种写法。

我们对dfs函数的定义是 是处理当前节点 还是处理下一个节点 很重要，决定了两种dfs的写法。

这也是为什么很多录友看到不同的dfs写法，结果发现提交都能过的原因。

而深搜还有细节，有的深搜题目需要用到回溯的过程，有的就不用回溯的过程，

一般是需要计算路径的问题 需要回溯，如果只是染色问题（岛屿问题系列） 就不需要回溯。

例如： 0105.有向图的完全可达性 深搜就不需要回溯，而 0098.所有可达路径 中的递归就需要回溯，文章中都有详细讲解

注意：以上说的是不需要回溯，不是没有回溯，只要有递归就会有回溯，只是我们是否需要用到回溯这个过程，这是需要考虑的。

很多录友写出来的广搜可能超时了， 例如题目：0099.岛屿的数量广搜

根本原因是只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。

具体原因，我在0099.岛屿的数量广搜 中详细讲了。

在深搜与广搜的讲解中，为了防止惯性思维，我特别加入了题目 0106.岛屿的周长，提醒大家，看到类似的题目，也不要上来就想着深搜和广搜。

还有一些图的问题，在题目描述中，是没有图的，需要我们自己构建一个图，例如 0110.字符串接龙，题目中连线都没有，需要我们自己去思考 什么样的两个字符串可以连成线。

并查集

并查集相对来说是比较复杂的数据结构，其实他的代码不长，但想彻底学透并查集，需要从多个维度入手，

我在理论基础篇的时候 讲解如下重点：

  • 为什么要用并查集，怎么不用个二维数据，或者set、map之类的。
  • 并查集能解决那些问题，哪些场景会用到并查集
  • 并查集原理以及代码实现
  • 并查集写法的常见误区
  • 带大家去模拟一遍并查集的过程
  • 路径压缩的过程
  • 时间复杂度分析

上面这几个维度 大家都去思考了，并查集基本就学明白了。

其实理论基础篇就算是给大家出了一道裸的并查集题目了，所以在后面的题目安排中，会稍稍的拔高一些，重点在于并查集的应用上。

例如 并查集可以判断这个图是否是树，因为树的话，只有一个根，符合并查集判断集合的逻辑，题目：0108.冗余连接。

在0109.冗余连接II 中 对有向树的判断难度更大一些，需要考虑的情况比较多。

最小生成树

最小生成树是所有节点的最小连通子图， 即：以最小的成本（边的权值）将图中所有节点链接到一起。

最小生成树算法，有prim和 kruskal。

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。

在 稀疏图中，用Kruskal更优。 在稠密图中，用prim算法更优。

边数量较少为稀疏图，接近或等于完全图（所有节点皆相连）为稠密图

Prim 算法 时间复杂度为$ O(n^2)$，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。

Kruskal算法 时间复杂度 为 $O(nlogn)$，其中n 为边的数量，适用稀疏图。

关于 prim算法，我自创了三部曲，来帮助大家理解：

  1. 第一步，选距离生成树最近节点
  2. 第二步，最近节点加入生成树
  3. 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

大家只要理解这三部曲， prim算法 至少是可以写出一个框架出来，然后在慢慢补充细节，这样不至于 自己在写prim的时候 两眼一抹黑 完全凭感觉去写。

minDist数组 是prim算法的灵魂，它帮助 prim算法完成最重要的一步，就是如何找到 距离最小生成树最近的点。

kruscal的主要思路：

  • 边的权值排序，因为要优先选最小的边加入到生成树里
  • 遍历排序后的边
    • 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
    • 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

而判断节点是否在一个集合 以及将两个节点放入同一个集合，正是并查集的擅长所在。

所以Kruskal是需要用到并查集的。

这也是我在代码随想录图论编排上 为什么要先 讲解 并查集 在讲解 最小生成树。

拓扑排序

拓扑排序 是在图上的一种排序。

概括来说，给出一个 有向图，把这个有向图转成线性的排序 就叫拓扑排序。

同样，拓扑排序也可以检测这个有向图 是否有环，即存在循环依赖的情况。

拓扑排序的一些应用场景，例如：大学排课，文件下载依赖 等等。

只要记住如下两步拓扑排序的过程，代码就容易写了：

  1. 找到入度为0 的节点，加入结果集
  2. 将该节点从图中移除

最短路算法

最短路算法是图论中，比较复杂的算法，而且不同的最短路算法都有不同的应用场景。

我在 最短路算法总结篇 里已经做了一个高度的概括。

大家要时常温故而知新，才能透彻理解各个最短路算法。

总结

到最后，图论终于剧终了，相信这是市面上大家能看到最全最细致的图论讲解教程。

图论也是我 《代码随想录》所有章节里 所费精力最大的一个章节。

只为了不负录友们的期待。 大家加油💪🏻

代码随想录
#LEECODE
10.8-10.15并查集-最短路径算法
https://bing.7dragonpig.cn/posts/217faa3e/
作者
七龙猪
发布于
2024年10月8日
许可协议