代码随想录算法训练营第60期第六十五天打卡

        大家好，今天是我们的第六十五天了，我们的算法训练营马上结束了，回想这一路下来真实不容易，中间好多次想偷懒但是依旧选择了坚持下来，我们还是要认认真真讲解完今天的内容，我们今天的内容是我比较熟悉的一种算法叫做Floyd算法还有一个bellman_ford之单源有限最短路，还有A*算法，我们明天对我们整个图论进行一个总结，我们今天先把所有的算法都过一遍。

第一部分 bellman_ford之单源有限最短路

        我们前几次博客已经了解过这个最短路算法，到这里我发现这个算法的用途还是很广泛的，我们今天来看看单源有限最短路，节点数量为n，起点到终点，最多是 n-1 条边相连。 那么对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离。理论上来说，对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。对所有边松弛两次，相当于计算 起点到达 与起点两条边相连的节点的最短距离。但在对所有边松弛第一次的过程中，大家会发现，不仅仅 与起点一条边相连的节点更新了，所有节点都更新了。到这里大家可能不清楚我可以给大家模拟一下松弛一次的操作：

         大家可以看上图，边：节点1 -> 节点2，权值为-1 ，minDist[2] > minDist[1] + (-1)，更新 minDist[2] = minDist[1] + (-1) = 0 - 1 = -1 ，边：节点2 -> 节点3，权值为1 ，minDist[3] > minDist[2] + 1 ，更新 minDist[3] = minDist[2] + 1 = -1 + 1 = 0 ，接下来是边：节点3 -> 节点1，权值为-1 ，minDist[1] > minDist[3] + (-1)，更新 minDist[1] = 0 + (-1) = -1 ，边：节点3 -> 节点4，权值为1 ，minDist[4] > minDist[3] + 1，更新 minDist[4] = 0 + 1 = 1 ，以上是对所有边进行的第一次松弛，最后 minDist数组为 ：-1 -1 0 1 ，（从下标1算起）当然我还可以继续松弛第二次，但在对所有边松弛第一次的过程中，大家会发现，不仅仅 与起点一条边相连的节点更新了，所有节点都更新了。而且对所有边的后面几次松弛，同样是更新了所有的节点，说明 至多经过k 个节点 这个限制 根本没有限制住，每个节点的数值都被更新了。这样的话我么就应该在每次计算 minDist 时候，要基于 对所有边上一次松弛的 minDist 数值才行，所以我们要记录上一次松弛的minDist。

     其实关于这个算法，代码随想录是给出了一道例题，同时给出了这道例题的多种优化解法，我就不带大家来解这道例题了，不过大家可以自己去看看，鉴于一刷代码随想录大家还是理解好基础理论就可以，理解好各种最短路算法的使用场景与拓展应用即可。

第二部分 Floyd 算法

      这个算法我就比较熟悉了，我可以带大家刷一道例题，我们就看给出的例题：

        这道题目是多个节点多条边的图里面寻找最短路问题，我们就看看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 到 节点9 的最短距离 可以由 节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成， 也可以有 节点1 到节点7的最短距离 + 节点7 到节点9的最短距离的距离组成。但是我们由于是求最短路问题我们应该是取最小值，这里我们其实都有一个媒介，就是中间变量，这里就需要使用动规五部曲来讲解Floyd算法。

       第一步确定dp数组（dp table）以及下标的含义，这里我们用 grid数组来存图，那就把dp数组命名为 grid。grid[i][j][k] = m，表示 节点i 到 节点j 以[1...k] 集合中的一个节点为中间节点的最短距离为m。这里其实是可以优化的，可以将三维数组优化为二维数组，节点i 到 节点j 的最短路径中 一定是经过很多节点，那么这个集合用[1...k] 来表示。所以 这里的k不能单独指某个节点，k 一定要表示一个集合，即[1...k] ，表示节点1 到 节点k 一共k个节点的集合。接下来是确定递推公式，有这样几种情况：节点i 到 节点j 的最短路径经过节点k，节点i 到 节点j 的最短路径不经过节点k，对于第一种情况grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]，对于第二种情况grid[i][j][k] = 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])，接下来重要的问题是dp数组如何初始化，我们只能 把k 赋值为 0，本题 节点0 是无意义的，节点是从1 到 n。因此起初我们是无法判断k是什么值的，本题求的是最小值，所以输入数据没有涉及到的节点的情况都应该初始为一个最大数。接下来是确定遍历顺序，我们来看初始化，我们是把 k =0 的 i 和j 对应的数值都初始化了，这样才能去计算 k = 1 的时候 i 和 j 对应的数值。我们一定要将k放到最外面。

       有了如上的思路我们就可以尝试给出代码：

#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;}
}

       这个算法其实是动态规划的思想，我们需要一个中转点，而且要时刻取最短，这个算法的缺点就是时间复杂度比较高，还要注意初始化的时候我们的无向图是双向的。

第三部分 A * 算法

        这个算法我以前也是没有听说过的，这还是第一次听说，我们先来看看这个算法是做什么的？Astar 是一种 广搜的改良版。 有的是 Astar是 dijkstra 的改良版。其实只是场景不同而已 我们在搜索最短路的时候， 如果是无权图（边的权值都是1） 那就用广搜，代码简洁，时间效率和 dijkstra 差不多 （具体要取决于图的稠密），看到这句话我们大致了解了，这个算法还是求最短路的，其实我们也知道广搜深度很容易超时，尤其是深搜本质上是递归，递归的时间复杂度是非常高的，大家可以发现 BFS 是没有目的性的 一圈一圈去搜索， 而 A * 是有方向性的去搜索。这样其实就可以提高搜索的效率，A*算法的关键在于启发式函数。每个节点的权值为F，给出公式为：F = G + H，G：起点达到目前遍历节点的距离，H：目前遍历的节点到达终点的距离，关于距离我们选用欧氏距离（欧拉距离） ，计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )，大家在数学里面两点间的距离公式应该也是这个，可以使用 优先级队列 帮我们排好序，每次出队列，就是F最小的节点。这样我们就可以给出代码：

#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;
}

       如果大家不明白可以放一放，以后我还会补充博客的，我目前也只能看着答案敲一遍，大家尽力就可以，这些算法其实都很难，代码量比较大。

今日总结

      今天的几种最短路算法其实都很难，第一次大家看不懂很正常，大家完全可以等算法功底扎实了以后再回来看，我以后也会持续更新，目前写的可能有点草率，希望大家可以见谅，我们今天的内容就到这里，我们下次博客再见！