图论篇--代码随想录算法训练营第六十一天打卡| Floyd 算法，A*算法

Floyd 算法（求多源汇最短路）

题目链接：97. 小明逛公园

题目描述：

小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。 

给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。

小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。 请你帮助小明计算出每个观景计划的最短路径长度。

算法思想：

使用三重for循环，遍历从1~n节点，grip二维数组含义是表示点i和j间的距离，将其初始化为INT_MAX，对角线初始化为0。使用grip[i][j] = min(grip[i][j],grip[i][k]+grip[k][j])来判断最短路径。

代码：

#include<iostream>
#include<vector>
#include<climits>
using namespace std;void floyd(vector<vector<int>>& graphs)
{int n = graphs.size() - 1;for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(graphs[i][k] != INT_MAX && graphs[k][j] != INT_MAX)graphs[i][j] = min(graphs[i][j],graphs[i][k] + graphs[k][j]);
}int main()
{int n,m;cin >> n >> m;vector<vector<int>> graphs(n+1,vector<int>(n+1,INT_MAX));for(int i = 1; i <= n; i++) graphs[i][i] = 0;for(int i = 0; i < m; i++){int u,v,w;cin >> u >> v >> w;graphs[u][v] = min(graphs[u][v],w);graphs[v][u] = min(graphs[v][u],w);}floyd(graphs);int q;cin >> q;while(q--){int start,end;cin >> start >> end;if(graphs[start][end] == INT_MAX) cout << -1 << endl;else cout << graphs[start][end] << endl;}return 0;
}

A*算法

题目链接：127. 骑士的攻击

题目描述：

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

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

算法思想：

1、该算法是对宽搜算法的优化，能保证有方向地去搜索点。在宽搜基础上增添了权重概念。

2、如何保证有方向搜索--对每一个点设置一个权重f，f=g+h，g表示起点达到目前遍历节点的距离，h表示目前遍历的节点到达终点的距离。距离计算公式如下：

• 曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)
• 欧氏距离（常用，不会超时） ，计算方式：d =  (x1-x2)^2 + (y1-y2)^2 
• 切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))

3、每次使用具有最小权重的点来更新节点位置--->使用优先级队列保存

代码：

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;int b1,b2;
int dx[8] = {-1,-1,1,1,2,2,-2,-2};
int dy[8] = {2,-2,2,-2,-1,1,-1,1};typedef struct Knight
{int a1,a2;int f,g,h;bool operator < (const struct Knight& k) const{return k.f < f;}
}Knight;int function(const Knight& knt)
{return (knt.a1 - b1)*(knt.a1 - b1) + (knt.a2 - b2)*(knt.a2 - b2);
}void Astar(vector<vector<int>>& step, const Knight& knt, priority_queue<Knight>& pq)
{Knight cur,next;while(!pq.empty()){cur = pq.top(),pq.pop();if(cur.a1 == b1 && cur.a2 == b2) break;for(int i = 0; i < 8; i++){next.a1 = cur.a1 + dx[i];next.a2 = cur.a2 + dy[i];if(next.a1 < 1 || next.a1 > 1000 || next.a2 < 1 || next.a2 > 1000) continue;if(!step[next.a1][next.a2]){step[next.a1][next.a2] = step[cur.a1][cur.a2] + 1;next.g = cur.g + 5;next.h = function(next);next.f = next.g + next.h;pq.push(next);}}}
}int main()
{int a1,a2,n;cin >> n;while(n--){priority_queue<Knight> pq;vector<vector<int>> step(1010,vector<int>(1010));cin >> a1 >> a2 >> b1 >> b2;Knight knt;knt.a1 = a1;knt.a2 = a2;knt.g = 0;knt.h = function(knt);knt.f = knt.g + knt.h;pq.push(knt);Astar(step,knt,pq);cout << step[b1][b2] << endl;}return 0;
}