最短路 最短路 一、图论基础 二、图的存储 2.1 邻接矩阵 2.2 邻接表 使用vector存储邻接表 使用链表存储邻接表（链式前向星） 三、最短路问题概述 四、朴素Dijkstra算法 4.1 Dijkstra算法思想 4.2 Dijkstra算法步骤 4.3 Dijkstra算法程序实现 五、堆优化Dijkstra算法 六、Bellman-Ford算法 问题：为什么Dijkstra算法无法处理含负权边的图？ 负权回路 6.1 Bellman-Ford算法步骤 6.2 算法分析 七、SPFA算法 7.1 Bellman-Ford算法的优化策略 （1）提前退出循环 （2）队列优化 7.2 SPFA算法步骤 7.3 SPFA算法判断负环 八、其他最短路问题 8.1 BFS最短路问题 8.2 双端队列BFS求最短路问题 8.3 分层图 九、Floyd算法 9.1 基于动态规划算法思想 9.2 Floyd算法代码实现 9.3 传递闭包

一、图论基础 图（graph) 通常用 表示， 是点集， 是边集。

一般设 表示点的数量， 表示边的数量。

image-20240411143117230

有向图

边集 中的每个元素为一个无序二元组 ， 称为无向边，简称边。

其中 。设 , 则 和 称为 的端点。

无向图

边集 中的每个元素为一个有序二元组 ，也可以表示为 。称为有向边，或称为弧，在不引起混淆的情况下也可以称作边。

设边 ,则称 为 的起点， 称为 的终点。并称 是 的直接前驱， 是 的直接后继。

带权图

图中每条边被赋予了权值，称为带权图。

自环

对于 中的边 , 若 ,则 被称作一个自环。

重边

若 中存在两个完全相同的元素（边） ，则它们被称为（一组）重边。

二、图的存储 对于一张有向图，一般有邻接矩阵和邻接表两种存储方式。对于无向图，可以把无向图看做两条方向相反的有向边。从而采用与有向图一样的存储方式。

2.1 邻接矩阵 设有向图 ， 是点集， 是边集， 表示一条从 到 的有向边，其边权（或称长度）为 。

设 ， 邻接矩阵 是一个 的矩阵。

image-20240411144606516

空间复杂度： ​

适用情况：

没有重边或重边可以忽略的情况

稠密图：边数 接近 级别

const int N = 100010; int n, a[N][N]; memset(a, 0x3f, sizeof(a)); //初始化为无穷大

//读入一条从x到y长度z的有向边 a[x][y] = min(a[x][y], z); //处理重边 for (int i = 1; i <=n; i ++) a[i][i] = 0; //访问从x出发的所有边 for (int y = 1; y <= n; y ++) { //对边a[x][y]进行处理 } 2.2 邻接表 空间复杂度： ​

适用情况：

大部分情况都可以使用邻接表存储

稀疏图：边数 接近 级别

使用vector存储邻接表 const int N = 100010; struct edge { //存储边 int to; //终点 int w; //边权 } vector g[N]; //定义vector用于存储边

//读入一条从x到y长度为z的有向边 g[x].push_back({y, z});

//访问从x出发的所有边 for (int i = 0, sz = g[x].size(); i < sz; i ++) { int y = g[x][i].to, z = g[x][i].w; //读取到一条从x出发到y边权为z的边

}

image-20240411144640124

使用链表存储邻接表（链式前向星） const int N = 100010; int h[N]; //表头数组，用于存储每种分类链表的头指针 int e[N]; //存储每条边的终点 int w[N]; //存储每条边的权值 int ne[N]; //存储当前节点后继节点的指针（数组下标） int idx; //存储当前节点在数组中的下标

memset(h, -1, sizeof(h)); //初始化头指针数组为-1，表示指针域为空 //在邻接表中插入一条边从x到y长度为z的有向边 void add(int x, int y, int z) { e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx ++; }

//访问从x出发的所有边 for (int i = h[x]; ~i; i = ne[i]) { int y = e[i], z = w[i]; //找到一条有向边(x, y)，权值为z }

三、最短路问题概述 最短路算法主要分成两种：

单源最短路：求一个点到其他点的最短路径

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

最短路算法

四、朴素Dijkstra算法 4.1 Dijkstra算法思想 Dijkstra算法基于贪心思想，它只适用于所有边的的长度都是非负数的图。

Dijkstra算法需要定义以下两个数组：

数组 表示从源点 到节点 的已知的最短路长度

数组 表示节点 是否已经找到最短路

Dijkstra算法将图中节点划分成两部分：

已经确定最短路的节点， 数组标记为

最短路待定的节点， 数组标记为

由于图中所有边长 ​ 都是非负数时，所以全局最小值不可能再被其他节点更新。因此每次只需要在最短路待定的节点中找到 值最小的节点 ，则节点 中的 值一定是最短路长度。然后再用节点 去更新所有与之相连的节点的 ​ 值，这种更新操作称为 松弛操作。

image-20240413092516834

松弛操作：对于一条从 到 长度为 的边， 如果dist[u] + w < dist[v]， 那么就可以将 dist[v] 的值更新为 dist[u] + w。因为这代表从 走到 再经过 这条边走到 是一条未被发现过的路径，且比原先的最优路径还要短，这个操作被称为松弛操作。

4.2 Dijkstra算法步骤 初始化 dist[1] = 0，其余节点的 值为无穷大。

找出一个未被标记的、dist[x] 最小的节点 ，然后标记节点 。

扫描节点 的所有出边 ​，若 dist[y] > dist[x] + z， 则使用 dist[x] + z 更新 dist[y]。

重复上述 两个步骤，直到所有节点都被标记。

4.3 Dijkstra算法程序实现 const int N = 510; int g[N][N]; //使用邻接矩阵存储图 int dist[N], vis[N];

void dijkstra() { memset(dist, 0x3f, sizeof(d)); //dist数组初始化为 dist[1] = 0; //起点最短路为0 for (int i = 1; i < n; i ++) { //执行一次循环确定一个节点的最短路，共需执行n - 1次循环 int x = 0; for (int j = 1; j <= n; j ++) //找到未标记的节点中dist值最小的 if (!vis[j] && (x == 0 || dist[j] < dist[x])) x = j; for (int y = 1; y <= n; y ++) //用节点x更新所有出边 dist[y] = min(dist[y], dist[x] + g[x][y]); //松弛操作 vis[x] = 1; //标记x节点已找到最短路 } }

五、堆优化Dijkstra算法 Dijkstra算法 的主要瓶颈在于寻找全局最小值的过程。可以使用二叉堆（优先队列进行）对 数组进行维护。将循环最小值的时间复杂度从 降低到 。

堆优化Dijkstra算法时间复杂度为 ，因此堆优化Dijkstra算法适合对稀疏图求最短路，如果图为稠密图，即 是 级别的，那效率还不如朴素Dijkstra算法

const int N = 150010; typedef pair<int, int> PII; int h[N], e[N], w[N], ne[N], idx; //邻接表 priority_queue q; //优先队列大根堆 int dist[N], vis[N];

void dijkstra() { memset(dist, 0x3f, sizeof(dist)); dist[1] = 0; //起点最短路为0 q.push({0, 1}); //将起点放入堆，{距离, 节点} while (q.size()) { int x = q.top().second; q.pop(); //取出最小值 if (vis[x]) continue; //如果该节点已被标记则跳过 vis[x] = 1; //标记该节点 for (int i = h[x]; ~i; i = ne[i]) {//遍历节点x的所有出边 int y = e[i], z = w[i]; if (dist[x] + z < dist[y]) {//松弛操作 dist[y] = dist[x] + z; q.push({-dist[y], y}); //存入负数转化为小根堆，注：同一个节点可能会被重复放入堆 } } } }

六、Bellman-Ford算法 问题：为什么Dijkstra算法无法处理含负权边的图？ image-20240413092438002

按照Dijkstra算法的步骤

dist[1] = 0, 其他节点dist值为无穷大，标记节点1，用节点1更新出边，得到dist[2] = 2, dist[3] = 5

找到未标记的dist值最小的节点2，用节点2更新出边，得到dist[4] = 4，标记节点2

找到未标记的dist值最小的节点4，用节点4更新出边，得到dist[5] = 5， 标记节点4

找到未标记的dist值最小的节点3，用节点3更新出边（已经没有未被标记出边）,标记节点3

找到未标记的dist值最小的节点5，用节点5更新出边（已经没有未被标记出边），标记节点5

至此，得到节点5的最短路为5。但实际上有一条更短的路径1 → 3 → 4 → 5，路径长度为4。

原因是在第3步找到未标记的dist值最小的节点4时，该节点的dist值未必是最小值，还有可能被另外非最小值节点加上负权边更新。解决方案是每遍都是对所有边进行松弛操作。就不会丢失更短的路径。这就是Bellman-Ford算法的基本思想。

给定一张有向图，若对于图中的某一条边 ，有 成立，则称该边满足三角形不等式。若所有边都满足三角形不等式，则 ​ 数组就是所求最短路。

Bellman-Ford算法每次对所有边进行松弛操作，经过 遍对所有边进行松弛操作 后数组 中存储的是经过 ​ 条边的最短路。

对于 个节点的图来说，从点 到 点 的最短路径上共有 条边。因此总共需要对所有边做 遍松弛操作就能求出所有节点的最短路。在完成 ​​ 次松弛操作后，如果还可以松弛，那就意味着，图中存在着负环。

负权回路 在一个图中每条边都有一个权值（正或负）。如果存在一个环（从某个点出发又回到自己的路径），而且这个环上所有权值之和是负数 ，那这个环称为负环，也叫负权回路。

存在负权回路的图是不能求两点间的最短路的，因为只要在负权回路上不断兜圈子，所得的最短路长度可以任意小。

image-20240413150926347

6.1 Bellman-Ford算法步骤 初始化 dist[s] = 0，其余节点的 值为无穷大。

扫描所有边 , 若 ，则用 更新 。

重复第 2 步操作 遍，即完成最短路的求解。如果再进行一次遍历，还能进行松弛操作，就说明图中存在负环。

const int N = 510, M = 10010; int dist[N]; struct edge{ int x, y, z; }e[M];

void bellman_ford() { memset(dist, 0x3f, sizeof(dist)); dist[1] = 0; for (int i = 1; i < n; i ++) {//执行n - 1遍对所有边进行松弛操作 for (int j = 0; j < m; j ++) {//遍历所有边 int x = e[j].x, y = e[j].y, z = e[j].z; dist[y] = min(dist[y], dist[x] + z); //松弛操作 } } } 6.2 算法分析 （1）时间复杂度：算法对每条边进行松弛操作，重复 次，时间复杂度为

（2）空间复杂度： ​

七、SPFA算法 7.1 Bellman-Ford算法的优化策略 （1）提前退出循环 Bellman-Ford算法如果某次对所有边进行松弛操作都没有发生 值更新，就说明已经完成了最短路的求解，可以提前退出循环

（2）队列优化 松弛操作必定会发生在最短路径松弛过的前驱节点上，用一个队列记录松弛过的节点，可以避免冗余计算。

这就是队列优化的Bellman-Ford算法， 又称为SPFA算法。

7.2 SPFA算法步骤 建立一个队列，最初队列中只含有起点 。

取出队头节点 , 扫描它的所有出边 , 若 ， 则使用 更新 。同时，若 不在队列中，则把 入队。

重复上述步骤，直至队列为空。

const int N = 10010; int dist[N]; int vis[N]; //vis[x]表示x是否在队列中

void spfa() { memset(dist, 0x3f, sizeof(dist)); //初始化dist数组 dist[1] = 0; vis[1] = 1; //初始化起点 q.push(1); //起点入队 while (q.size()) { int x = q.front(); q.pop(); vis[x] = 0; //标记节点x不在队列中 for (int i = h[x]; ~i; i = ne[i]) { //遍历x的所有出边 int y = e[x], z = w[x]; if (dist[x] + z < dist[y]) { //松弛操作 dist[y] = dist[x] + z; if (!vis[y]) q.push(y), vis[y] = 1; //如果节点y不在队列中，则入队并标记y在队列中 } } } } 7.3 SPFA算法判断负环 给定一个 个点 条边的有向图，图中可能存在重边和自环，边权可能为负数。请你判断图中是否存在负权回路。

基本思想

对于有 个节点的图，其从节点 到节点 的最短路径上共有 条边。也即图中最短路径长度不超过

在使用 SPFA 算法求最短路过程中，可以统计出每个节点 到起点的最短路径中的边数 ，如果统计过程中发现有一个节点的最短路径中边长超过 条，则可以断定图中存在负环

统计每个节点到起点的最短路径中边数的方法：

当存在一条边 到 边权为 时，如果 成立，那么，我们使用 去更新 含义是从起点走到节点 再经过边 这条边目前是节点 目前找到的最短路径，明显有 。

八、其他最短路问题 8.1 BFS最短路问题 使用BFS（广度优先搜索）可以实现图中所有边权值都为1的最短路问题，常用于“走地图”类问题。如：给定一个矩形地图，控制一个物体在地图中桉要求移动，求最少步数问题。

基本原理：广度优先搜索是逐层遍历搜索树的算法，所有状态按照入队的先后顺序具有层次单调性（也即步数单调性）。BFS具有以下两个性质

在访问完所有的第 层节点后，才会开始访问第 层节点。

任意时刻，队列中至多有两个层次的节点。若其中一部分节点属于第 层，则另一部分节点属于第 层，并且所有第 层节点排在第 层节点之前。也就是说，广度优先遍历队列中的元素关于层次满足“两端性”和“单调性”。

两段性：在队列中当前层的状态都在前面，下一层的状态都在后面。因此，每种状态只会入队一次，无需判重。

单调性：在队列中状态的是单调递增的（如步数单调性）。因此，每次从队列中取出的状态都是未被标记的全局最小值，也即最短路。

因此，BFS求最短路本质上是一种特殊的Dijkstra算法的体现。

8.2 双端队列BFS求最短路问题 双端队列BFS用于求解图中权值为 或 的最短路问题。每个节点沿分支扩展时，根据分支边权情况分两种情况处理：

分支边权为 ： 将新节点从队头入队

分支边权为 ：将新节点队尾入队

任意时刻广搜队列中节点对应的距离值具有两段性和单调性。但每个节点可能被更新（入队）多次，但是它第一次被扩展（出对）时，就能得到最短路。

例题：题目详情 - 电路维修 - HZOJ

8.3 分层图 例题：[P4568 JLOI2011] 飞行路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[JLOI2011] 飞行路线 题目描述 Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 个城市设有业务，设这些城市分别标记为 到 ，一共有 种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？

输入格式 第一行三个整数 ，分别表示城市数，航线数和免费乘坐次数。

接下来一行两个整数 ，分别表示他们出行的起点城市编号和终点城市编号。

接下来 行，每行三个整数 ，表示存在一种航线，能从城市 到达城市 ，或从城市 到达城市 ，价格为 。

输出格式 输出一行一个整数，为最少花费。

样例 #1 样例输入 #1 5 6 1 0 4 0 1 5 1 2 5 2 3 5 3 4 5 2 3 3 0 2 100 样例输出 #1 8 提示 数据规模与约定 对于 的数据， ， ， 。

对于 的数据， ， ， 。

对于 的数据， ， ， ， ， ， 。

另外存在一组 hack 数据。

算法分析

由于购买机票需要花费金钱，所以肯定不会重复乘坐多次同样的航班或者多次访问一个城市。

如果 ,则本题就是最基础的最短路问题。

题中设置最多 条线路免费，可以使用分层图的方式。具体放入如下：

（1）将原始图多复制 次，原编号为i的节点复制为编号为 的节点；

（2）对于原图存在的 到 的边，其他k层复制的图中也需要连上对应的边，看起来就是相同的图上下堆叠起来，所以被称为分层图；

（3）从第 层（原始层）到第 层，上一层到下一层之间创建单向的 到 的边权为 的边，所以从上一层u城市沿着这条边到下一层 城市免费；

由于题意最多 次免费航班，所以最后的答案取应该是第 层到第 层的目标节点 中最小值。第 层的目标节点 表示使用免费航班次数 ；第 层的目标节点t表示使用免费航班次数 ，因为从第 层走到第 层需要经历一次免费航班，后面几层依次类推。

image-20240419103903385

int main(){ scanf("%d%d%d", &n, &m, &k); scanf("%d%d", &s, &t); while (m --) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add(u, v, w); //在原始层创建边，由于航向可以从u -> v也可以从v -> u，所以是无向图，创建双向边 add(v, u, w); //创建k个分层图，k个图层内部的边与原始图层一致 //两个图层之间创建边权为0的边，即表示免费的航班 //由于只能从上一图层向下一图层航行，所是单向边 for (int i = 1; i <= k; i ++) { add(u + i * n, v + i * n, w); //在第i个分层中复制边 add(v + i * n, u + i * n, w); //创建从第i - 1图层到第i图层之间的边权为0的边 //即如果本次航班从u -> v选择的是从第i - 1层的u飞到第i层的v，则这趟航班是免费的 //由于共有k层分层，所以最多有k条免费航班 add(u + (i - 1) * n, v + i * n, 0); add(v + (i - 1) * n, u + i * n, 0); } } dijkstra(); int ans = inf; //由于题意最多有k个航班，所以最后的结果应该在原始图层和k个分层中的目标节点t中找最小值 for (int i = 0; i <= k; i ++) if (dist[t + i * n] < ans) ans = dist[t + i * n]; printf("%d\n", ans); return 0; } 为了节省空间，分层图有第二种做法：

将 数组 和 数组 多开一维记录 次免费机会的信息

dist[i][j] 表示到达 用了 次免费机会的最小花费

vis[i][j] 表示到达 用了 次 免费机会是否出现过

更新的时候先更新同层之间（即花费免费机会相同）的最短路，然后更新从该层到下一层（即再花费一次免费机会）的最短路

不使用免费机会：dist[y][c] = min(dist[y][c], dist[x][c] + z)

使用免费机会：dist[y][c + 1] = min(dist[y][c + 1], dist[x][c])

九、Floyd算法 Floyd算法用于求图中任意两个节点间的最短路。其核心思想是在节点 与节点 之间插入节点 ,看看是否可以缩短节点 与节点 的距离（松弛操作）。

9.1 基于动态规划算法思想 设 dist[k][i][j] 表示以编号 到 的节点作为中转，节点 到节点 的最短路的长度。

则当 k = 0 时，即 dist[0][i][j]表示不经过任何节点中转时各节点的最短路径长度，即 <i, j> 的边权。

考虑如何进行状态更新

显然从 到 且只以 到 节点作为中转的路径分为以下两类：

从 到 , 不经过 , 即只经过编号为 到 的路径。最短路长度可以表示为：dist[k - 1][i][j]

从 到 , 经过 且只经过编号为 到 的路径，可以分为从 到 , 再从 到 两段。最短路长度可以表示为：

dist[k - 1][i][k] + dist[k - 1][k][j]

因此，从 到 且只以 到 节点作为中转的最短路是上面两种情况取最小值。

状态转移方程为：dist[k][i][j] = min(dist[k - 1][i][j], dist[k - 1][i][k] + dist[k - 1][k][j])

9.2 Floyd算法代码实现 void floyd() { for (int k = 1; k <= n; k ++) //由于状态转移方程中k是从k - 1转移而来，所以最外层循环是k for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) dist[k][i][j] = min(dist[k - 1][i][j], dist[k - 1][i][k] + dist[k - 1][k][j]);
} 时间复杂度：

空间复杂度：

（1）图例分析

image-20240423231357763

dist[0][i][j] 即图的邻接表表示

dist[1][i][j] 表示将 号节点加入中转节点，则从节点 到 找到一条新的路径 3 → 1 → 2 路径长度为 比原来的 更短，则更新之。

（2）空间优化

从状态转移方程：dist[k][i][j] = min(dist[k - 1][i][j], dist[k - 1][i][k] + dist[k - 1][k][j]) ，可知：

第三维中 只与 有关，我们可以使用滚动数组进行优化。将 这个维度去掉。

void floyd() { for (int k = 1; k <= n; k ++) for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
} （3）如何输出最短路径

用二维数组 p[i][j] 记录从 到 的最短路径上 的直接前驱。

初始状态： 和 之间有边，则将 的前驱设置为 ，否则设置为

如果找到一条从 经过 到 的更短路径，则将 p[i][j] 更新为 p[k][j]

最后递归输出数组 内容

int dist[N][N]; //dist[i][j]用于存储从 i -> j 的最短路 int p[N][N]; //p[i][j]表示i到j的最短路上j的直接前驱 void floyd() { for (int k = 1; k <= n; k ++) for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; //找到一条从i经过k到j的更短路径 //将p[i][j]更新为p[k][j]，注意j的直接前驱不是k p[i][j] = p[k][j]; } } //递归输出s到t的最短路径，包含s但不包含t void displayPath(int s, int t) { if (p[s][t] != -1) { distplayPath(s, p[s][t]); cout << p[s][t] << "->"; } } 9.3 传递闭包 在交际网络中，给定若干个元素和若干对二元关系，且关系具有传递性。“通过传递性推导出尽量多的元素之间的关系”的问题被称为传递闭包

算法思想

建立邻接矩阵 用于存储每个元素之间的二元关系。

dist[i][j] = 1 表示 和 之间存在关系

dist[i][j] = 0 表示 和 之间不存在关系

dist[i][i] = 1 元素自身存在关系

使用 算法可以解决传递闭包问题

for (int k = 1; k <= n; k ++) for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) dist[i][j] |= dist[i][k] & dist[k][j]; 【练习】

B3647 【模板】Floyd - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[P2910 USACO08OPEN] Clear And Present Danger S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

B3611 【模板】传递闭包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

343. 排序 - AcWing题库

AcWing 344. 观光之旅 - AcWing