代码随想录第六十二天| Floyd 算法精讲 A * 算法精讲 （A star算法） 最短路算法总结篇

Floyd 算法精讲

题目描述

小明希望在公园散步时找到从一个景点到另一个景点的最短路径。给定公园的景点图，包含 N 个景点和 M 条双向道路，每条道路有已知的长度。小明有 Q 个观景计划，每个计划包含一个起点和终点，求每个计划的最短路径长度。

输入包含景点数量 N、道路数量 M，接着 M 行每行三个整数 u、v、w 表示景点 u 和 v 之间的双向道路长度为 w。然后输入观景计划数量 Q，接着 Q 行每行两个整数 start 和 end。输出每个计划的最短路径长度，若无路径则输出 -1。

输入输出示例

输入：

7 3 1 2 4 2 5 6 3 6 8 2 1 2 2 3

输出：

4 -1

解题思路

算法原理

Floyd 算法是一种多源最短路径算法，基于动态规划思想。通过引入中间节点逐步更新所有节点对之间的最短距离，最终得到全局最优解。该算法可以处理带负权的图。

动态规划思想

1. 状态定义：grid[i][j][k] 表示从节点 i 到节点 j，只能经过节点 1 到 k 的最短距离。
2. 状态转移：grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1])，即不经过节点 k 或经过节点 k 的最小值。
3. 初始化：初始时，grid[i][j][0] 为直接连接的边的权值，其他为无穷大。
4. 遍历顺序：按 k、i、j 的顺序遍历，确保每一步都基于之前的结果。

空间优化

由于每次计算只依赖前一次的结果，可以将三维数组优化为二维数组，减少空间复杂度。

代码实现

import java.util.Scanner;

public class FloydAlgorithm {

    public static final int MAX_VAL = 10005; // 边的最大距离

    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];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                grid[i][j] = MAX_VAL; // 初始化为最大值
            }
        }

        // 输入道路信息
        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;
        }

        // Floyd 算法核心部分
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    // 更新 i 到 j 的最短路径
                    if (grid[i][k] + grid[k][j] < grid[i][j]) {
                        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] == MAX_VAL) {
                System.out.println(-1); // 无路径
            } else {
                System.out.println(grid[start][end]); // 最短路径长度
            }
        }
    }
}

代码注释

1. 初始化距离矩阵：grid[i][j] 初始化为最大值，表示初始时无路径。
2. 输入道路信息：读取每条道路并更新距离矩阵，双向道路需两边更新。
3. Floyd 算法核心：三重循环，逐步引入中间节点 k，更新所有节点对的最短路径。
4. 处理观景计划：对每个计划查询最短路径，若仍为最大值则输出 -1，否则输出路径长度。

总结

Floyd 算法通过动态规划思想，利用三维数组逐步更新节点间的最短路径。空间优化后使用二维数组，时间复杂度为 O(n^3)，适合稠密图或多源最短路径问题。理解动态规划的状态转移和遍历顺序是掌握该算法的关键。

A* 算法精讲

题目描述

在象棋中，骑士（马）按照“日”字形移动。给定骑士的起始坐标和目标坐标，计算从起点到达目标点所需的最短步数。棋盘大小为 1000x1000。

输入包含多个测试用例，每行给出起点和目标点的坐标。输出每个测试用例的最短步数。

输入输出示例

输入：

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

解题思路

算法原理

A* 算法是一种启发式搜索算法，结合了广度优先搜索（BFS）和迪杰斯特拉算法（Dijkstra）的优点，通过引入启发式函数来指导搜索方向，从而提高搜索效率。

关键点

• 启发式函数：用于估计当前节点到目标节点的距离，指导搜索方向。常见的启发式函数包括曼哈顿距离、欧氏距离和切比雪夫距离。本题采用欧氏距离。
• 优先级队列：根据启发式函数计算的值（F = G + H）对节点进行排序，优先扩展最有可能接近目标的节点。
• 节点状态记录：记录已访问节点的步数，避免重复访问。

代码实现

import java.util.*;
import java.awt.Point;
import java.util.PriorityQueue;

public class KnightAttack {

    // 定义骑士的8个可能移动方向
    private static final int[][] MOVES = {
        {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
        {1, -2}, {1, 2}, {2, -1}, {2, 1}
    };

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            int a1 = scanner.nextInt();
            int a2 = scanner.nextInt();
            int b1 = scanner.nextInt();
            int b2 = scanner.nextInt();
            System.out.println(astar(new Point(a1, a2), new Point(b1, b2)));
        }
    }

    private static int astar(Point start, Point end) {
        // 优先级队列，存储 (总代价, 当前位置, 已走步数)
        PriorityQueue<Node> heap = new PriorityQueue<>((a, b) -> Double.compare(a.f, b.f));
        heap.add(new Node(start, 0, heuristic(start, end)));

        // 记录访问过的节点及其步数
        Map<Point, Integer> visited = new HashMap<>();
        visited.put(start, 0);

        while (!heap.isEmpty()) {
            Node current = heap.poll();

            // 检查是否到达目标
            if (current.point.equals(end)) {
                return current.steps;
            }

            // 生成下一个可能的移动位置
            for (int[] move : MOVES) {
                Point nextPoint = new Point(current.point.x + move[0], current.point.y + move[1]);

                // 检查是否在棋盘范围内
                if (nextPoint.x >= 1 && nextPoint.x <= 1000 && nextPoint.y >= 1 && nextPoint.y <= 1000) {
                    int newSteps = current.steps + 1;
                    // 如果该位置未被访问或有更短路径
                    if (!visited.containsKey(nextPoint) || newSteps < visited.get(nextPoint)) {
                        visited.put(nextPoint, newSteps);
                        double f = newSteps + heuristic(nextPoint, end);
                        heap.add(new Node(nextPoint, newSteps, f));
                    }
                }
            }
        }

        // 如果无法到达目标
        return -1;
    }

    private static double heuristic(Point start, Point end) {
        // 欧氏距离启发式函数
        double dx = start.x - end.x;
        double dy = start.y - end.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    private static class Node {
        Point point;
        int steps;
        double f; // 总代价：f = steps + heuristic

        Node(Point point, int steps, double f) {
            this.point = point;
            this.steps = steps;
            this.f = f;
        }
    }
}

代码注释

1. 移动方向定义：骑士有8个可能的移动方向，用 moves 数组表示。
2. 启发式函数：heuristic 函数计算两个点之间的欧氏距离，作为估计距离。
3. A 搜索函数*：astar 函数使用优先级队列进行搜索，每次扩展最有可能接近目标的节点。
4. 优先级队列：队列中存储元组 (总代价, 当前位置x, 当前位置y, 已走步数)，按总代价排序。
5. 访问记录：visited 字典记录已访问节点及其最小步数，避免重复访问。
6. 输入处理：读取多个测试用例，对每个用例调用 astar 函数计算最短步数。

总结

A* 算法通过引入启发式函数，能够在大规模地图上高效地找到最短路径。相比传统的广度优先搜索（BFS），A* 算法通过优先扩展接近目标的节点，减少了不必要的搜索，提高了效率。选择合适的启发式函数对算法性能至关重要。

最短路算法总结

至此已经讲解了四大最短路算法，分别是 Dijkstra、Bellman-Ford、SPFA 和 Floyd。

针对这四大最短路算法，我用了七篇长文才彻底讲清楚，分别是：

• Dijkstra 朴素版
• Dijkstra 堆优化版
• Bellman-Ford
• Bellman-Ford 队列优化算法（又名 SPFA）
• Bellman-Ford 算法判断负权回路
• Bellman-Ford 之单源有限最短路
• Floyd 算法精讲
• 启发式搜索：A * 算法

最短路算法比较复杂，而且各自有各自的应用场景。以下是讲过的最短路算法的使用场景对比表：

（因为 A * 属于启发式搜索，和上面最短路算法并不是一类，不适合一起对比，所以没有放在一起）

可能有同学感觉：这个表太复杂了，我记也记不住。

其实记不住的原因还是对这几个最短路算法没有深刻的理解。这里给大家一个大体使用场景的分析：

• 如果遇到单源且边为正数，直接 Dijkstra。至于使用朴素版还是堆优化版，还是取决于图的稠密度。多少节点多少边算是稠密图，多少算是稀疏图，这个没有量化。如果想量化，只能写出两个版本然后做实验去测试，不同的判题机得出的结果还不太一样。一般情况下，可以直接用堆优化版本。
• 如果遇到单源边可为负数，直接 Bellman-Ford。同样 SPFA 还是 Bellman-Ford 取决于图的稠密度。一般情况下，直接用 SPFA。
• 如果有负权回路，优先 Bellman-Ford。如果是有限节点最短路，也优先 Bellman-Ford，理由是写代码比较方便。
• 如果是遇到多源点求最短路，直接 Floyd。除非源点特别少，且边都是正数，那可以多次 Dijkstra 求出最短路径，但这种情况很少。一般出现多个源点了，就是想让你用 Floyd 了。
• 对于 A *，由于其高效性，在实际工程应用中使用最为广泛。由于其结果的不唯一性，也就是可能是次短路的特性，一般不适合作为算法题。游戏开发、地图导航、数据包路由等都广泛使用 A * 算法。

图论总结

从深搜广搜到并查集，从最小生成树到拓扑排序，最后是最短路算法系列。

至此算上本篇，一共30篇文章，图论之旅就在此收官了。

在0098.所有可达路径，我们接触了两种图的存储方式，邻接表和邻接矩阵，掌握两种图的存储方式很重要。

图的存储方式也是大家习惯在核心代码模式下刷题经常忽略的知识点。因为在力扣上刷题不需要掌握图的存储方式。

深搜与广搜

在二叉树章节中，其实我们讲过了深搜和广搜在二叉树上的搜索过程。

在图论章节中，深搜与广搜就是在图这个数据结构上的搜索过程。

深搜与广搜是图论里基本的搜索方法，大家需要掌握三点：

• 搜索方式：深搜是一个方向搜，不到黄河不回头。广搜是围绕起点一圈一圈的去搜。
• 代码模板：需要熟练掌握深搜和广搜的基本写法。
• 应用场景：图论题目基本上可以用深搜也可用广搜，看哪个方便而已。

注意事项

需要注意的是，同样是深搜模板题，会有两种写法。

在0099.岛屿的数量深搜.md和0105.有向图的完全可达性，涉及到dfs的两种写法。

我们对dfs函数的定义是处理当前节点还是处理下一个节点很重要，决定了两种dfs的写法。

这也是为什么很多录友看到不同的dfs写法，结果发现提交都能过的原因。

而深搜还有细节，有的深搜题目需要用到回溯的过程，有的就不用回溯的过程，

一般是需要计算路径的问题需要回溯，如果只是染色问题（岛屿问题系列）就不需要回溯。

例如：0105.有向图的完全可达性深搜就不需要回溯，而0098.所有可达路径中的递归就需要回溯，文章中都有详细讲解

注意：以上说的是不需要回溯，不是没有回溯，只要有递归就会有回溯，只是我们是否需要用到回溯这个过程，这是需要考虑的。

很多录友写出来的广搜可能超时了，例如题目：0099.岛屿的数量广搜

根本原因是只要加入队列就代表走过，就需要标记，而不是从队列拿出来的时候再去标记走过。

具体原因，我在0099.岛屿的数量广搜中详细讲了。

在深搜与广搜的讲解中，为了防止惯性思维，我特别加入了题目0106.岛屿的周长，提醒大家，看到类似的题目，也不要上来就想着深搜和广搜。

还有一些图的问题，在题目描述中，是没有图的，需要我们自己构建一个图，例如0110.字符串接龙，题目中连线都没有，需要我们自己去思考什么样的两个字符串可以连成线。

并查集

并查集相对来说是比较复杂的数据结构，其实他的代码不长，但想彻底学透并查集，需要从多个维度入手，

我在理论基础篇的时候讲解如下重点：

• 为什么要用并查集，怎么不用个二维数据，或者set、map之类的。
• 并查集能解决那些问题，哪些场景会用到并查集
• 并查集原理以及代码实现
• 并查集写法的常见误区
• 带大家去模拟一遍并查集的过程
• 路径压缩的过程
• 时间复杂度分析

上面这几个维度大家都去思考了，并查集基本就学明白了。

其实理论基础篇就算是给大家出了一道裸的并查集题目了，所以在后面的题目安排中，会稍稍的拔高一些，重点在于并查集的应用上。

例如并查集可以判断这个图是否是树，因为树的话，只有一个根，符合并查集判断集合的逻辑，题目：0108.冗余连接。

在0109.冗余连接II中对有向树的判断难度更大一些，需要考虑的情况比较多。

最小生成树

最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。

最小生成树算法，有prim和kruskal。

prim算法是维护节点的集合，而Kruskal是维护边的集合。

在稀疏图中，用Kruskal更优。在稠密图中，用prim算法更优。

边数量较少为稀疏图，接近或等于完全图（所有节点皆相连）为稠密图

Prim算法时间复杂度为O(n^2)，其中n为节点数量，它的运行效率和图中边树无关，适用稠密图。

Kruskal算法时间复杂度为O(nlogn)，其中n为边的数量，适用稀疏图。

关于prim算法，我自创了三部曲，来帮助大家理解：

第一步，选距离生成树最近节点

第二步，最近节点加入生成树

第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

大家只要理解这三部曲，prim算法至少是可以写出一个框架出来，然后在慢慢补充细节，这样不至于自己在写prim的时候两眼一抹黑完全凭感觉去写。

minDist数组是prim算法的灵魂，它帮助prim算法完成最重要的一步，就是如何找到距离最小生成树最近的点。

kruscal的主要思路：

• 边的权值排序，因为要优先选最小的边加入到生成树里
• 遍历排序后的边
• 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
• 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

而判断节点是否在一个集合以及将两个节点放入同一个集合，正是并查集的擅长所在。

所以Kruskal是需要用到并查集的。

这也是我在代码随想录图论编排上为什么要先讲解并查集在讲解最小生成树。

拓扑排序

拓扑排序是在图上的一种排序。

概括来说，给出一个有向图，把这个有向图转成线性的排序就叫拓扑排序。

同样，拓扑排序也可以检测这个有向图是否有环，即存在循环依赖的情况。

拓扑排序的一些应用场景，例如：大学排课，文件下载依赖等等。

只要记住如下两步拓扑排序的过程，代码就容易写了：

• 找到入度为0的节点，加入结果集
• 将该节点从图中移除

最短路算法

最短路算法是图论中，比较复杂的算法，而且不同的最短路算法都有不同的应用场景。

我在最短路算法总结篇里已经做了一个高度的概括。

大家要时常温故而知新，才能透彻理解各个最短路算法。