第十一章：图论part11
Floyd 算法精讲
Floyd 算法代码很简单，但真正理解起原理 还是需要花点功夫，大家在看代码的时候，会发现 Floyd 的代码很简单，甚至看一眼就背下来了，但我为了讲清楚原理，本篇还是花了大篇幅来讲解。
文章讲解
思路
- 本题是经典的多源最短路问题，即 求多个起点到多个终点的多条最短路径。
Floyd算法简介及其核心思想
Floyd算法，又称为Floyd-Warshall算法，是一种用于求解所有节点对之间最短路径的算法。该算法特别强大的一点是，它对边的权值正负没有限制，也就是说，边的权值可以是正数、零，甚至是负数（前提是没有负权环）。因此，Floyd算法能够处理更广泛的问题。
Floyd算法的核心思想：动态规划
Floyd算法的核心思想是动态规划。它通过不断更新所有节点对之间的最短路径，最终找到全局最优解。
递推关系的推导：
直接路径：如果我们要计算节点1到节点9的最短路径，可以直接从节点1到节点9得到该路径的初始值，记为
grid[1][9]。-
通过中间节点路径：节点1到节点9的最短路径可以通过某个中间节点（如节点5）来拆分，即：grid[1][9] = grid[1][5] + grid[5][9]
其中，
grid[1][5]表示从节点1到节点5的最短路径，而grid[5][9]表示从节点5到节点9的最短路径。 -
逐步分解：进一步地，节点1到节点5的最短路径可以通过其他中间节点（如节点3）来分解：grid[1][5] = grid[1][3] + grid[3][5]
以此类推，我们可以将节点1到节点9的最短路径逐步分解为更小的子路径，直到不能再分解。
Floyd算法的动态规划五部曲总结
之前在讲解动态规划的时候，给出过动规五部曲：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
接下来还是用这五部讲解 Floyd。
1. 确定dp数组（dp table）以及下标的含义
在Floyd算法中，dp数组可以用grid[i][j][k]表示，含义是节点i到节点j，以集合[1...k]为中间节点的最短距离为m。
-
grid[i][j][k]：表示从节点i到节点j，经过节点1到节点k之间所有节点的最短路径。 -
k表示一个节点的集合，不是单独的一个节点。通过这样的定义，可以递归地计算出任意两个节点之间的最短路径。
2. 确定递推公式
Floyd算法的递推公式是通过分析两种情况得出的：
路径经过节点k：如果节点i到节点j的最短路径经过节点k，那么：
grid[i][j][k] = grid[i][k][k-1] + grid[k][j][k-1]
其中grid[i][k][k-1]和grid[k][j][k-1]分别表示节点i到节点k和节点k到节点j的最短路径，不经过节点k。路径不经过节点k：如果节点i到节点j的最短路径不经过节点k，那么：
grid[i][j][k] = grid[i][j][k-1]
因此，递推公式为：
grid[i][j][k] = \min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1])
3. dp数组如何初始化
grid数组是一个三维数组，那么我们初始化的数据在 i 与 j 构成的平层，如图：
image.png
红色的 底部一层是我们初始化好的数据
初始化dp数组时：
-
grid[i][j][0]表示从节点i到节点j的直接路径长度。如果节点i直接连向节点j（例如边p1 -> p2，权值为val），那么：
grid[p1][p2][0] = val
同样，因为图是双向的，所以：
grid[p2][p1][0] = val - 对于没有直接连通的节点，
grid[i][j][0]应初始化为一个很大的值（如10005，题目中最大是10004），表示无法直接连通。
代码：
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 节点数量
int m = scanner.nextInt(); // 边的数量
// 初始化三维数组 grid
int[][][] grid = new int[n + 1][n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
Arrays.fill(grid[i][j], 10005); // 设置初始值为10005
}
}
// 读取边的信息并初始化 grid 数组
for (int i = 0; i < m; i++) {
int p1 = scanner.nextInt();
int p2 = scanner.nextInt();
int val = scanner.nextInt();
grid[p1][p2][0] = val;
grid[p2][p1][0] = val; // 处理双向图
}
4. 确定遍历顺序
遍历顺序的确定是Floyd算法的关键：
从递推公式：grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])可以看出，我们需要三个for循环，分别遍历i，j 和k
而 k 依赖于 k - 1， i 和j 的到 并不依赖与 i - 1 或者 j - 1 等等。
那么这三个for的嵌套顺序应该是什么样的呢？
我们来看初始化，我们是把 k =0 的 i 和j 对应的数值都初始化了，这样才能去计算 k = 1 的时候 i 和 j 对应的数值。
这就好比是一个三维坐标，i 和j 是平层，而k 是 垂直向上 的。
遍历的顺序是从底向上 一层一层去遍历。
所以遍历k 的for循环一定是在最外面，这样才能一层一层去遍历。
image.png
-
k放在最外层：首先遍历
k（中间节点的集合），然后遍历i和j（起点和终点），确保在更新grid[i][j][k]时，已经计算出了grid[i][j][k-1]的值。for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { grid[i][j][k] = Math.min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]); } } } - 如果将
k放在内层，可能会导致不能正确利用之前的计算结果，导致错误的最短路径。
5. 举例推导dp数组
为了确保理解Floyd算法的递推过程，可以通过举例分析各个步骤：
- 先初始化
k=0的dp数组，然后逐层计算k=1, 2, ...时的最短路径。 - 通过打印出每层的
dp数组，可以直观地看到如何一步步接近最终的最短路径。
Java 版本的 Floyd 算法实现及空间优化
原始版本
import java.util.Scanner;
public class FloydWarshall {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 节点数量
int m = scanner.nextInt(); // 边的数量
int[][][] grid = new int[n + 1][n + 1][n + 1];
// 初始化三维数组 grid，所有元素设置为10005
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++) {
grid[i][j][k] = 10005;
}
}
}
// 读取边的信息并初始化 grid 数组
for (int i = 0; i < m; i++) {
int p1 = scanner.nextInt();
int p2 = scanner.nextInt();
int val = scanner.nextInt();
grid[p1][p2][0] = val;
grid[p2][p1][0] = val; // 双向图
}
// 开始 Floyd-Warshall 算法
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
grid[i][j][k] = Math.min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
}
}
}
// 输出结果
int z = scanner.nextInt();
while (z-- > 0) {
int start = scanner.nextInt();
int end = scanner.nextInt();
if (grid[start][end][n] == 10005) {
System.out.println(-1);
} else {
System.out.println(grid[start][end][n]);
}
}
}
}
空间优化版本
空间优化版本利用滚动数组和二维数组来减少空间消耗，将三维数组优化为二维数组：
import java.util.Scanner;
public class FloydWarshallOptimized {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 节点数量
int m = scanner.nextInt(); // 边的数量
int[][] grid = new int[n + 1][n + 1];
// 初始化二维数组 grid，所有元素设置为10005
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
grid[i][j] = 10005;
}
}
// 读取边的信息并初始化 grid 数组
for (int i = 0; i < m; i++) {
int p1 = scanner.nextInt();
int p2 = scanner.nextInt();
int val = scanner.nextInt();
grid[p1][p2] = val;
grid[p2][p1] = val; // 双向图
}
// 开始 Floyd-Warshall 算法
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 z = scanner.nextInt();
while (z-- > 0) {
int start = scanner.nextInt();
int end = scanner.nextInt();
if (grid[start][end] == 10005) {
System.out.println(-1);
} else {
System.out.println(grid[start][end]);
}
}
}
}
代码解释
-
初始化:
- 在原始版本中，使用三维数组
grid[i][j][k]来表示从节点i到节点j，经过前k个节点时的最短路径。 - 在优化版本中，使用二维数组
grid[i][j]来表示从节点i到节点j的最短路径。每次更新时，直接使用当前二维数组的状态，这样只需存储当前和前一个状态的最短路径。
- 在原始版本中，使用三维数组
-
Floyd-Warshall算法:
- 遍历
k，i，j三个维度，通过中间节点k来更新节点i到节点j的最短路径。
- 遍历
-
空间优化:
- 通过使用二维数组代替三维数组，将空间复杂度从
O(n^3)优化到O(n^2)。
- 通过使用二维数组代替三维数组，将空间复杂度从
复杂度分析
-
时间复杂度:
- 两个版本的时间复杂度都是
O(n^3)，因为需要遍历三个维度i，j，k。
- 两个版本的时间复杂度都是
-
空间复杂度:
- 原始版本的空间复杂度是
O(n^3)。 - 优化版本的空间复杂度是
O(n^2)，因为只使用了二维数组。
- 原始版本的空间复杂度是
A * 算法精讲 （A star算法）
一般 笔试或者 面试的时候，不会考察A， 都是会结合具体业务场景问 A算法，例如：地图导航，游戏开发 等等。
其实基础版的A* 并不难，所以大家不要畏惧，理解本篇内容，甚至独立写出代码，大家可以做到，加油
文章讲解
思路
我们看到这道题目的第一个想法就是广搜，这也是最经典的广搜类型题目。
import java.util.*;
public class KnightMoves {
static int[][] moves = new int[1001][1001];
static int[][] dir = {
{-2, -1}, {-2, 1}, {-1, 2}, {1, 2},
{2, 1}, {2, -1}, {1, -2}, {-1, -2}
};
public static void bfs(int a1, int a2, int b1, int b2) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{a1, a2});
while (!q.isEmpty()) {
int[] current = q.poll();
int m = current[0];
int n = current[1];
if (m == b1 && n == b2) {
break;
}
for (int i = 0; i < 8; i++) {
int mm = m + dir[i][0];
int nn = n + dir[i][1];
if (mm < 1 || mm > 1000 || nn < 1 || nn > 1000) {
continue;
}
if (moves[mm][nn] == 0) {
moves[mm][nn] = moves[m][n] + 1;
q.offer(new int[]{mm, nn});
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
while (n-- > 0) {
int a1 = scanner.nextInt();
int a2 = scanner.nextInt();
int b1 = scanner.nextInt();
int b2 = scanner.nextInt();
// 重置moves数组
for (int i = 0; i < 1001; i++) {
Arrays.fill(moves[i], 0);
}
bfs(a1, a2, b1, b2);
System.out.println(moves[b1][b2]);
}
scanner.close();
}
}
提交后会发现，超时了。
因为本题地图足够大，且 n 也有可能很大，导致有非常多的查询。
Astar
A算法是广度优先搜索（BFS）和Dijkstra算法的改良版，适用于在图上寻找最短路径的问题。A通过结合启发式函数，引导搜索过程更高效地找到目标节点。
1. 选择算法的场景
- 无权图（边的权值都是1）：使用BFS，代码简洁，效率较高。
- 有权图（边有不同的权值）：优先考虑Dijkstra算法。
- 目标导向搜索：A*算法适合有明确起点和终点的搜索，能有效减少不必要的遍历。
2. A*算法的核心：启发式函数
A算法的关键在于启发式函数*，它影响搜索过程中从容器（队列或优先队列）中取出节点的优先顺序。
BFS与A*的对比
- BFS：一层一层地遍历节点，无目的性，搜索过程是无方向的。
- A*：搜索过程中有方向性，基于启发式函数优先选择更有可能到达终点的路径，节省了大量不必要的遍历步骤。
3. 启发式函数的作用
启发式函数用于给每个节点赋予一个权值F，并按照F值来排序队列中的节点，决定搜索的方向。公式如下：
-
F = G + H
- G：从起点到当前节点的实际代价（路径长度）。
- H：当前节点到终点的估算代价（通常用距离计算）。
4. 距离计算方法
在网格状图中，常用的距离计算方法有三种：
-
曼哈顿距离：
d = abs(x1-x2) + abs(y1-y2) -
欧氏距离（欧拉距离）：
d = sqrt((x1-x2)^2 + (y1-y2)^2) -
切比雪夫距离：
d = max(abs(x1-x2), abs(y1-y2))
三种距离的详细讲解
在图算法（如A*算法）中，计算距离是确定启发式函数的重要部分。曼哈顿距离、欧氏距离和切比雪夫距离是最常用的三种距离计算方式，它们适用于不同的场景。以下是对这三种距离的详细讲解：
1. 曼哈顿距离（Manhattan Distance）
公式：d = abs(x1 - x2) + abs(y1 - y2)
-
概念：
- 曼哈顿距离是指在网格状的地图中，只能沿着水平或垂直方向移动的情况下，两个点之间的距离总和。
- 这种距离计算方式得名于曼哈顿的街道布局，在这种布局中，街道呈网格状，车辆只能沿着正北、正南、正东、正西方向移动。
-
适用场景：
- 当只能在网格上水平或垂直移动时，曼哈顿距离是最准确的。
- 例如：在棋盘游戏中，棋子只能水平或垂直移动。
-
举例：
- 假设有两个点A和B，A的坐标是(1, 2)，B的坐标是(4, 6)，那么它们之间的曼哈顿距离为：
[
d = abs(1 - 4) + abs(2 - 6) = 3 + 4 = 7
] - 这个值表示从A到B的最短路径需要7个单位长度的移动，如果只能沿着网格的水平和垂直方向移动。
- 假设有两个点A和B，A的坐标是(1, 2)，B的坐标是(4, 6)，那么它们之间的曼哈顿距离为：
2. 欧氏距离（Euclidean Distance）
公式：d = sqrt((x1 - x2)^2 + (y1 - y2)^2)
-
概念：
- 欧氏距离是平面直角坐标系中，两个点之间的直线距离。
- 它是使用勾股定理计算出来的，也被称为欧拉距离或直线距离。
-
适用场景：
- 当可以在任意方向上移动时，欧氏距离是最准确的。
- 例如：在平面中自由移动的机器人，或者需要测量点与点之间的直线距离时。
-
举例：
- 假设有两个点A和B，A的坐标是(1, 2)，B的坐标是(4, 6)，它们之间的欧氏距离为：
[
d = \sqrt{(1 - 4)^2 + (2 - 6)^2} = \sqrt{9 + 16} = \sqrt{25} = 5
] - 这个值表示从A到B的直线距离为5个单位长度，适合可以沿任意方向移动的情况。
- 假设有两个点A和B，A的坐标是(1, 2)，B的坐标是(4, 6)，它们之间的欧氏距离为：
3. 切比雪夫距离（Chebyshev Distance）
公式：d = max(abs(x1 - x2), abs(y1 - y2))
-
概念：
- 切比雪夫距离是指在允许沿着水平、垂直以及对角线方向移动的情况下，两个点之间的最大单一方向上的距离。
- 这种距离计算方式适用于可以沿对角线方向自由移动的场景。
-
适用场景：
- 当在网格上移动时，既可以沿水平或垂直方向移动，也可以沿对角线移动时，切比雪夫距离是最准确的。
- 例如：在国际象棋中，国王每次可以沿任意方向移动一个单位，适用切比雪夫距离。
-
举例：
- 假设有两个点A和B，A的坐标是(1, 2)，B的坐标是(4, 6)，它们之间的切比雪夫距离为：
[
d = \max(abs(1 - 4), abs(2 - 6)) = \max(3, 4) = 4
] - 这个值表示从A到B的最短路径需要4步，如果允许沿水平、垂直和对角线方向移动。
- 假设有两个点A和B，A的坐标是(1, 2)，B的坐标是(4, 6)，它们之间的切比雪夫距离为：
总结
- 曼哈顿距离：适用于只能沿水平或垂直方向移动的场景，计算简单，结果为移动步数的总和。
- 欧氏距离：适用于可以在任意方向上自由移动的场景，结果为两个点之间的直线距离。
- 切比雪夫距离：适用于可以沿水平、垂直以及对角线方向移动的场景，结果为两个点之间最大单一方向的距离。
5. A*算法的实现
在A*算法中，启发式函数引导搜索过程，可以通过优先级队列来实现：
-
优先级队列：根据节点的
F值进行排序，每次从队列中取出F值最小的节点进行扩展。
import java.util.PriorityQueue;
import java.util.Scanner;
class Knight implements Comparable<Knight> {
int x, y;
int g, h, f;
// 重载运算符，用于优先级队列的排序
@Override
public int compareTo(Knight k) {
return Integer.compare(this.f, k.f);
}
}
public class AStarKnight {
static int[][] moves = new int[1001][1001];
static int[][] dir = {
{-2, -1}, {-2, 1}, {-1, 2}, {1, 2},
{2, 1}, {2, -1}, {1, -2}, {-1, -2}
};
static int b1, b2;
static PriorityQueue<Knight> que = new PriorityQueue<>();
public static int heuristic(Knight k) { // 欧拉距离
return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); // 统一不开根号，这样可以提高精度
}
public static void astar(Knight k) {
que.offer(k);
while (!que.isEmpty()) {
Knight cur = que.poll();
if (cur.x == b1 && cur.y == b2)
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 || nextX > 1000 || nextY < 1 || nextY > 1000)
continue;
if (moves[nextX][nextY] == 0) {
moves[nextX][nextY] = moves[cur.x][cur.y] + 1;
Knight next = new Knight();
next.x = nextX;
next.y = nextY;
next.g = cur.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5
next.h = heuristic(next);
next.f = next.g + next.h;
que.offer(next);
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
while (n-- > 0) {
int a1 = scanner.nextInt();
int a2 = scanner.nextInt();
b1 = scanner.nextInt();
b2 = scanner.nextInt();
// 重置 moves 数组
for (int i = 0; i < 1001; i++) {
for (int j = 0; j < 1001; j++) {
moves[i][j] = 0;
}
}
Knight start = new Knight();
start.x = a1;
start.y = a2;
start.g = 0;
start.h = heuristic(start);
start.f = start.g + start.h;
astar(start);
que.clear(); // 清空队列
System.out.println(moves[b1][b2]);
}
scanner.close();
}
}
代码解释
-
Knight类：
- 定义了骑士的坐标
x和y，以及g（从起点到当前节点的路径消耗）、h（当前节点到终点的预估消耗）、f（总消耗，即g + h）。 - 实现了
Comparable<Knight>接口，以便在PriorityQueue中根据f值进行排序。
- 定义了骑士的坐标
-
AStarKnight类：
-
moves：二维数组，用于记录骑士到达每个位置的最短路径长度。 -
dir：存储骑士可以移动的8个方向。 -
b1和b2：目标位置的坐标。 -
que：优先级队列，用于按照f值对节点进行排序。
-
-
启发式函数：
-
heuristic(Knight k)：计算欧拉距离（启发式函数H），这里不开根号以提高精度。
-
-
A算法的实现*：
-
astar(Knight k)：使用A*算法从起点开始搜索最短路径，每次选择f值最小的节点进行扩展，直到找到终点。
-
-
main方法：
- 读取输入数据，初始化起点骑士的位置和其他参数，调用
astar方法进行搜索，最后输出到达终点的最短路径长度。
- 读取输入数据，初始化起点骑士的位置和其他参数，调用
你提到的关于坐标系的解释是正确的，涉及到的是二维数组的标准坐标系（行列表示法）与通常的笛卡尔坐标系之间的区别。这种区别确实在不同的应用场景中可能会导致混淆。让我为你澄清这两种坐标系在骑士移动问题中的具体应用，并解释它们如何一致或不同。
-
二维数组坐标系（行列表示法）
在二维数组（如图像处理、棋盘游戏等）中，通常采用的坐标系如下：
-
行（row）：表示
x轴，通常从上到下，x值递增。 -
列（column）：表示
y轴，通常从左到右，y值递增。
(0,0) (0,1) (0,2) ...
(1,0) (1,1) (1,2) ...
(2,0) (2,1) (2,2) ...
在这个系统中：
- 向右移动：
y增加 (y+1) - 向下移动：
x增加 (x+1) - 向上移动：
x减少 (x-1) - 向左移动：
y减少 (y-1)
在骑士的移动问题中，坐标系通常遵循二维数组的定义，即：
-
x表示行数，向下递增。 -
y表示列数，向右递增。
static int[][] dir = {
{-2, -1}, {-2, 1}, {-1, 2}, {1, 2},
{2, 1}, {2, -1}, {1, -2}, {-1, -2}
};
这些方向的含义如下：
-
{-2, -1}：向上移动2格，同时向左移动1格（x减少2，y减少1） -
{-2, 1}：向上移动2格，同时向右移动1格（x减少2，y增加1） -
{-1, 2}：向上移动1格，同时向右移动2格（x减少1，y增加2） -
{1, 2}：向下移动1格，同时向右移动2格（x增加1，y增加2） -
{2, 1}：向下移动2格，同时向右移动1格（x增加2，y增加1） -
{2, -1}：向下移动2格，同时向左移动1格（x增加2，y减少1） -
{1, -2}：向下移动1格，同时向左移动2格（x增加1，y减少2） -
{-1, -2}：向上移动1格，同时向左移动2格（x减少1，y减少2）
A* 算法的复杂度分析
时间复杂度：
- 不可量化：A*算法的时间复杂度难以精确量化，因为它高度依赖于启发式函数的设计。
-
最坏情况：在最坏情况下，A*算法可能退化为广度优先搜索（BFS），其时间复杂度为
O(n^2)，其中n为节点数量。 -
最佳情况：如果启发式函数非常有效，使得搜索路径直接从起点到终点，时间复杂度可以降到
O(d log d)，其中d为起点到终点的深度。 -
一般情况：通常，A*算法的时间复杂度介于最优和最坏情况之间，可以粗略地认为是
O(n log n)，其中n为节点数量。这是因为在搜索过程中，节点需要通过优先级队列排序，而队列操作的时间复杂度是O(log n)。
空间复杂度：
- A*算法的空间复杂度是
O(b^d)，其中d为起点到终点的深度，b是图中节点间的连接数量。在网格图中，每个节点通常有4个相邻节点，因此b通常为4。
扩展分析
-
启发式函数的选择：
- 启发式函数的设计直接影响A*算法的搜索路径和效率。不同的启发式函数，如曼哈顿距离和切比雪夫距离，可能在某些场景下导致次优路径。
- 例如在某些小型地图（如8x8棋盘）上，使用曼哈顿距离可能不会明显影响结果，但在较大或更复杂的地图上，不准确的启发式函数会影响路径质量。
-
启发式函数与效率的权衡：
- A*算法并不是严格的最短路径算法，其结果取决于启发式函数的设计。启发式函数需要在时间效率和路径准确度之间找到平衡。
- 在某些应用场景，如游戏开发中，A*算法的启发式函数可能设计为次优路径，以提高运行效率，而不一定追求最短路径。玩家通常接受接近最短路径的结果，而不会在意微小的偏差。
A* 算法的缺点
-
空间消耗：
- A*算法在搜索过程中会扩展大量节点并将它们存储在优先级队列中。即使这些节点可能不被访问，它们仍然占用空间，导致高内存消耗。
- 优化方案：IDA（Iterative Deepening A）算法是A的改进版，旨在解决A算法中空间消耗过大的问题。
-
多目标问题：
- A算法不擅长处理多个潜在目标的问题。如果需要在多个目标中找到最近的一个，A算法可能表现不佳。
- 替代方案：对于多个目标问题，可以考虑使用Dijkstra算法、BFS或Floyd算法，它们在这种场景下可能更合适。
最短路算法总结篇
最各个最短路算法有个全面的了解
文章讲解
算法选择的场景分析总结
-
单源最短路径，且边权为正：
- 优先选择：Dijkstra算法。
-
具体实现：
- 朴素版Dijkstra适用于图较稠密的情况。
- 堆优化版Dijkstra适用于图较稀疏的情况。
- 稠密度判断：稠密图和稀疏图的具体划分没有严格的量化标准，通常可以通过实验对比朴素版和堆优化版Dijkstra的性能来判断。
-
单源最短路径，边权可以为负：
- 优先选择：Bellman-Ford算法。
-
具体实现：
- Bellman-Ford适用于图较稠密的情况。
- SPFA（Shortest Path Faster Algorithm）适用于图较稀疏的情况。
- 一般推荐：通常情况下，优先使用SPFA，因为它在大部分情况下比Bellman-Ford更快。
-
存在负权回路或有限节点最短路径问题：
- 优先选择：Bellman-Ford算法。
- 理由：Bellman-Ford能够检测负权回路，并且代码实现相对简单，适合处理复杂的路径问题。
-
多源最短路径：
- 优先选择：Floyd-Warshall算法。
- 例外情况：如果源点非常少且边权为正，可以使用多次Dijkstra来求解，但这种情况较少见，多源问题通常直接适用于Floyd-Warshall算法。
-
A算法的应用场景*：
- 广泛使用：A*算法由于其高效性，广泛应用于实际工程中，例如游戏开发、地图导航、数据包路由等。
- 注意事项：A*算法的结果不一定是唯一的，可能会得到次短路径，因此在算法竞赛中较少使用，更多应用于实际工程需求中。
总结
- Dijkstra：用于单源正权图。
- Bellman-Ford和SPFA：用于单源负权图，尤其是Bellman-Ford适用于检测负权回路。
- Floyd-Warshall：用于多源最短路径问题。
- A算法*：适用于实际工程中的路径搜索需求，尤其是在需要高效搜索但不要求唯一最短路径的场景。
