前言

这里记录一下陈菜菜的刷题记录，主要应对25秋招、春招
个人背景
211CS本+CUHK计算机相关硕，一年车企软件开发经验
代码能力：有待提高
常用语言：C++

系列文章目录

第66天 ：第十一章：图论part11

---

`

---

---

一、今日任务

● Floyd 算法精讲
● A * 算法精讲 （A star算法）
● 最短路算法总结篇

二、详细布置

Floyd 算法精讲

Floyd 算法解决多源最短路问题
dijkstra朴素版、dijkstra堆优化、Bellman算法、Bellman队列优化（SPFA） 都是单源最短路，即只能有一个起点。

Floyd 算法对边的权值正负没有要求，都可以处理。
Floyd算法核心思想是动态规划。

Floyd动规五部曲：

1、确定dp数组（dp table）以及下标的含义
把dp数组命名为 grid。
grid[i][j][k] = m，表示 节点i 到 节点j 以[1…k] 集合为中间节点的最短距离为m。
2、确定递推公式

分两种情况：
节点i 到 节点j 的最短路径经过节点k
节点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 是不确定的。把k 赋值为 0，本题 节点0 是无意义的，节点是从1 到 n.

vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));  // C++定义了一个三位数组，10005是因为边的最大距离是10^4for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2][0] = val;grid[p2][p1][0] = val; // 注意这里是双向图
} 

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 等等

遍历k 的for循环一定是在最外面，这样才能一层一层去遍历。至于遍历 i 和 j 的话，for 循环的先后顺序无所谓。

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]);}}
}

模板

#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^4for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2][0] = val;grid[p2][p1][0] = val; // 注意这里是双向图}// 开始 floydfor (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;}
}

空间优化（二维数组）

#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^4for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2] = val;grid[p2][p1] = val; // 注意这里是双向图}// 开始 floydfor (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;}
}

floyd算法的时间复杂度相对较高，适合 稠密图且源点较多的情况。
如果是稀疏图，floyd是从节点的角度去计算了，例如 图中节点数量是 1000，就一条边，那 floyd的时间复杂度依然是 O(n^3) 。
如果 源点少，其实可以 多次dijsktra 求源点到终点。

题目链接：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 <= N, M, Q <= 1000.

样例1：

输入：
7 3
2 3 4
3 6 6
4 7 8
2
2 3
3 4
输出：
4
-1

A * 算法精讲 （A star算法）

Astar 是一种 广搜的改良版
我们在搜索最短路的时候， 如果是无权图（边的权值都是1） 那就用广搜，代码简洁，时间效率和 dijkstra 差不多 （具体要取决于图的稠密）

如果是有权图（边有不同的权值），优先考虑 dijkstra。

而 Astar 关键在于 启发式函数， 也就是 影响 广搜或者 dijkstra 从 容器（队列）里取元素的优先顺序。
BFS 是没有目的性的 一圈一圈去搜索， 而 A * 是有方向性的去搜索。

从队列里取出什么元素，接下来就是从哪里开始搜索。
所以 启发式函数 要影响的就是队列里元素的排序！

对队列里节点进行排序，就需要给每一个节点权值，如何计算权值呢？

每个节点的权值为F，给出公式为：F = G + H

G：起点达到目前遍历节点的距离

H：目前遍历的节点到达终点的距离

起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离 就是起点到达终点的距离。

本题的图是无权网格状，在计算两点距离通常有如下三种计算方式：

曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)
欧氏距离（欧拉距离） ，计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )
切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))
x1, x2 为起点坐标，y1, y2 为终点坐标 ，abs 为求绝对值，sqrt 为求开根号，

选择哪一种距离计算方式 也会导致 A * 算法的结果不同。

本题，采用欧拉距离才能最大程度体现 点与点之间的距离。

所以 使用欧拉距离计算 和 广搜搜出来的最短路的节点数是一样的。 （路径可能不同，但路径上的节点数是相同的）

#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;// 开始计算Fnext.g = cur.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5next.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 * 退化成广搜，算法的时间复杂度 是 O(n * 2)，n 为节点数量。

最佳情况，是从起点直接到终点，时间复杂度为 O(dlogd)，d 为起点到终点的深度。

因为在搜索的过程中也需要堆排序，所以是 O(dlogd)。

实际上 A * 的时间复杂度是介于 最优 和最坏 情况之间， 可以 非常粗略的认为 A * 算法的时间复杂度是 O(nlogn) ，n 为节点数量。

A * 算法的空间复杂度 O(b ^ d) ,d 为起点到终点的深度，b 是 图中节点间的连接数量，本题因为是无权网格图，所以 节点间连接数量为 4。

有一种场景 是 A * 解决不了的。

如果题目中，给出 多个可能的目标，然后在这多个目标中 选择最近的目标，这种 A * 就不擅长了， A * 只擅长给出明确的目标 然后找到最短路径。

如果是多个目标找最近目标（特别是潜在目标数量很多的时候），可以考虑 Dijkstra ，BFS 或者 Floyd。

题目链接：127题链接
文章讲解：图文讲解

题目描述

在象棋中，马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，计算从起点到达目标点所需的最短步数。

骑士移动规则如图，红色是起始位置，黄色是骑士可以走的地方。

棋盘大小 1000 x 1000（棋盘的 x 和 y 坐标均在 [1, 1000] 区间内，包含边界）

输入描述

第一行包含一个整数 n，表示测试用例的数量。

接下来的 n 行，每行包含四个整数 a1, a2, b1, b2，分别表示骑士的起始位置 (a1, a2) 和目标位置 (b1, b2)。

输出描述

输出共 n 行，每行输出一个整数，表示骑士从起点到目标点的最短路径长度。

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

样例1：

输入：
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
输出：
2
4
6
5
1
0     

最短路径总结

如果遇到单源且边为正数，直接Dijkstra。

至于 使用朴素版还是 堆优化版 还是取决于图的稠密度， 多少节点多少边算是稠密图，多少算是稀疏图，这个没有量化，如果想量化只能写出两个版本然后做实验去测试，不同的判题机得出的结果还不太一样。

一般情况下，可以直接用堆优化版本。

如果遇到单源边可为负数，直接 Bellman-Ford，同样 SPFA 还是 Bellman-Ford 取决于图的稠密度。

一般情况下，直接用 SPFA。

如果有负权回路，优先 Bellman-Ford， 如果是有限节点最短路 也优先 Bellman-Ford，理由是写代码比较方便。

如果是遇到多源点求最短路，直接 Floyd。

除非 源点特别少，且边都是正数，那可以 多次 Dijkstra 求出最短路径，但这种情况很少，一般出现多个源点了，就是想让你用 Floyd 了。

总结

今天主要学习了图的一系列操作，感觉是图的算法多且难，但是考察很多，记忆重点，多写代码，练习中巩固。
加油，坚持打卡的第66天。