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的最短距离可以由更小的区间组成。

那么这样我们是不是就找到了，子问题推导求出整体最优方案的递归关系呢。

这里我们用 grid数组来存图，那就把dp数组命名为 grid。

grid[i][j][k] = m，表示 节点i 到节点j 以[1...k] 集合中的一个节点为中间节点的最短距离为m。

这里的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]

节点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])

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 的最小距离了。

遍历的顺序是从底向上一层一层去遍历。

所以遍历k 的for循环一定是在最外面，这样才能一层一层去遍历。

kama97. 小明逛公园

题目描述
小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。
给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。
小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。请你帮助小明计算出每个观景计划的最短路径长度。
输入描述
第一行包含两个整数 N, M, 分别表示景点的数量和道路的数量。
接下来的 M 行，每行包含三个整数 u, v, w，表示景点 u 和景点 v 之间有一条长度为 w 的双向道路。
接下里的一行包含一个整数 Q，表示观景计划的数量。
接下来的 Q 行，每行包含两个整数 start, end，表示一个观景计划的起点和终点。
输出描述
对于每个观景计划，输出一行表示从起点到终点的最短路径长度。如果两个景点之间不存在路径，则输出 -1。
输入示例
7 3
2 3 4
3 6 6
4 7 8
2
2 3
3 4
输出示例
4
-1
提示信息
从 2 到 3 的路径长度为 4，3 到 4 之间并没有道路。
1 <= N, M, Q <= 1000.
1 <= w <= 10000.

#include <bits/stdc++.h>
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,10001)));while(m--){cin>>p1>>p2>>val;grid[p1][p2][0] = val;//可以想象为一个三维的空间，我们只初始化空间的底层，后续遍历的时候从底层一层一层往上遍历。grid[p2][p1][0] = val;//双向图！！！}for(int k = 1;k<=n;k++)//注意这里先遍历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 q,start,end;cin>>q;while(q--){cin>>start>>end;if(grid[start][end][n]==10001)cout<<"-1"<<endl;else cout<<grid[start][end][n]<<endl;}
}

A * 算法

Astar 是一种广搜的改良版。有的是 Astar是 dijkstra 的改良版。

其实只是场景不同而已我们在搜索最短路的时候，如果是无权图（边的权值都是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 * 算法的结果不同。

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

相对了普通BFS，A * 算法只从队列里取出距离终点最近的节点。

那么问题来了，A * 在一次路径搜索中，大量不需要访问的节点都在队列里，会造成空间的过度消耗。

IDA * 算法对这一空间增长问题进行了优化，关于 IDA * 算法，本篇不再做讲解，感兴趣的录友可以自行找资料学习。

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

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

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

127. 骑士的攻击

题目描述
在象棋中，马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，计算从起点到达目标点所需的最短步数。
棋盘大小 1000 x 1000（棋盘的 x 和 y 坐标均在 [1, 1000] 区间内，包含边界）
输入描述
第一行包含一个整数 n，表示测试用例的数量，1 <= n <= 100。
接下来的 n 行，每行包含四个整数 a1, a2, b1, b2，分别表示骑士的起始位置 (a1, a2) 和目标位置 (b1, b2)。
输出描述
输出共 n 行，每行输出一个整数，表示骑士从起点到目标点的最短路径长度。
输入示例
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
提示信息
骑士移动规则如图，红色是起始位置，黄色是骑士可以走的地方。

#include <bits/stdc++.h>
using namespace std;
int dir[8][2] = {-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
int moves[1001][1001];
int b1, b2;
struct Knight
{int x,y;int f,g,h; //f = g + h;  g为从起点到当前遍历节点的消耗，h为当前遍历节点到终点的“预计“消耗bool operator < (const Knight& k) const{return k.f < f;//后续的priority_queue会根据这个来找出f最小的。} 
};
priority_queue<Knight> que;
int calDistance(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;next.g = cur.g + 5;//马走日，2*2+1*1.next.h = calDistance(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 = calDistance(start);start.f = start.g + start.h;astar(start);while(!que.empty())que.pop();cout<<moves[b1][b2]<<endl;}return 0;
}