Day62 图论part11
Floyd 算法精讲
Floyd 算法代码很简单，但真正理解起原理 还是需要花点功夫，大家在看代码的时候，会发现 Floyd 的代码很简单，甚至看一眼就背下来了，但我为了讲清楚原理，本篇还是花了大篇幅来讲解。
代码随想录
方法1：三维dp数组
import java.util.*;
public class Main{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][][] grid = new int[n+1][n+1][n+1];
//grid[i][j][k] = m 表示节点i 到 j ，以[1...k] 集合为中间节点的最短距离为m
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
Arrays.fill(grid[i][j], Integer.MAX_VALUE);
}
grid[i][i][0] = 0;
}
for(int i = 0; i < m; i++){
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
grid[u][v][0] = w;
grid[v][u][0] = w;
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(grid[i][k][k-1] != Integer.MAX_VALUE && grid[k][j][k-1] != Integer.MAX_VALUE){
grid[i][j][k] = Math.min(grid[i][j][k-1], grid[i][k][k-1]+grid[k][j][k-1]);
}else{
grid[i][j][k] = grid[i][j][k-1];// grid[i][j][k]并不会继承grid[i][j][k-1]，而是保留为初始值;
}
}
}
}
int q = sc.nextInt();
for(int i = 0; i < q; i++){
int start = sc.nextInt();
int end = sc.nextInt();
if(grid[start][end][n] == Integer.MAX_VALUE){
System.out.println(-1);
}else{
System.out.println(grid[start][end][n]);
}
}
}
}方法2：二维dp数组
import java.util.*;
public class Main{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] grid = new int[n+1][n+1];
//grid[i][j][k] = m 表示节点i 到 j ，以[1...k] 集合为中间节点的最短距离为m
for(int i = 1; i <= n; i++){
Arrays.fill(grid[i], 10001);
grid[i][i] = 0;
}
for(int i = 0; i < m; i++){
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
grid[u][v] = w;
grid[v][u] = w;
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
grid[i][j] = Math.min(grid[i][j], grid[i][k]+grid[k][j]);
}
}
}
int q = sc.nextInt();
for(int i = 0; i < q; i++){
int start = sc.nextInt();
int end = sc.nextInt();
if(grid[start][end] == 10001){
System.out.println(-1);
}else{
System.out.println(grid[start][end]);
}
}
}
}总结
1.确定dp数组（dp table）以及下标的含义：
//grid[i][j][k] = m 表示节点i 到 j ，以[1...k] 集合为中间节点的最短距离为m2
2.确定递推公式
第一种情况：不经过中间节点K，那么
grid[i][j][k] = grid[i][j][k-1]
第二种情况：经过中间节点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] = Math.min(grid[i][j][k-1], grid[i][k][k-1]+grid[k][j][k-1]);
3.dp数组如何初始化：需要初始化K=0的情况，K=0，就是两个节点直接相连，没有中间节点，所以直接赋值边的权值就可以了(双向或者无向需要两个方向初始化，有向图只要一个方向初始化)。然后其他对角元素应该初始化为0，其他元素初始化为边的权值的最大值（10001或者最大整形都可以，10001更加方便，后续不需要考虑溢出的情况）。
4.确定遍历顺序：
grid[i][j][k] = Math.min(grid[i][j][k-1], grid[i][k][k-1]+grid[k][j][k-1]);
初始化的时候把 k =0 的 i 和j 对应的数值都初始化了，这样才能去计算 k = 1 的时候 i 和 j 对应的数值。这就好比是一个三维坐标，i 和j 是平层，而k是垂直向上的。遍历的顺序是从底向上 一层一层去遍历。所以遍历k 的for循环一定是在最外面，这样才能一层一层去遍历。k 依赖于 k - 1， i 和j 的到并不依赖与 i - 1 或者 j - 1 。所以一定是把k 的for循环放在最外面，才能用上 初始化和上一轮计算的结果了。i和j的遍历顺序就无所谓了。
5.二维的dp数组，就把k这一维度去掉。每次进入新的k，其实都保留着上一轮k的数值，靠着最外层的for循环，来实现对k的滚动。
6.Floyd 算法的时间复杂度相对较高，Floyd 算法适合多源最短路，即 求多个起点到多个终点的多条最短路径。适合 稠密图且源点较多的情况。时间复杂度： O(n^3)；如果 源点少，其实可以 多次dijsktra 求源点到终点。Floyd 算法对边的权值正负没有要求，都可以处理。
A * 算法精讲 （A star算法）
一般 笔试或者 面试的时候，不会考察A*， 都是会结合具体业务场景问 A*算法，例如：地图导航，游戏开发 等等。其实基础版的A* 并不难，所以大家不要畏惧，理解本篇内容，甚至独立写出代码，大家可以做到，加油
A * 算法精讲 （A star算法） | 代码随想录
import java.util.*;
public class Main {
static int[][] moves = new int[1001][1001]; // 记录每个位置的移动次数
static int[][] dir = { // 马的8个方向
{-2, -1}, {-2, 1}, {-1, 2}, {1, 2},
{2, 1}, {2, -1}, {1, -2}, {-1, -2}
};
static int b1, b2; // 目标位置的x, y坐标
static class Knight implements Comparable<Knight> {
int x, y, g, h, f;
Knight(int x, int y, int g, int h) {
this.x = x;
this.y = y;
this.g = g; // G = 从起点到该节点的路径消耗
this.h = h; // H = 从该节点到终点的预估消耗
this.f = g + h; // F = G + H
}
@Override
public int compareTo(Knight k) {
return Integer.compare(this.f, k.f); // 按照f值从小到大排序
}
}
// 欧拉距离的启发函数（不开根号以提高精度）
static int heuristic(Knight k) {
return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2);
}
static void astar(Knight start) {
PriorityQueue<Knight> queue = new PriorityQueue<>();
queue.add(start);
while (!queue.isEmpty()) {
Knight cur = queue.poll(); // 取出f值最小的节点
// 如果到达目标位置，直接退出
if (cur.x == b1 && cur.y == b2) {
break;
}
for (int[] d : dir) {
int nx = cur.x + d[0];
int ny = cur.y + d[1];
// 检查边界
if (nx < 1 || nx > 1000 || ny < 1 || ny > 1000) {
continue;
}
// 如果这个位置没有访问过
if (moves[nx][ny] == 0) {
moves[nx][ny] = moves[cur.x][cur.y] + 1; // 更新移动次数
int g = cur.g + 5; // 马走日消耗固定为5
int h = heuristic(new Knight(nx, ny, 0, 0));
Knight next = new Knight(nx, ny, g, h);
queue.add(next); // 加入优先队列
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 测试案例数量
while (n-- > 0) {
int a1 = sc.nextInt(), a2 = sc.nextInt(); // 起点坐标
b1 = sc.nextInt();
b2 = sc.nextInt(); // 终点坐标
for (int[] row : moves) {
Arrays.fill(row, 0); // 初始化moves数组
}
Knight start = new Knight(a1, a2, 0, heuristic(new Knight(a1, a2, 0, 0)));
astar(start);
System.out.println(moves[b1][b2]); // 输出结果
}
sc.close();
}
}PriorityQueue<Knight> queue = new PriorityQueue<>();这个PriorityQueue 自动根据 compareTo 方法维护堆的性质或任何自定义比较器的实现。
@Override
public int compareTo(Person other) {
return Integer.compare(this.age, other.age); // 按年龄升序排序
}
//反向比较
@Override
public int compareTo(Knight k) {
return Integer.compare(k.f, this.f); // 交换位置，k 在前面
}
1.为什么按照 F 值排序？
- F = G + H 表示从起点经过当前节点到终点的总代价估计值。
- 按照 F 值排序能够保证优先探索 当前预估代价最小的路径，从而以最快的速度找到最优解。
示例解释
假设：
- 当前节点 A 的 G=2, H=5, 所以 F=2+5=7。
- 另一个节点 B 的 G=4, H=2, 所以 F=4+2=6。
如果只按照 H 值排序，会优先选择 A（H = 5）：
- 但 A 的总代价 F=7，并不是最优路径。
按照 F 值排序，会优先选择 B（F = 6），更接近最终的最优路径。
核心思路就是从队列里面优先弹出F值更小的元素，那么使用优先级队列就可以做到。Java 的优先级队列 (PriorityQueue) 默认是小顶堆。这意味着在队列中，优先级最低的元素（数值最小的元素）会排在队首，即最先被弹出。
2.moves 数组的作用是 记录某个棋盘位置是否已经访问过，以及该位置从起点到当前的 步数。
3.Astar 是一种 广搜的改良版。 或者是 dijkstra 的改良版。如果是无权图（边的权值都是1） 那就用广搜。如果是有权图（边有不同的权值），优先考虑 dijkstra。Astar 关键在于 启发式函数， 也就是 影响 广搜或者 dijkstra 从 容器（队列）里取元素的优先顺序。
最短路算法总结篇
最各个最短路算法有个全面的了解
最短路算法总结篇 | 代码随想录
图论总结
图论总结篇 | 代码随想录