代码随想录算法训练营五十三天|图论part11

最后一天！！！

小明逛公园（Floyd算法精讲）

【题目描述】

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

给定一个公园景点图，图中有 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.

本题采用动态规划解决，单看代码是非常简单的，重点是理解原理。

1.确定dp数组及其下标的含义：

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

2.确定递推公式：

两种情况：

节点i到j的最短路径经过节点k：dp[i][j][k]=dp[i][k][k-1]+dp[k][j][k-1]；

节点i到j的最短路径不经过节点k：dp[i][j][k]=dp[i][j][k-1]。

所以递推公式：dp[i][j][k] = min(dp[i][k][k - 1] + dp[k][j][k - 1]， dp[i][j][k - 1])。

3.初始化：

对于输入的数据节点u，节点v，权值val，初始化dp[u][v][0]=val；

数组中其它元素的初始值为10001，因为题目给出边的最大距离为10000。

4.确定遍历顺序：

根据递推公式dp[i][j][k] = min(dp[i][k][k - 1] + dp[k][j][k - 1]， dp[i][j][k - 1])，我们可以看出k是依赖于k-1的，而i和j并不依赖于i-1和j-1。

所以三维数组dp的遍历顺序是从底层一层一层往上的，也就是要先遍历k，i和j的遍历顺序无所谓。

空间优化：

我们可以发现，k只是依赖于k-1的状态，而不需要记录k-2，k-3等等这些状态。

也就是说，我们只要记录一个dp[i][j][0]和dp[i][j][1]就可以了，二者交替滚动。

再进一步想，就算在本层计算dp[i][j]用了本层中刚计算好的dp[i][j]会有什么问题吗？

如果 本层刚计算好的 dp[i][k] 比上一层 （即k-1层）计算的 dp[i][k] 小，说明确实有 i 到 k 的更短路径，那么基于 更小的 dp[i][k] 去计算 dp[i][j] 没有问题。

如果 本层刚计算好的 dp[i][k] 比上一层 （即k-1层）计算的 dp[i][k] 大， 这不可能，因为这样也不会做更新 dp[i][k]的操作。

所以在本层计算中，使用了本层计算过的 dp[i][k] 和 dp[k][j] 是没问题的。

所以递归公式可以写为：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])。

代码如下：

import java.util.*;public class Main{public static void main(String[] args){Scanner in=new Scanner(System.in);int n=in.nextInt();int m=in.nextInt();int[][] dp=new int[n+1][n+1];for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){dp[i][j]=10001;}}for(int i=0;i<m;i++){int u=in.nextInt();int v=in.nextInt();int w=in.nextInt();dp[u][v]=w;dp[v][u]=w;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k][j]);}}}int q=in.nextInt();for(int i=0;i<q;i++){int start=in.nextInt();int end=in.nextInt();if(dp[start][end]!=10001)System.out.println(dp[start][end]);else System.out.println(-1);}}
}

骑士的攻击（A*算法）

题目描述

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

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

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

输入描述

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

接下来的 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

思路：

看到这个题目的第一想法就是广搜：

import java.util.*;public class Main {private static int[][] move=new int[1001][1001];private static int[][] dir = {{1, -2}, {-1, -2}, {-1, 2}, {1, 2}, {2, -1}, {-2, -1}, {-2, 1}, {2, 1}};public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();for (int i = 0; i < n; i++) {int a1 = in.nextInt();int a2 = in.nextInt();int b1 = in.nextInt();int b2 = in.nextInt();for(int j=0;j<=1000;j++){for(int k=0;k<=1000;k++){move[j][k]=0;}}bfs(a1, a2, b1, b2);System.out.println(move[b1][b2]);}}public static void bfs(int x, int y, int x2, int y2) {Queue<Integer> q = new LinkedList<>();q.offer(x);q.offer(y);while (!q.isEmpty()) {int curx=q.poll();int cury=q.poll();if(curx==x2&&cury==y2)break;for (int i = 0; i < 8; i++) {int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if (nextx < 1 || nexty < 1 || nextx > 1000 || nexty > 1000) continue;if (move[nextx][nexty]==0) {move[nextx][nexty] = move[curx][cury] + 1;q.offer(nextx);q.offer(nexty);}}}}
}

但是这样写是超时的，因为本题棋盘很大1000*1000，这就可能导致我们有很多点都需要查询。所以我们要考虑怎么不去搜索一些没必要的节点。

我们可以使用优先队列，队列中的元素按照权值F从小到大去排序。

F是什么？

G表示起点到当前遍历节点的路径消耗；

H表示目前遍历节点到最终节点的预估消耗；（注意这里的区别）

F=G+H。

代码如下：

import java.util.*;class Knight{int x,y;// F = G + H// G = 从起点到该节点路径消耗// H = 该节点到终点的预估消耗int f,g,h;public Knight(int x,int y,int g,int h){this.x=x;this.y=y;this.f=g+h;this.g=g;this.h=h;}
}
class MyComparison implements Comparator<Knight>{public int compare(Knight k1,Knight k2){return Integer.compare(k1.f,k2.f);}
}
public class Main {private static int[][] move=new int[1001][1001];private static int[][] dir = {{1, -2}, {-1, -2}, {-1, 2}, {1, 2}, {2, -1}, {-2, -1}, {-2, 1}, {2, 1}};public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();for (int i = 0; i < n; i++) {int a1 = in.nextInt();int a2 = in.nextInt();int b1 = in.nextInt();int b2 = in.nextInt();for(int j=0;j<=1000;j++){for(int k=0;k<=1000;k++){move[j][k]=0;}}bfs(a1, a2, b1, b2);System.out.println(move[b1][b2]);}}public static void bfs(int x, int y, int x2, int y2) {PriorityQueue<Knight> q = new PriorityQueue<>(new MyComparison());int g=0;int h=(x-x2)*(x-x2)+(y-y2)*(y-y2);q.offer(new Knight(x,y,g,h));while (!q.isEmpty()) {Knight cur=q.poll();if(cur.x==x2&&cur.y==y2)break;for (int i = 0; i < 8; i++) {int nextx = cur.x + dir[i][0];int nexty = cur.y + dir[i][1];if (nextx < 1 || nexty < 1 || nextx > 1000 || nexty > 1000) continue;g=cur.g+5;h=(nextx-x2)*(nextx-x2)+(nexty-y2)*(nexty-y2);if (move[nextx][nexty]==0) {move[nextx][nexty] = move[cur.x][cur.y] + 1;q.offer(new Knight(nextx,nexty,g,h));}}}}
}

时间复杂度：

最坏情况：O(n*2)，n是节点数量

最佳情况：从起点直接到终点，O(dlogd)（d表示起点到终点的深度）