代码随想录刷题记录-28 图论 (5)最短路径

一、dijkstra（朴素版）精讲

47. 参加科学大会

思路

本题就是求最短路，最短路是图论中的经典问题即：给出一个有向图，一个起点，一个终点，问起点到终点的最短路径。

接下来讲解最短路算法中的 dijkstra 算法。

dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。

需要注意两点：

dijkstra 算法可以同时求起点到所有节点的最短路径
权值不能为负数

dijkstra 算法同样是贪心的思路，不断寻找距离源点最近的没有访问过的节点。

这里给出 dijkstra三部曲：

第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新minDist数组）

大家此时已经会发现，这和prim算法怎么这么像呢。

我在prim算法讲解中也给出了三部曲。 prim 和 dijkstra 确实很像，思路也是类似的，这一点我在后面还会详细来讲。

在dijkstra算法中，同样有一个数组很重要，起名为：minDist。

minDist数组用来记录每一个节点距离源点的最小距离。

理解这一点很重要，也是理解 dijkstra 算法的核心所在。

先来画图看一下 dijkstra 的工作过程，以本题示例为例：（以下为朴素版dijkstra的思路）

（示例中节点编号是从1开始，所以为了让大家看的不晕，minDist数组下标我也从 1 开始计数，下标0 就不使用了，这样下标和节点标号就可以对应上了，避免大家搞混）

朴素版dijkstra

模拟过程

0、初始化

minDist数组数值初始化为int最大值。

这里在强点一下 minDist数组的含义：记录所有节点到源点的最短路径，那么初始化的时候就应该初始为最大值，这样才能在后续出现最短路径的时候及时更新。

（图中，max 表示默认值，节点0 不做处理，统一从下标1 开始计算，这样下标和节点数值统一，方便大家理解，避免搞混）

源点（节点1）到自己的距离为0，所以 minDist[1] = 0

此时所有节点都没有被访问过，所以 visited数组都为0

以下为dijkstra 三部曲

1、选源点到哪个节点近且该节点未被访问过

源点距离源点最近，距离为0，且未被访问。

2、该最近节点被标记访问过

标记源点访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

更新 minDist数组，即：源点（节点1）到节点2 和节点3的距离。

源点到节点2的最短距离为1，小于原minDist[2]的数值max，更新minDist[2] = 1
源点到节点3的最短距离为4，小于原minDist[3]的数值max，更新minDist[3] = 4

遍历更新minDist的点是当前访问节点的邻接点。

1、选源点到哪个节点近且该节点未被访问过

未访问过的节点中，源点到节点2距离最近，选节点2

2、该最近节点被标记访问过

节点2被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

更新 minDist数组，即：源点（节点1）到节点6 、节点3 和节点4的距离。

为什么更新这些节点呢？怎么不更新其他节点呢？

因为源点（节点1）通过已经计算过的节点（节点2）可以链接到的节点有节点3，节点4和节点6.

更新 minDist数组：

源点到节点6的最短距离为5，小于原minDist[6]的数值max，更新minDist[6] = 5
源点到节点3的最短距离为3，小于原minDist[3]的数值4，更新minDist[3] = 3
源点到节点4的最短距离为6，小于原minDist[4]的数值max，更新minDist[4] = 6

1、选源点到哪个节点近且该节点未被访问过

未访问过的节点中，源点距离哪些节点最近，怎么算的？

其实就是看 minDist数组里的数值，minDist 记录了源点到所有节点的最近距离，结合visited数组筛选出未访问的节点就好。

从上面的图，或者从minDist数组中，我们都能看出未访问过的节点中，源点（节点1）到节点3距离最近。

2、该最近节点被标记访问过

节点3被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点3的加入，那么源点可以有新的路径链接到节点4 所以更新minDist数组：

更新 minDist数组：

源点到节点4的最短距离为5，小于原minDist[4]的数值6，更新minDist[4] = 5

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，有节点4 和节点6，距离源点距离都是 5 （minDist[4] = 5，minDist[6] = 5），选哪个节点都可以。

2、该最近节点被标记访问过

节点4被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点4的加入，那么源点可以链接到节点5 所以更新minDist数组：

源点到节点5的最短距离为8，小于原minDist[5]的数值max，更新minDist[5] = 8

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，是节点6，距离源点距离是 5 （minDist[6] = 5）

2、该最近节点被标记访问过

节点6 被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点6的加入，那么源点可以链接到节点7 所以更新minDist数组：

源点到节点7的最短距离为14，小于原minDist[7]的数值max，更新minDist[7] = 14

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，是节点5，距离源点距离是 8 （minDist[5] = 8）

2、该最近节点被标记访问过

节点5 被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点5的加入，那么源点有新的路径可以链接到节点7 所以更新minDist数组：

源点到节点7的最短距离为12，小于原minDist[7]的数值14，更新minDist[7] = 12

1、选源点到哪个节点近且该节点未被访问过

距离源点最近且没有被访问过的节点，是节点7（终点），距离源点距离是 12 （minDist[7] = 12）

2、该最近节点被标记访问过

节点7 被标记访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

节点7加入，但节点7到节点7的距离为0，所以不用更新minDist数组

最后我们要求起点（节点1）到终点（节点7）的距离。

再来回顾一下minDist数组的含义：记录每一个节点距离源点的最小距离。

那么起到（节点1）到终点（节点7）的最短距离就是 minDist[7] ，按上面举例讲解来说，minDist[7] = 12，节点1 到节点7的最短路径为 12。

路径如图：

在上面的讲解中，每一步我都是按照 dijkstra 三部曲来讲解的，理解了这三部曲，代码也就好懂的。

代码如下：

import java.util.*;
import java.util.List;


public class Main {

    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];
        for(int[] array : grid){
            Arrays.fill(array,Integer.MAX_VALUE);
        }
        //读入图
        for(int i = 0 ; i < m ; i++){
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            int value = scanner.nextInt();
            grid[from][to] = value;
        }
        int[] minDist = new int[n+1];
        boolean[] visited = new boolean[n+1];
        int source = 1;
        int destination = n;
        visited[source] = true;
        Arrays.fill(minDist,Integer.MAX_VALUE);
        minDist[source] = 0;
        //dijkstra算法大循环，遍历所有节点
        for(int i = 0 ; i < n ; i++){
            int cur = 1;
            int minValue = Integer.MAX_VALUE;
            //找到当前非访问过的节点中，最近的节点。
            for(int j = 1 ; j <= n  ; j++){
                if(visited[j]) continue;
                if(minDist[j] < minValue){
                    minValue = minDist[j];
                    cur = j;

                }
            }
            visited[cur] = true;
            //针对该节点的邻接点 中的 非访问过的 节点 到 source的距离进行更新
            for(int j = 1 ; j <= n  ; j++){
                if(!visited[j] && grid[cur][j] != Integer.MAX_VALUE && minDist[cur] + grid[cur][j] < minDist[j]){
                    minDist[j] = minDist[cur] +grid[cur][j];
                }
            }
        }

        if(minDist[destination] != Integer.MAX_VALUE){
            System.out.println(minDist[destination]);
        }else{
            System.out.println("-1");
        }


    }

}

如何求路径

如果要记录路径的话，也是用一维parent数组来记录，类似于prim算法，在更新minDist的时候记录即可。

import java.util.*;
import java.util.List;


public class Main {

    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];
        int[] parent = new int[n+1]; //用以记录路径
        Arrays.fill(parent,-1);
        for(int[] array : grid){
            Arrays.fill(array,Integer.MAX_VALUE);
        }
        //读入图
        for(int i = 0 ; i < m ; i++){
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            int value = scanner.nextInt();
            grid[from][to] = value;
        }
        int[] minDist = new int[n+1];
        boolean[] visited = new boolean[n+1];
        int source = 1;
        int destination = n;
        visited[source] = true;
        Arrays.fill(minDist,Integer.MAX_VALUE);
        minDist[source] = 0;
        //dijkstra算法大循环，遍历所有节点
        for(int i = 0 ; i < n ; i++){
            int cur = 1;
            int minValue = Integer.MAX_VALUE;
            //找到当前非访问过的节点中，最近的节点。
            for(int j = 1 ; j <= n  ; j++){
                if(visited[j]) continue;
                if(minDist[j] < minValue){
                    minValue = minDist[j];
                    cur = j;

                }
            }
            visited[cur] = true;
            //针对该节点的邻接点 中的 非访问过的 节点 到 source的距离进行更新
            for(int j = 1 ; j <= n  ; j++){
                if(!visited[j] && grid[cur][j] != Integer.MAX_VALUE && minDist[cur] + grid[cur][j] < minDist[j]){
                    minDist[j] = minDist[cur] +grid[cur][j];
                    parent[j] = cur;//记录路径
                }
            }
        }

        if(minDist[destination] != Integer.MAX_VALUE){
            System.out.println(minDist[destination]);
        }else{
            System.out.println("-1");
        }


    }

}

debug方法

在每一次选择后输出日志，输出当前选择的节点和minDist数组，看和自己的预期是否相同。

出现负数

如果图中边的权值为负数，dijkstra 还合适吗？

看一下这个图：（有负权值）

节点1 到节点5 的最短路径应该是节点1 -> 节点2 -> 节点3 -> 节点4 -> 节点5

那我们来看dijkstra 求解的路径是什么样的，继续dijkstra 三部曲来模拟：（dijkstra模拟过程上面已经详细讲过，以下只模拟重要过程，例如如何初始化就省略讲解了）

初始化：

1、选源点到哪个节点近且该节点未被访问过

源点距离源点最近，距离为0，且未被访问。

2、该最近节点被标记访问过

标记源点访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

更新 minDist数组，即：源点（节点1）到节点2 和节点3的距离。

源点到节点2的最短距离为100，小于原minDist[2]的数值max，更新minDist[2] = 100
源点到节点3的最短距离为1，小于原minDist[3]的数值max，更新minDist[4] = 1

1、选源点到哪个节点近且该节点未被访问过

源点距离节点3最近，距离为1，且未被访问。

2、该最近节点被标记访问过

标记节点3访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点3的加入，那么源点可以有新的路径链接到节点4 所以更新minDist数组：

源点到节点4的最短距离为2，小于原minDist[4]的数值max，更新minDist[4] = 2

1、选源点到哪个节点近且该节点未被访问过

源点距离节点4最近，距离为2，且未被访问。

2、该最近节点被标记访问过

标记节点4访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

由于节点4的加入，那么源点可以有新的路径链接到节点5 所以更新minDist数组：

源点到节点5的最短距离为3，小于原minDist[5]的数值max，更新minDist[5] = 5

1、选源点到哪个节点近且该节点未被访问过

源点距离节点5最近，距离为3，且未被访问。

2、该最近节点被标记访问过

标记节点5访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

节点5的加入，而节点5 没有链接其他节点，所以不用更新minDist数组，仅标记节点5被访问过了

1、选源点到哪个节点近且该节点未被访问过

源点距离节点2最近，距离为100，且未被访问。

2、该最近节点被标记访问过

标记节点2访问过

3、更新非访问节点到源点的距离（即更新minDist数组），如图：

至此dijkstra的模拟过程就结束了，根据最后的minDist数组，我们求节点1 到节点5 的最短路径的权值总和为 3，路径：节点1 -> 节点3 -> 节点4 -> 节点5

通过以上的过程模拟，我们可以发现之所以没有走有负权值的最短路径是因为在访问节点 2 的时候，节点 3 已经访问过了，就不会再更新了。

那有录友可能会想：我可以改代码逻辑啊，访问过的节点，也让它继续访问不就好了？

那么访问过的节点还能继续访问会不会有死循环的出现呢？控制逻辑不让其死循环？那特殊情况自己能都想清楚吗？（可以试试，实践出真知）

对于负权值的出现，大家可以针对某一个场景不断去修改 dijkstra 的代码，但最终会发现只是拆了东墙补西墙，对dijkstra的补充逻辑只能满足某特定场景最短路求解。

对于求解带有负权值的最短路问题，可以使用 Bellman-Ford 算法，后序会详细讲解。

dijkstra与prim算法的区别

大家可以发现 dijkstra的代码看上去怎么和 prim算法这么像呢。

其实代码大体不差，唯一区别在三部曲中的第三步：更新minDist数组

因为prim是求非访问节点到最小生成树的最小距离，而 dijkstra是求非访问节点到源点的最小距离。

prim 更新 minDist数组的写法：

for (int j = 1; j <= v; j++) {
    if (!isInTree[j] && grid[cur][j] < minDist[j]) {
        minDist[j] = grid[cur][j];
    }
}

因为 minDist表示节点到最小生成树的最小距离，所以新节点cur的加入，只需要使用 grid[cur][j] ，grid[cur][j] 就表示 cur 加入生成树后，生成树到节点j 的距离。

dijkstra 更新 minDist数组的写法：

for (int v = 1; v <= n; v++) {
    if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
        minDist[v] = minDist[cur] + grid[cur][v];
    }
}

因为 minDist表示节点到源点的最小距离，所以新节点 cur 的加入，需要使用源点到cur的距离（minDist[cur]） + cur 到节点 v 的距离（grid[cur][v]），才是源点到节点v的距离。

此时大家可能不禁要想 prim算法可以有负权值吗？

当然可以，prim算法只需要将节点以最小权值和链接在一起，不涉及到单一路径。

二、dijkstra（堆优化版）精讲

在节点数很大的情况下（稀疏图），考虑维护边集合来实现dijkstra算法。

使用邻接表来存储图。

同时，因为每一步要选择未访问节点中minDist最小的节点，考虑使用堆来进行优化。

堆优化细节

其实思路依然是 dijkstra 三部曲：

第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新minDist数组）

只不过之前是通过遍历节点来遍历边，通过两层for循环来寻找距离源点最近节点。这次我们直接遍历边，且通过堆来对边进行排序，达到直接选择距离源点最近节点。

先来看一下针对这三部曲，如果用堆来优化。

那么三部曲中的第一步（选源点到哪个节点近且该节点未被访问过），我们如何选？

我们要选择距离源点近的节点（即：该边的权值最小），所以我们需要一个小顶堆来帮我们对边的权值排序，每次从小顶堆堆顶取边就是权值最小的边。

C++定义小顶堆，可以用优先级队列实现，代码如下：

// 小顶堆
class mycomparison {
public:
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};
// 优先队列中存放 pair<节点编号，源点到该节点的权值> 
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;

（pair<int, int>中第二个int 为什么要存源点到该节点的权值，因为这个小顶堆需要按照权值来排序）

有了小顶堆自动对边的权值排序，那我们只需要直接从堆里取堆顶元素（小顶堆中，最小的权值在上面），就可以取到离源点最近的节点了（未访问过的节点，不会加到堆里进行排序）

所以三部曲中的第一步，我们不用 for循环去遍历，直接取堆顶元素：

// pair<节点编号，源点到该节点的权值>
pair<int, int> cur = pq.top(); pq.pop();

第二步（该最近节点被标记访问过）这个就是将节点做访问标记，和朴素dijkstra 一样，代码如下：

// 2. 第二步，该最近节点被标记访问过
visited[cur.first] = true;

（cur.first 是指取 pair<int, int> 里的第一个int，即节点编号）

第三步（更新非访问节点到源点的距离），这里的思路也是和朴素dijkstra一样的。

但很多录友对这里是最懵的，主要是因为两点：

没有理解透彻 dijkstra 的思路
没有理解邻接表的表达方式

我们来回顾一下朴素dijkstra 在这一步的代码和思路（如果没看过我讲解的朴素版dijkstra，这里会看不懂）


// 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）
for (int v = 1; v <= n; v++) {
    if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
        minDist[v] = minDist[cur] + grid[cur][v];
    }
}

其中 for循环是用来做什么的？是为了找到节点cur 链接指向了哪些节点，因为使用邻接矩阵的表达方式所以把所有节点遍历一遍。

而在邻接表中，我们可以以相对高效的方式知道一个节点链接指向哪些节点。

再回顾一下邻接表的构造（数组 + 链表）：

假如加入的cur 是节点 2，那么 grid[2] 表示的就是图中第二行链表。（grid数组的构造我们在上面「图的存储」中讲过）

所以在邻接表中，我们要获取节点cur 链接指向哪些节点，就是遍历 grid[cur节点编号] 这个链表。

这个遍历方式，C++代码如下：

for (Edge edge : grid[cur.first])

cur.first 就是cur节点编号，参考上面pair的定义： pair<节点编号，源点到该节点的权值>

接下来就是更新非访问节点到源点的距离，代码实现和朴素dijkstra 是一样的，代码如下：

// 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点，cur指向的节点为 edge
    // cur指向的节点edge.to，这条边的权值为 edge.val
    if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist
        minDist[edge.to] = minDist[cur.first] + edge.val;
        pq.push(pair<int, int>(edge.to, minDist[edge.to]));
    }
}

确定该节点没有被访问过，!visited[edge.to] ，目前源点到cur.first的最短距离（minDist） + cur.first 到 edge.to 的距离（edge.val）是否小于 minDist已经记录的源点到 edge.to 的距离（minDist[edge.to]）

如果是的话，就开始更新操作。

即：

if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist
    minDist[edge.to] = minDist[cur.first] + edge.val;
    pq.push(pair<int, int>(edge.to, minDist[edge.to])); // 由于cur节点的加入，而新链接的边，加入到优先级队里中
}

同时，由于cur节点的加入，源点又有可以新链接到的边，将这些边加入到优先级队里中。

以上代码思路和朴素版dijkstra 是一样一样的，主要区别是两点：

邻接表的表示方式不同
使用优先级队列（小顶堆）来对新链接的边排序

代码实现

堆优化dijkstra完整代码如下：

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std; 
// 小顶堆
class mycomparison {
public:
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};
// 定义一个结构体来表示带权重的边
struct Edge {
    int to;  // 邻接顶点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<list<Edge>> grid(n + 1);

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val; 
        // p1 指向 p2，权值为 val
        grid[p1].push_back(Edge(p2, val));

    }

    int start = 1;  // 起点
    int end = n;    // 终点

    // 存储从源点到每个节点的最短距离
    std::vector<int> minDist(n + 1, INT_MAX);

    // 记录顶点是否被访问过
    std::vector<bool> visited(n + 1, false); 
    
    // 优先队列中存放 pair<节点，源点到该节点的权值>
    priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;


    // 初始化队列，源点到源点的距离为0，所以初始为0
    pq.push(pair<int, int>(start, 0)); 
    
    minDist[start] = 0;  // 起始点到自身的距离为0

    while (!pq.empty()) {
        // 1. 第一步，选源点到哪个节点近且该节点未被访问过 （通过优先级队列来实现）
        // <节点， 源点到该节点的距离>
        pair<int, int> cur = pq.top(); pq.pop();

        if (visited[cur.first]) continue;

        // 2. 第二步，该最近节点被标记访问过
        visited[cur.first] = true;

        // 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
        for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点，cur指向的节点为 edge
            // cur指向的节点edge.to，这条边的权值为 edge.val
            if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist
                minDist[edge.to] = minDist[cur.first] + edge.val;
                pq.push(pair<int, int>(edge.to, minDist[edge.to]));
            }
        }

    }

    if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点
    else cout << minDist[end] << endl; // 到达终点最短路径
}

时间复杂度：O(ElogE) E 为边的数量
空间复杂度：O(N + E) N 为节点的数量

堆优化的时间复杂度只和边的数量有关和节点数无关，在优先级队列中放的也是边。

以上代码中，while (!pq.empty()) 里套了 for (Edge edge : grid[cur.first])

for 里遍历的是当前节点 cur 所连接边。

那当前节点cur 所连接的边也是不固定的，这就让大家分不清，这时间复杂度究竟是多少？

其实 for (Edge edge : grid[cur.first]) 里最终的数据走向是给队列里添加边。

那么跳出局部代码，整个队列一定是所有边添加了一次，同时也弹出了一次。

所以边添加一次时间复杂度是 O(E)， while (!pq.empty()) 里每次都要弹出一个边来进行操作，在优先级队列（小顶堆）中弹出一个元素的时间复杂度是 O(logE) ，这是堆排序的时间复杂度。

（当然小顶堆里是添加元素的时候排序，还是取数元素的时候排序，这个无所谓，时间复杂度都是O(E)，总之是一定要排序的，而小顶堆里也不会滞留元素，有多少元素添加一定就有多少元素弹出）

所以该算法整体时间复杂度为 O（ElogE)

网上的不少分析会把 n （节点的数量）算进来，这个分析是有问题的，举一个极端例子，在n 为 10000，且是有一条边的图里，以上代码，大家感觉执行了多少次？

while (!pq.empty()) 中的 pq 存的是边，其实只执行了一次。

所以该算法时间复杂度和节点没有关系。

至于空间复杂度，邻接表是数组 + 链表数组的空间是 N ，有E条边就申请对应多少个链表节点，所以是复杂度是 N + E

Java实现如下：


import java.util.*;
import java.util.List;


public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if(n == 1){
            System.out.println(0);
            return ;
        }
        int m = scanner.nextInt();
        //邻接表存储表
        List<List<Edge>> grid = new ArrayList<>(n+1);
        for(int i = 0 ; i <= n ; i++){
            grid.add(new ArrayList<>());
        }
        //读入表
        for(int i = 0 ; i < m ; i++){
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            int value = scanner.nextInt();
            grid.get(from).add(new Edge(to,value));
        }
        //构建优先队列维护边集合
        PriorityQueue<Edge> pq = new PriorityQueue<>(new MyComparision());
        boolean[] visited = new boolean[n+1];
        int[] minDist = new int[n+1];
        Arrays.fill(minDist,Integer.MAX_VALUE);
        //初始化
        int start = 1;
        int destination = n;
        minDist[start] = 0;
        pq.add(new Edge(start,0));
        //dijkstra算法
        while(!pq.isEmpty()){
            //访问距离源点最小的未访问过的节点
            Edge edge = pq.poll();
            if(visited[edge.to]) continue;
            visited[edge.to] = true;
            //更新当前访问节点的 未访问过的邻接点的 minDist
            for(Edge e : grid.get(edge.to)){
                if(visited[e.to] == false && minDist[edge.to] + e.value < minDist[e.to]){
                    minDist[e.to] = minDist[edge.to] + e.value;
                    pq.add(new Edge(e.to,minDist[e.to]));//pq中加入更新过的节点及其对应的与源点的距离。
                    //这里不用作删除操作，因为取的一定是权重最小的那一个，并且访问过之后由于visited数组存在，不会再次访问
                }
            }
        }
        if(minDist[destination] == Integer.MAX_VALUE){
            System.out.println("-1");
        }else{
            System.out.println(minDist[destination]);
        }
    }

}

class Edge{
    int to;
    int value;
    Edge(int to , int value){
        this.to = to;
        this.value = value;
    }

}

class MyComparision implements Comparator<Edge>{
    @Override
    public int compare(Edge o1, Edge o2) {
        return Integer.compare(o1.value,o2.value);
    }
}

也可以像C++里一样，定义一个Pair类使用泛型，PriorityQueue里维护Pair：


import java.util.*;

class Edge {
    int to;  // 邻接顶点
    int val; // 边的权重

    Edge(int to, int val) {
        this.to = to;
        this.val = val;
    }
}

class MyComparison implements Comparator<Pair<Integer, Integer>> {
    @Override
    public int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs) {
        return Integer.compare(lhs.second, rhs.second);
    }
}

class Pair<U, V> {
    public final U first;
    public final V second;

    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        List<List<Edge>> grid = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            grid.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int p1 = scanner.nextInt();
            int p2 = scanner.nextInt();
            int val = scanner.nextInt();
            grid.get(p1).add(new Edge(p2, val));
        }

        int start = 1;  // 起点
        int end = n;    // 终点

        // 存储从源点到每个节点的最短距离
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);

        // 记录顶点是否被访问过
        boolean[] visited = new boolean[n + 1];

        // 优先队列中存放 Pair<节点，源点到该节点的权值>
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(new MyComparison());

        // 初始化队列，源点到源点的距离为0，所以初始为0
        pq.add(new Pair<>(start, 0));

        minDist[start] = 0;  // 起始点到自身的距离为0

        while (!pq.isEmpty()) {
            // 1. 第一步，选源点到哪个节点近且该节点未被访问过（通过优先级队列来实现）
            // <节点， 源点到该节点的距离>
            Pair<Integer, Integer> cur = pq.poll();

            if (visited[cur.first]) continue;

            // 2. 第二步，该最近节点被标记访问过
            visited[cur.first] = true;

            // 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
            for (Edge edge : grid.get(cur.first)) { // 遍历 cur指向的节点，cur指向的节点为 edge
                // cur指向的节点edge.to，这条边的权值为 edge.val
                if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist
                    minDist[edge.to] = minDist[cur.first] + edge.val;
                    pq.add(new Pair<>(edge.to, minDist[edge.to]));
                }
            }
        }

        if (minDist[end] == Integer.MAX_VALUE) {
            System.out.println(-1); // 不能到达终点
        } else {
            System.out.println(minDist[end]); // 到达终点最短路径
        }
    }
}

拓展

当然也有录友可能想堆优化dijkstra 中我为什么一定要用邻接表呢，我就用邻接矩阵行不行？

也行的。

但正是因为稀疏图，所以我们使用堆优化的思路，如果我们还用邻接矩阵去表达这个图的话，就是 一个高效的算法使用了低效的数据结构，那么整体算法效率依然是低的。

总结

在学习一种优化思路的时候，首先就要知道为什么要优化，遇到了什么问题。

正如我在开篇就给大家交代清楚堆优化方式的背景。

堆优化的整体思路和朴素版是大体一样的，区别是堆优化从边的角度出发且利用堆来排序。

三、Bellman_ford 算法精讲

本题依然是单源最短路问题，求从节点1 到节点n 的最小费用。 但本题不同之处在于边的权值是有负数了。

Bellman_ford算法可以解决图中有负权值的求单源最短路问题（不能解决有负环的问题）。

Bellman_ford算法的核心思想是对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。

什么叫做松弛

《算法四》里面把这个操作叫做 “放松”，英文版里叫做 “relax the edge”

所以大家翻译过来，就是 “放松” 或者 “松弛” 。

但《算法四》没有具体去讲这个 “放松” 究竟是个啥？网上很多题解也没有讲题解里的 “松弛这条边，松弛所有边”等等里面的 “松弛” 究竟是什么意思？

这里我给大家举一个例子，每条边有起点、终点和边的权值。例如一条边，节点A 到节点B 权值为value，如图：

minDist[B] 表示到达B节点最小权值，minDist[B] 有哪些状态可以推出来？

状态一： minDist[A] + value 可以推出 minDist[B] 状态二： minDist[B]本身就有权值（可能是其他边链接的节点B 例如节点C，以至于 minDist[B]记录了其他边到minDist[B]的权值）

minDist[B] 应为如何取舍。

本题我们要求最小权值，那么这两个状态我们就取最小的

if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value

也就是说，如果通过 A 到 B 这条边可以获得更短的到达B节点的路径，即如果 minDist[B] > minDist[A] + value，那么我们就更新 minDist[B] = minDist[A] + value ，这个过程就叫做 “松弛” 。

以上讲了这么多，其实都是围绕以下这句代码展开：

if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value

这句代码就是 Bellman_ford算法的核心操作。

以上代码也可以这么写：minDist[B] = min(minDist[A] + value, minDist[B])

如果大家看过代码随想录的动态规划章节，会发现无论是背包问题还是子序列问题，这段代码（递推公式）出现频率非常高的。

其实 Bellman_ford算法也是采用了动态规划的思想，即：将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解。

即松弛操作就是Bellman_ford算法里进行动态规划中的一个单步操作，这个单步操作取当前遍历到的元素在当前状态下最优的minDist.

那么为什么是 n - 1次松弛呢？

这里要模拟一遍 Bellman_ford 的算法才行，接下来看对所有边松弛 n - 1 次的操作是什么样的。

依然使用minDist数组来表达起点到各个节点的最短距离，例如minDist[3] = 5 表示起点到达节点3 的最小距离为5

模拟过程

初始化过程。

起点为节点1，起点到起点的距离为0，所以 minDist[1] 初始化为0

如图：

其他节点对应的minDist初始化为max，因为我们要求最小距离，那么还没有计算过的节点默认是一个最大数，这样才能更新最小距离。

对所有边进行第一次松弛：（什么是松弛，在上面我已经详细讲过）

以示例给出的所有边为例：

接下来我们来松弛一遍所有的边。

边：节点5 -> 节点6，权值为-2 ，minDist[5] 还是默认数值max，所以不能基于节点5 去更新节点6，如图：

（在复习一下，minDist[5] 表示起点到节点5的最短距离）

边：节点1 -> 节点2，权值为1 ，minDist[2] > minDist[1] + 1 ，更新 minDist[2] = minDist[1] + 1 = 0 + 1 = 1 ，如图：

边：节点5 -> 节点3，权值为1 ，minDist[5] 还是默认数值max，所以不能基于节点5去更新节点3 如图：

边：节点2 -> 节点5，权值为2 ，minDist[5] > minDist[2] + 2 （经过上面的计算minDist[2]已经不是默认值，而是 1），更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 ，如图：

边：节点2 -> 节点4，权值为-3 ，minDist[4] > minDist[2] + (-3)，更新 minDist[4] = minDist[2] + (-3) = 1 + (-3) = -2 ，如图：

边：节点4 -> 节点6，权值为4 ，minDist[6] > minDist[4] + 4，更新 minDist[6] = minDist[4] + 4 = -2 + 4 = 2

边：节点1 -> 节点3，权值为5 ，minDist[3] > minDist[1] + 5，更新 minDist[3] = minDist[1] + 5 = 0 + 5 = 5 ，如图：

以上是对所有边进行一次松弛之后的结果。

那么需要对所有边松弛几次才能得到起点（节点1）到终点（节点6）的最短距离呢？

对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离。

上面的距离中，我们得到里起点达到与起点一条边相邻的节点2 和节点3 的最短距离，分别是 minDist[2] 和 minDist[3]

这里有录友疑惑了 minDist[3] = 5，分明不是起点到达节点3 的最短距离，节点1 -> 节点2 -> 节点5 -> 节点3 这条路线距离才是4。

注意我上面讲的是 对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离，这里说的是一条边相连的节点。

与起点（节点1）一条边相邻的节点，到达节点2 最短距离是 1，到达节点3 最短距离是5。

而节点1 -> 节点2 -> 节点5 -> 节点3 这条路线是与起点三条边相连的路线了。

所以对所有边松弛一次能得到与起点一条边相连的节点最短距离。

那对所有边松弛两次可以得到与起点两条边相连的节点的最短距离。

那对所有边松弛三次可以得到与起点三条边相连的节点的最短距离，这个时候，我们就能得到到达节点3真正的最短距离，也就是节点1 -> 节点2 -> 节点5 -> 节点3 这条路线。

那么再回归刚刚的问题，需要对所有边松弛几次才能得到起点（节点1）到终点（节点6）的最短距离呢？

节点数量为n，那么起点到终点，最多是 n-1 条边相连。

那么无论图是什么样的，边是什么样的顺序，我们对所有边松弛 n-1 次就一定能得到起点到达终点的最短距离。

其实也同时计算出了，起点到达所有节点的最短距离，因为所有节点与起点连接的边数最多也就是 n-1 条边。

截止到这里，Bellman_ford 的核心算法思路，大家就了解的差不多了。

共有两个关键点。

“松弛”究竟是个啥？
为什么要对所有边松弛 n - 1 次（n为节点个数）？

那么Bellman_ford的解题解题过程其实就是对所有边松弛 n-1 次，然后得出得到终点的最短路径。

Java实现如下：

import java.util.*;
import java.util.List;


public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<Edge> edges = new ArrayList<>();
        for(int i = 0 ; i < m ; i++){
            edges.add(new Edge(scanner.nextInt(),scanner.nextInt(),scanner.nextInt()));
        }
        //初始化
        int start = 1;
        int end = n;
        int[] minDist = new int[n+1];
        Arrays.fill(minDist,Integer.MAX_VALUE);
        minDist[start] = 0;
        for(int i = 0 ; i < n-1 ; i++){
            //对所有的边进行n-1次松弛操作
            for(Edge edge : edges){
                if(minDist[edge.from] != Integer.MAX_VALUE && minDist[edge.from] + edge.value < minDist[edge.to]){
                    minDist[edge.to] = minDist[edge.from] + edge.value;
                }
            }
        }
        if(minDist[end] == Integer.MAX_VALUE){
            System.out.println("unconnected");
        }else{
            System.out.println(minDist[end]);
        }
    }

}

class Edge{
    int from;
    int to;
    int value;
    Edge(int from, int to , int value){
        this.from = from;
        this.to = to;
        this.value = value;
    }

}

总结

Bellman_ford 是可以计算负权值的单源最短路算法。

其算法核心思路是对所有边进行 n-1 次松弛。

弄清楚什么是松弛？为什么要 n-1 次？对理解Bellman_ford 非常重要。

四、Bellman_ford 队列优化算法（又名SPFA）

94. 城市间货物运输 I

可以发现 Bellman_ford 算法每次松弛都是对所有边进行松弛。

但真正有效的松弛，是基于已经计算过的节点在做的松弛。

给大家举一个例子：

本图中，对所有边进行松弛，真正有效的松弛，只有松弛边（节点1->节点2）和边（节点1->节点3）。

而松弛边（节点4->节点6），边（节点5->节点3）等等都是无效的操作，因为节点4 和节点 5 都是没有被计算过的节点。

所以 Bellman_ford 算法每次都是对所有边进行松弛，其实是多做了一些无用功。

只需要对上一次松弛的时候更新过的节点作为出发节点所连接的边进行松弛就够了。（对上一轮更新结点的出发边做松弛）

基于以上思路，如何记录上次松弛的时候更新过的节点呢？

用队列来记录。（其实用栈也行，对元素顺序没有要求）

模拟过程

接下来来举例这个队列是如何工作的。

以示例给出的所有边为例：

我们依然使用minDist数组来表达起点到各个节点的最短距离，例如minDist[3] = 5 表示起点到达节点3 的最小距离为5

初始化，起点为节点1，起点到起点的最短距离为0，所以minDist[1] 为 0。将节点1 加入队列（下次松弛从节点1开始）

从队列里取出节点1，松弛节点1 作为出发点连接的边（节点1 -> 节点2）和边（节点1 -> 节点3）

边：节点1 -> 节点2，权值为1 ，minDist[2] > minDist[1] + 1 ，更新 minDist[2] = minDist[1] + 1 = 0 + 1 = 1 。

边：节点1 -> 节点3，权值为5 ，minDist[3] > minDist[1] + 5，更新 minDist[3] = minDist[1] + 5 = 0 + 5 = 5。

将节点2、节点3 加入队列，如图：

从队列里取出节点2，松弛节点2 作为出发点连接的边（节点2 -> 节点4）和边（节点2 -> 节点5）

边：节点2 -> 节点4，权值为1 ，minDist[4] > minDist[2] + (-3) ，更新 minDist[4] = minDist[2] + (-3) = 1 + (-3) = -2 。

边：节点2 -> 节点5，权值为2 ，minDist[5] > minDist[2] + 2 ，更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 。

将节点4，节点5 加入队列，如图：

从队列里出去节点3，松弛节点3 作为出发点连接的边。

因为没有从节点3作为出发点的边，所以这里就从队列里取出节点3就好，不用做其他操作，如图：

从队列中取出节点4，松弛节点4作为出发点连接的边（节点4 -> 节点6）

边：节点4 -> 节点6，权值为4 ，minDist[6] > minDist[4] + 4，更新 minDist[6] = minDist[4] + 4 = -2 + 4 = 2 。

将节点6加入队列

如图：

从队列中取出节点5，松弛节点5作为出发点连接的边（节点5 -> 节点3），边（节点5 -> 节点6）

边：节点5 -> 节点3，权值为1 ，minDist[3] > minDist[5] + 1 ，更新 minDist[3] = minDist[5] + 1 = 3 + 1 = 4

边：节点5 -> 节点6，权值为-2 ，minDist[6] > minDist[5] + (-2) ，更新 minDist[6] = minDist[5] + (-2) = 3 - 2 = 1

如图，将节点3加入队列，因为节点6已经在队列里，所以不用重复添加

所以我们在加入队列的过程可以有一个优化，用visited数组记录已经在队列里的元素，已经在队列的元素不用重复加入

从队列中取出节点6，松弛节点6 作为出发点连接的边。

节点6作为终点，没有可以出发的边。

同理从队列中取出节点3，也没有可以出发的边

所以直接从队列中取出，如图：

这样我们就完成了基于队列优化的bellman_ford的算法模拟过程。

大家可以发现基于队列优化的算法，要比bellman_ford 算法减少很多无用的松弛情况，特别是对于边数众多的大图优化效果明显。

Java代码如下：

import java.util.*;
import java.util.List;


public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<List<Edge>> edges = new ArrayList<>(n+1);
        for(int i = 0 ; i <= n; i++){
            edges.add(new ArrayList<>());
        }
        for(int i = 0 ; i < m ; i++){
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            int value = scanner.nextInt();
            edges.get(from).add(new Edge(from,to,value));
        }
        boolean[] visited = new boolean[n+1];
        int[] minDist = new int[n+1];
        Arrays.fill(minDist,Integer.MAX_VALUE);
        int start = 1;
        int end = n;
        minDist[start] = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        visited[start] = true;
        //进行松弛操作
        while(!queue.isEmpty()){
            int node = queue.remove();
            visited[node] = false;
            for(Edge edge : edges.get(node)){
                if(!visited[node] && minDist[node] + edge.value < minDist[edge.to]){
                    minDist[edge.to] = minDist[node] + edge.value;
                    queue.add(edge.to);
                    visited[edge.to] = true;
                }
            }
        }
        if(minDist[end] == Integer.MAX_VALUE){
            System.out.println("unconnected");
        }else{
            System.out.println(minDist[end]);
        }
    }

}

class Edge{
    int from;
    int to;
    int value;
    Edge(int from, int to , int value){
        this.from = from;
        this.to = to;
        this.value = value;
    }

}

效率分析

队列优化版Bellman_ford 的时间复杂度并不稳定，效率高低依赖于图的结构。

例如如果是一个双向图，且每一个节点和所有其他节点都相连的话，那么该算法的时间复杂度就接近于 Bellman_ford 的 O(N * E) N 为节点数量，E为边的数量。

在这种图中，每一个节点都会重复加入队列 n - 1次，因为这种图中每个节点都有 n-1 条指向该节点的边，每条边指向该节点，就需要加入一次队列。

如果图越稠密，则 SPFA的效率越接近与 Bellman_ford。

反之，图越稀疏，SPFA的效率就越高。

一般来说，SPFA 的时间复杂度为 O(K * N) K 为不定值，因为节点需要计入几次队列取决于图的稠密度。

如果图是一条线形图且单向的话，每个节点的入度为1，那么只需要加入一次队列，这样时间复杂度就是 O(N)。

所以 SPFA 在最坏的情况下是 O(N * E)，但一般情况下时间复杂度为 O(K * N)。

尽管如此，以上分析都是理论上的时间复杂度分析。

并没有计算出队列和入队列的时间消耗。因为这个在不同语言上时间消耗也是不一定的。

拓展

这里可能有录友疑惑，while (!que.empty()) 队里里会不会造成死循环？例如图中有环，这样一直有元素加入到队列里？

其实有环的情况，要看它是正权回路还是负权回路。

题目描述中，已经说了，本题没有负权回路。

如图：

正权回路就是有环，但环的总权值为正数。

在有环且只有正权回路的情况下，即使元素重复加入队列，最后，也会因为所有边都松弛后，节点数值（minDist数组）不在发生变化了而终止。

（而且有重复元素加入队列是正常的，多条路径到达同一个节点，节点必要要选择一个最短的路径，而这个节点就会重复加入队列进行判断，选一个最短的）

在0094.城市间货物运输I 中我们讲过对所有边最多松弛 n -1 次，就一定可以求出所有起点到所有节点的最小距离即 minDist数组。

即使再松弛n次以上，所有起点到所有节点的最小距离（minDist数组）不会再变了。（这里如果不理解，建议认真看0094.城市间货物运输I讲解）

所以本题我们使用队列优化，有元素重复加入队列，也会因为最后 minDist数组不会在发生变化而终止。

节点再加入队列，需要有松弛的行为，而每个节点已经都计算出来起点到该节点的最短路径，那么就不会有执行这个判断条件if (minDist[to] > minDist[from] + value)，从而不会有新的节点加入到队列。

但如果本题有负权回路，那情况就不一样了。

五、bellman_ford之判断负权回路

95. 城市间货物运输 II

本题中，在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时，存在一种情况：图中可能出现负权回路。

负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。

为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴，算法还需检测这种特殊情况。

思路

使用 bellman_ford 算法来判断负权回路。

在 kama94.城市间货物运输I 中我们讲了 bellman_ford 算法的核心就是一句话：对所有边进行 n-1 次松弛。同时文中的【拓展】部分，我们也讲了松弛n次以上会怎么样？

在没有负权回路的图中，松弛 n 次以上，结果不会有变化。

但本题有负权回路，如果松弛 n 次，结果就会有变化了，因为有负权回路就是可以无限最短路径（一直绕圈，就可以一直得到无限小的最短距离）。

那么每松弛一次，都会更新最短路径，所以结果会一直有变化。

在代码中，进行n次松弛，前n-1次计算最短路，第n次判断是否有负环。如果第n次仍然有minDist需要更新的情况，那么说明有负环：

import java.util.*;
import java.util.List;


public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<Edge> edges = new ArrayList<>();
        for(int i = 0 ; i < m ; i++){
            edges.add(new Edge(scanner.nextInt(),scanner.nextInt(),scanner.nextInt()));
        }
        //初始化
        int start = 1;
        int end = n;
        int[] minDist = new int[n+1];
        Arrays.fill(minDist,Integer.MAX_VALUE);
        minDist[start] = 0;
        boolean flag = false;
        for(int i = 0 ; i < n ; i++){
            //对所有的边进行n次松弛操作，其中第n次用于判断是否有负环
            if(i < n-1){
                for(Edge edge : edges){
                    if(minDist[edge.from] != Integer.MAX_VALUE && minDist[edge.from] + edge.value < minDist[edge.to]){
                        minDist[edge.to] = minDist[edge.from] + edge.value;
                    }
                }
            }else{
                for(Edge edge : edges){
                    if(minDist[edge.from] != Integer.MAX_VALUE && minDist[edge.from] + edge.value < minDist[edge.to]){
                        flag = true;
                        break;
                    }
                }
            }
            
        }
        if(flag){
            System.out.println("circle");
        }else if(minDist[end] == Integer.MAX_VALUE){
            System.out.println("unconnected");
        }else{
            System.out.println(minDist[end]);
        }
    }

}

class Edge{
    int from;
    int to;
    int value;
    Edge(int from, int to , int value){
        this.from = from;
        this.to = to;
        this.value = value;
    }

}

拓展

本题可不可使用队列优化版的bellman_ford（SPFA）呢？

上面的解法中，我们对所有边松弛了n-1次后，在松弛一次，如果出现minDist出现变化就判断有负权回路。

如果使用 SPFA 那么节点都是进队列的，那么节点进入队列几次后足够判断该图是否有负权回路呢？

在 0094.城市间货物运输I-SPFA 中，我们讲过在极端情况下，即：所有节点都与其他节点相连，每个节点的入度为 n-1 （n为节点数量），所以每个节点最多加入 n-1 次队列。

那么如果节点加入队列的次数超过了 n-1次，那么该图就一定有负权回路。

所以本题也是可以使用 SPFA 来做的。

六、bellman_ford之单源有限最短路

96. 城市间货物运输 III

本题要求计算在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本。

根据bellman_ford算法的思路，容易想到可以进行k+1次松弛。

问题在于在每一次松弛的时候，受到松弛边的处理顺序的影响，当前在处理的边的结果可能在本次松弛过程中影响到其他边，实际起到了一条边被多次松弛的效果，这就导致了k实际上不起作用，这不是我们期望的。

我们期望的是第一次松弛只更新和start直接相连的边，第二次松弛在第一次松弛的基础上更新和start间隔1个城市的边。参考讲解：代码随想录：bellman_ford之单源有限最短路

那么只需要将上一次的minDist记录下来，本次更新使用上一次的minDist，避免本次更新minDist过程中使用到本次的结果。

Java实现如下：

import java.util.*;
import java.util.List;


public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<Edge> edges = new ArrayList<>();
        for(int i = 0; i < m; i++){
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            int value = scanner.nextInt();
            edges.add(new Edge(from,to,value));
        }
        int[] minDist = new int[n+1];
        int[] minDist_pre ;
        Arrays.fill(minDist,Integer.MAX_VALUE);
        int start = scanner.nextInt();
        int end = scanner.nextInt();
        minDist[start] = 0;
        int k = scanner.nextInt();
        for(int i = 0 ; i < k+1 ; i++){
            minDist_pre = Arrays.copyOf(minDist,n+1);
            for(Edge edge : edges){
                if(minDist_pre[edge.from] != Integer.MAX_VALUE && minDist_pre[edge.from] + edge.value < minDist[edge.to]){
                    //要更新的是 minDist[edge.to] 使用 minDist_pre进行更新
                    minDist[edge.to] = minDist_pre[edge.from] + edge.value;
                }
            }
        }
        if(minDist[end] == Integer.MAX_VALUE){
            System.out.println("unreachable");
        }else{
            System.out.println(minDist[end]);
        }
    }

}

class Edge{
    int from;
    int to;
    int value;
    Edge(int from, int to , int value){
        this.from = from;
        this.to = to;
        this.value = value;
    }

}

拓展一（边的顺序的影响）

其实边的顺序会影响我们每一次拓展的结果。

我来给大家举个例子。

我上面讲解中，给出的示例是这样的：

我将示例中边的顺序改一下，给成：

所构成是图是一样的，都是如下的这个图，但给出的边的顺序是不一样的。

再用版本一的代码是运行一下，发现结果输出是 1，是对的。

分明刚刚输出的结果是 -2，是错误的，怎么一样的图，这次输出的结果就对了呢？

其实这是和示例中给出的边的顺序是有关的，

我们按照修改后的示例再来模拟对所有边的第一次拓展情况。

初始化：

边：节点3 -> 节点1，权值为-1 ，节点3还没有被计算过，节点1 不更新。

边：节点3 -> 节点4，权值为1 ，节点3还没有被计算过，节点4 不更新。

边：节点2 -> 节点3，权值为 1 ，节点2还没有被计算过，节点3 不更新。

边：节点1 -> 节点2，权值为 -1 ，minDist[2] > minDist[1] + (-1)，更新 minDist[2] = 0 + (-1) = -1 ，如图：

以上是对所有边松弛一次的状态。

可以发现同样的图，边的顺序不一样，使用版本一的代码每次松弛更新的节点也是不一样的。

而边的顺序是随机的，是题目给我们的，所以本题我们才需要记录上一次松弛的minDist，来保障每一次对所有边松弛的结果。

拓展二（本题本质）

那么前面讲解过的 94.城市间货物运输I 和 95.城市间货物运输II 也是bellman_ford经典算法，也没使用 minDist_copy，怎么就没问题呢？

94.城市间货物运输I，是没有负权回路的，那么多松弛多少次，对结果都没有影响。

求节点1 到节点n 的最短路径，松弛n-1 次就够了，松弛大于 n-1次，结果也不会变。

那么在对所有边进行第一次松弛的时候，如果基于本次计算的 minDist 来计算 minDist （相当于多做松弛了），也是对最终结果没影响。

95.城市间货物运输II 是判断是否有负权回路，一旦有负权回路，对所有边松弛 n-1 次以后，在做松弛 minDist 数值一定会变，根据这一点来判断是否有负权回路。

所以，95.城市间货物运输II 只需要判断minDist数值变化了就行，而 minDist 的数值对不对，并不是我们关心的。

那么本题为什么计算minDist 一定要基于上次的 minDist 数值。

其关键在于本题的两个因素：

本题可以有负权回路，说明只要多做松弛，结果是会变的。
本题要求最多经过k个节点，对松弛次数是有限制的。（这就不允许有多松弛的效果）

如果本题中没有负权回路的测试用例，那版本一的代码就可以过了，也就不用我费这么大口舌去讲解的这个坑了。

拓展三（SPFA）

本题也可以用 SPFA来做，关于 SPFA ，已经在这里 0094.城市间货物运输I-SPFA 有详细讲解。

使用SPFA算法解决本题的时候，关键在于如何控制松弛k次。

其实实现不难，但有点技巧，可以用一个变量 que_size 记录每一轮松弛入队列的所有节点数量。

下一轮松弛的时候，就把队列里 que_size 个节点都弹出来，就是上一轮松弛入队列的节点。

（SPFA实际上更符合对k个节点的要求，更加直观）

代码如下（详细注释）

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;

struct Edge { //邻接表
    int to;  // 链接的节点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};


int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<list<Edge>> grid(n + 1); // 邻接表

    // 将所有边保存起来
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid[p1].push_back(Edge(p2, val));
    }
    int start, end, k;
    cin >> start >> end >> k;

    k++;

    vector<int> minDist(n + 1 , INT_MAX);
    vector<int> minDist_copy(n + 1); // 用来记录每一次遍历的结果

    minDist[start] = 0;

    queue<int> que;
    que.push(start); // 队列里放入起点

    int que_size;
    while (k-- && !que.empty()) {

        minDist_copy = minDist; // 获取上一次计算的结果
        que_size = que.size(); // 记录上次入队列的节点个数
        while (que_size--) { // 上一轮松弛入队列的节点，这次对应的边都要做松弛
            int node = que.front(); que.pop();
            for (Edge edge : grid[node]) {
                int from = node;
                int to = edge.to;
                int price = edge.val;
                if (minDist[to] > minDist_copy[from] + price) {
                    minDist[to] = minDist_copy[from] + price;
                    que.push(to);
                }
            }

        }
    }
    if (minDist[end] == INT_MAX) cout << "unreachable" << endl;
    else cout << minDist[end] << endl;

}

时间复杂度： O(K * H) H 为不确定数，取决于图的稠密度，但H 一定是小于等于 E 的

关于 SPFA的是时间复杂度分析，我在0094.城市间货物运输I-SPFA 有详细讲解

但大家会发现，以上代码大家提交后，怎么耗时这么多？

理论上，SPFA的时间复杂度不是要比 bellman_ford 更优吗？

怎么耗时多了这么多呢？

以上代码有一个可以改进的点，每一轮松弛中，重复节点可以不用入队列。

因为重复节点入队列，下次从队列里取节点的时候，该节点要取很多次，而且都是重复计算。

所以代码可以优化成这样：

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;

struct Edge { //邻接表
    int to;  // 链接的节点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};


int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<list<Edge>> grid(n + 1); // 邻接表

    // 将所有边保存起来
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，权值为 val
        grid[p1].push_back(Edge(p2, val));
    }
    int start, end, k;
    cin >> start >> end >> k;

    k++;

    vector<int> minDist(n + 1 , INT_MAX);
    vector<int> minDist_copy(n + 1); // 用来记录每一次遍历的结果

    minDist[start] = 0;

    queue<int> que;
    que.push(start); // 队列里放入起点

    int que_size;
    while (k-- && !que.empty()) {

        vector<bool> visited(n + 1, false); // 每一轮松弛中，控制节点不用重复入队列
        minDist_copy = minDist; 
        que_size = que.size(); 
        while (que_size--) { 
            int node = que.front(); que.pop();
            for (Edge edge : grid[node]) {
                int from = node;
                int to = edge.to;
                int price = edge.val;
                if (minDist[to] > minDist_copy[from] + price) {
                    minDist[to] = minDist_copy[from] + price;
                    if(visited[to]) continue; // 不用重复放入队列，但需要重复松弛，所以放在这里位置
                    visited[to] = true;
                    que.push(to);
                }
            }

        }
    }
    if (minDist[end] == INT_MAX) cout << "unreachable" << endl;
    else cout << minDist[end] << endl;
}

以上代码提交后，耗时情况：

大家发现依然远比 bellman_ford 的代码版本耗时高。

这又是为什么呢？

对于后台数据，我特别制作的一个稠密大图，该图有250个节点和10000条边，在这种情况下， SPFA 的时间复杂度是接近与 bellman_ford的。

但因为 SPFA 节点的进出队列操作，耗时很大，所以相同的时间复杂度的情况下，SPFA 实际上更耗时了。

这一点我在 0094.城市间货物运输I-SPFA 有分析，感兴趣的录友再回头去看看。

拓展四（能否用dijkstra）

本题能否使用 dijkstra 算法呢？

dijkstra 是贪心的思路每一次搜索都只会找距离源点最近的非访问过的节点。

如果限制最多访问k个节点，那么 dijkstra 未必能在有限次就能到达终点，即使在经过k个节点确实可以到达终点的情况下。

这么说大家会感觉有点抽象，我用 dijkstra朴素版精讲里的示例在举例说明：（如果没看过我讲的dijkstra朴素版精讲，建议去仔细看一下，否则下面讲解容易看不懂）

在以下这个图中，求节点1 到节点7 最多经过2个节点的最短路是多少呢？

最短路显然是：

最多经过2个节点，也就是3条边相连的路线：节点1 -> 节点2 -> 节点6-> 节点7

如果是 dijkstra 求解的话，求解过程是这样的：（下面是dijkstra的模拟过程，我精简了很多，如果看不懂，一定要先看dijkstra朴素版精讲）

初始化如图所示：

找距离源点最近且没有被访问过的节点，先找节点1

距离源点最近且没有被访问过的节点，找节点2：

距离源点最近且没有被访问过的节点，找到节点3：

距离源点最近且没有被访问过的节点，找到节点4：

此时最多经过2个节点的搜索就完毕了，但结果中minDist[7] （即节点7的结果）并没有被更。

那么 dijkstra 会告诉我们节点1 到节点7 最多经过2个节点的情况下是不可到达的。

通过以上模拟过程，大家应该能感受到 dijkstra 贪心的过程，正是因为贪心，所以 dijkstra 找不到节点1 -> 节点2 -> 节点6-> 节点7 这条路径。

本质上的原因是dijkstra是贪心的。

总结

本题是单源有限最短路问题，也是 bellman_ford的一个拓展问题，如果理解bellman_ford 其实思路比较容易理解，但有很多细节。

例如为什么要用 minDist_copy 来记录上一轮松弛的结果。这也是本篇我为什么花了这么大篇幅讲解的关键所在。

接下来，还给大家做了四个拓展：

边的顺序的影响
本题的本质
SPFA的解法
能否用dijkstra

学透了以上四个拓展，相信大家会对bellman_ford有更深入的理解。

七、Floyd 算法精讲

97. 小明逛公园

思路

本题是经典的多源最短路问题，即求多个起点到多个终点的多条最短路径。

通过本题来系统讲解一个新的最短路算法-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的最短距离可以由更小的区间组成。

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

节点1 到节点9 的最短距离可以由节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成，也可以有节点1 到节点7的最短距离 + 节点7 到节点9的最短距离的距离组成。

那么选哪个呢？

是不是要选一个最小的，毕竟是求最短路。

此时我们已经接近明确递归公式了。

之前在讲解动态规划的时候，给出过动规五部曲：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

那么接下来我们还是用这五部来给大家讲解 Floyd。

1、dp数组及下标含义

grid[i][j][k] = m：表示从节点 i 考虑经过（可以选择经过或者不经过）节点1~k 到节点j 的代价是m.

2、确定递推公式

想要从 grid[i][j][k-1] 得到 grid[i][j][k] ，考虑两种情况

（1）从i到j的最短路径经过节点k，那么

grid[i][j][k] = grid[i][k][k-1] + grid[k][j][k-1] 右边的两个依赖项均计算过了

（2）从i到j的最短路径经过节点k，那么

grid[i][j][k] = grid[i][j][k-1]

综上，递推公式为 grid[i][j][k] = Math.min(grid[i][k][k-1] + grid[k][j][k-1] , grid[i][j][k-1]);

3、初始化

考虑 k = 0 的情况，根据定义，此时grid[i][j][0] 是从i到j不经过任何节点所要付出的代价，那么只能是i和j直接相连，所以在读入边的时候对grid[i][j][0]和 grid[j][i][0]初始化成对应的权重（无向图）

4、遍历顺序

dp数组是三维数组，初始化的都是k=0这个平面，要保证每一次计算的时候，它所以来的项都已经计算出来，并且依赖于之前计算的结果，这就要求从k=0这个平面一层一层向上计算。所以最外层的循环是k，内层的i的循环和j的循环可以交换。

5、dp模拟

日志输出的时候可以按k=0,1,2...逐层输出。

Java实现如下：

import java.util.*;


public class Main {


    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];
        for(int[][] grid1 : grid){
            for(int[] grid2 : grid1){
                Arrays.fill(grid2,Integer.MAX_VALUE);
            }
        }
        //读图，初始化
        for(int i = 0 ; i < m; i++){
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int value = scanner.nextInt();
            grid[start][end][0] = value;
            grid[end][start][0] = value;
        }
        //动态规划
        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] = grid[i][j][k-1];
                    else grid[i][j][k] = Math.min(grid[i][k][k-1] + grid[k][j][k-1],grid[i][j][k-1]); //如果初始化成Integer.MAX_VALUE,这里可能溢出，可以先判断一下是不是
                }
            }
        }
        //答案输出
        int plans = scanner.nextInt();
        for(int i = 0 ; i < plans ; i++){
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            if(grid[start][end][n] != Integer.MAX_VALUE){
                System.out.println(grid[start][end][n]);
            }else{
                System.out.println("-1");
            }
        }
    }

}

注意一个问题，dp数组递推的过程中，可能会出现Integer.MAX_VALUE相加导致溢出，需要预先判断一下。

也可以选择一个题目中一定不会到达的大数同时还能够避免溢出的来初始化。

空间优化

这里我们可以做一下空间上的优化，从滚动数组的角度来看，我们定义一个 grid[n + 1][ n + 1][2] 这么大的数组就可以，因为k 只是依赖于 k-1的状态，并不需要记录k-2，k-3，k-4 等等这些状态。

那么我们只需要记录 grid[i][j][1] 和 grid[i][j][0] 就好，之后就是 grid[i][j][1] 和 grid[i][j][0] 交替滚动。

在进一步想，如果本层计算（本层计算即k相同，从三维角度来讲） grid[i][j] 用到了本层中刚计算好的 grid[i][k] 会有什么问题吗？

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

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

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

那么就没必要区分，grid[i][k] 和 grid[k][j] 是属于 k - 1 层的呢，还是 k 层的。

所以递归公式可以为：

grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);

Java实现如下：

import java.util.*;


public class Main {


    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];
        for(int[] grid1 : grid){
            Arrays.fill(grid1,Integer.MAX_VALUE);
        }
        //读图，初始化
        for(int i = 0 ; i < m; i++){
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int value = scanner.nextInt();
            grid[start][end] = value;
            grid[end][start] = value;
        }
        //动态规划
        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] == Integer.MAX_VALUE || grid[k][j] == Integer.MAX_VALUE) continue;
                    else grid[i][j] = Math.min(grid[i][j],grid[i][k] + grid[k][j]);
                }
            }
        }
        
        //答案输出
        int plans = scanner.nextInt();
        for(int i = 0 ; i < plans ; i++){
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            if(grid[start][end] != Integer.MAX_VALUE){
                System.out.println(grid[start][end]);
            }else{
                System.out.println("-1");
            }
        }
    }

}

总结

本期如果上来只用二维数组来讲的话，其实更容易，但遍历顺序那里用二维数组其实是讲不清楚的，所以我直接用三维数组来讲，目的是将遍历顺序这里讲清楚。

理解了遍历顺序才是floyd算法最精髓的地方。

floyd算法的时间复杂度相对较高，适合稠密图且源点较多的情况。

如果是稀疏图，floyd是从节点的角度去计算了，例如图中节点数量是 1000，就一条边，那 floyd的时间复杂度依然是 O(n^3) 。

如果源点少，其实可以多次dijsktra 求源点到终点。

八、A * 算法精讲（A star算法）

127. 骑士的攻击

bfs

本题要求求最短路径，容易想到bfs：

Java实现：

import java.util.*;


public class Main {
    static int[][]directions = {{1,2},{2,1},{-1,2},{2,-1},{1,-2},{-2,1},{-1,-2},{-2,-1}};

    public static void main(String[] args) {
        int[][] grid = new int[1001][1001];
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for(int i = 0 ; i < n; i++){
            //注意每次都要把grid清0
            for(int[] l : grid){
                Arrays.fill(l,0);
            }
            int startX = scanner.nextInt();
            int startY = scanner.nextInt();
            int endX = scanner.nextInt();
            int endY= scanner.nextInt();
            if(startX == endX && startY == endY){
                System.out.println(0);
                continue;
            }
            Queue<int[]> queue = new ArrayDeque<>();
            queue.add(new int[]{startX,startY});
            while(!queue.isEmpty()){
                int[] nowLocation = queue.remove();
                int nowX = nowLocation[0];
                int nowY = nowLocation[1];
                for(int j = 0 ; j < 8 ; j++){
                    int nextX = nowX + directions[j][0];
                    int nextY = nowY + directions[j][1];
                    if(nextX < 1 || nextX > 1000 || nextY < 1 || nextY > 1000) continue;
                    if(grid[nextX][nextY] == 0){
                        grid[nextX][nextY] = grid[nowX][nowY] + 1;
                        queue.add(new int[]{nextX,nextY});
                    }
                }
                if(grid[endX][endY] != 0) break;
            }
            System.out.println(grid[endX][endY]);
        }
    }

}

C++实现：

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int moves[1001][1001];
int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
void bfs(int a1,int a2, int b1, int b2)
{
	queue<int> q;
	q.push(a1);
	q.push(a2);
	while(!q.empty())
	{
		int m=q.front(); q.pop();
		int n=q.front(); q.pop();
		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])
			{
				moves[mm][nn]=moves[m][n]+1;
				q.push(mm);
				q.push(nn);
			}
		}
	}
}

int main()
{
    int n, a1, a2, b1, b2;
    cin >> n;
    while (n--) {
        cin >> a1 >> a2 >> b1 >> b2;
        memset(moves,0,sizeof(moves));
		bfs(a1, a2, b1, b2);
		cout << moves[b1][b2] << endl;
	}
	return 0;
}

但提交后会时间超限。

Astar

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

其实只是场景不同而已我们在搜索最短路的时候，如果是无权图（边的权值都是1）那就用广搜，代码简洁，时间效率和 dijkstra 差不多（具体要取决于图的稠密）

如果是有权图（边有不同的权值），优先考虑 dijkstra。

而 Astar 关键在于启发式函数，也就是影响广搜或者 dijkstra 从容器（队列）里取元素的优先顺序。

A*算法通过启发函数的设计，实现有方向地搜索。

那么启发式函数落实到代码处，如果指引搜索的方向？

在本篇开篇中给出了BFS代码，指引搜索的方向的关键代码在这里：

int m=q.front();q.pop();
int n=q.front();q.pop();

从队列里取出什么元素，接下来就是从哪里开始搜索。

所以启发式函数要影响的就是队列里元素的排序！

这是影响BFS搜索方向的关键。

对队列里节点进行排序，就需要给每一个节点权值，如何计算权值呢？

每个节点的权值为F，给出公式为：F = G + H

G：起点达到目前遍历节点的距离

F：目前遍历的节点到达终点的距离

起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离就是起点到达终点的距离。

本题的图是无权网格状，在计算两点距离通常有如下三种计算方式：

曼哈顿距离，计算方式： 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 * 算法的结果不同。

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

所以使用欧拉距离计算和广搜搜出来的最短路的节点数是一样的。（路径可能不同，但路径上的节点数是相同的）

可以使用优先级队列帮我们排好序，每次出队列，就是F最小的节点。

Java实现：

import java.util.*;

class Knight{
    int x;
    int y;
    int g;
    int h;
    int weight;
    Knight(int x, int y){
        this.x = x;
        this.y = y;
    }

    void calWeight(int g,int endX,int endY){
        this.g = g;
        this.h = (x - endX) * (x - endX) + (y - endY) * (y - endY); // 统一不开根号，这样可以提高精度
        this.weight = this.g + this.h;
    }
}

class MyComparison implements  Comparator<Knight>{
    @Override
    public int compare(Knight o1, Knight o2) {
        return Integer.compare(o1.weight,o2.weight);
    }
}


public class Main {
    static int[][]directions = {{1,2},{2,1},{-1,2},{2,-1},{1,-2},{-2,1},{-1,-2},{-2,-1}};
    static int endX;
    static int endY;
    static PriorityQueue<Knight> queue = new PriorityQueue<>(new MyComparison());

    static int[][] grid =  new int[1001][1001];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for(int i = 0 ; i < n; i++){
            for(int[] arr : grid){
                Arrays.fill(arr,0);
            }
            Knight knight = new Knight(scanner.nextInt(),scanner.nextInt());
            endX = scanner.nextInt();
            endY = scanner.nextInt();
            knight.calWeight(0,endX,endY);
            astar(knight);
            while(!queue.isEmpty()) queue.remove();
            System.out.println(grid[endX][endY]);
        }
    }

    public static void astar(Knight knight){
        Knight cur,next;
        queue.add(knight);
        while(!queue.isEmpty()){
            cur = queue.remove();
            if(cur.x == endX && cur.y == endY) break;
            for(int i = 0 ; i < 8 ; i++){
                int nextX = cur.x + directions[i][0];
                int nextY = cur.y + directions[i][1];
                if(nextX < 1 || nextX > 1000 || nextY < 1 || nextY > 1000) continue;
                if(grid[nextX][nextY] == 0){
                    grid[nextX][nextY] = grid[cur.x][cur.y] + 1;
                    next = new Knight(nextX,nextY);
                    next.calWeight(cur.g+5,endX,endY);//统一不开根号，提高精度
                    queue.add(next);
                }
            }
        }

    }

}

感觉这里有必要讲解一下代码架构。

（1）为了实现对位置的排序，定义了一个类Knight专门用来存储当前的位置、当前的g、h和weight。

（2）为了实现优先队列排序，自定义了MyComparison 取 implements Comparator<Knight> 实现对Knight的排序，使用Integer.compare维护一个最小堆。

（3）Knight类中calWeight函数需要传入当前的g，endX和endY，用来计算h，并把g和h加和得到weight。Knight的x,y是要在创建的时候传入的。

（4）将一些必要的量，诸如grid，endX,endY设为全局静态变量，方便类内函数沟通，降低传参的要求。但也要注意每一轮grid初始化，每一轮要把queue清空。

C++实现：

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int moves[1001][1001];
int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
int b1, b2;
// F = G + H
// G = 从起点到该节点路径消耗
// H = 该节点到终点的预估消耗

struct Knight{
    int x,y;
    int g,h,f;
    bool operator < (const Knight & k) const{  // 重载运算符， 从小到大排序
     return k.f < f;
    }
};

priority_queue<Knight> que;

int Heuristic(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;

                // 开始计算F
				next.g = cur.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5
                next.h = Heuristic(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 = Heuristic(start);
        start.f = start.g + start.h;
		astar(start);
        while(!que.empty()) que.pop(); // 队列清空
		cout << moves[b1][b2] << endl;
	}
	return 0;
}