图论：常见的最短路算法模板

reso1mi 收录于算法

2021-03-17 约 5882 字预计阅读 12 分钟

849. Dijkstra 求最短路 I

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出-1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x，y，z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出-1。

数据范围： $1≤n≤500, 1≤m≤10^5$ , 图中涉及边长均不超过 10000。

进阶： $1≤n,m≤1.5×10^5$ , 图中涉及边长均不超过 10000。

输入样例：

输出样例：

解法一

Dijkstra 适用于非负权图，其核心思路就是将所有的点划分为两部分，一部分是已经确定最短路的点集合 $p$ ，这个集合最开始只有源点。另一部分是未确定最短路的点集合 $q$ 。

首先将刚加入 $p$ 的点的所有出边进行松弛（最开始就只有源点 $s$ ）
然后在 $q$ 中找一个离源点 $s$ 最近的，那么这个点的最短路就确定了，因为这个点当前的最短路必然是经过 $p$ 集合中的点进行松弛过后的，且图没有负权，所以这个点不可能再通过其他未确定的点中转来缩短距离（如果有负权就可能，所以 Dijkstra 无法处理存在负权的图），将其标记进入 $p$ 集合，然后重复步骤一，直到所有点都加入 $p$ 集合

Dijkstra 暴力写法，这题题目数据范围比较小 $n<500$ ，所以直接建邻接矩阵然后跑 Dijkstra，时间复杂度 $O(N^2)$

import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int INF = 0x3f3f3f3f;
        int[] in = read(br);
        int N = in[0], M = in[1];
        //邻接矩阵
        int[][] w = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(w[i], INF);
        }
        for (int i = 0; i < M; i++) {
            int[] t = read(br); //t[0]->t[1]
            int x = t[0]-1, y = t[1]-1;
            w[x][y] = Math.min(t[2], w[x][y]);
        }
        //dis[i]: 源点 s 到 i 的最短距离
        int[] dis = new int[N];
        boolean[] vis = new boolean[N];
        Arrays.fill(dis, INF);
        dis[0] = 0;
        for (int i = 0; i < N; i++) {
            int min = -1;
            //未确定最短路的点中距离 s 最近的点
            for (int j = 0; j < N; j++) {
                if (!vis[j] && (min==-1 || dis[j] < dis[min])) {
                    min = j;
                }
            }
            //松弛
            vis[min] = true;
            for (int j = 0; j < N; j++) {
                if (!vis[j]) {
                    dis[j] = Math.min(dis[j], dis[min] + w[min][j]);
                }
            }
        }
        out.println(dis[N-1] == INF ? -1 : dis[N-1]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

解法二

堆优化的 Dijkstra，上面的解法在数据量大的时候显然是不适用的，首先我们不能再使用邻接矩阵了，需要改用邻接表，同时采用小根堆来快速的获取未确定点集中距离源点最近的点，堆中需要存储节点编号以及当前节点最短路，时间复杂度大概 $O(m\log n)$ ，但是最坏情况下 $m$ 边数可能会达到 $n^2$ 级别（稠密图），导致堆优化的复杂度反而低于朴素的，但是大多数情况下边数不会有这么多，除此之外还有一些其它的优化方法，详见 OI-Wiki

import java.util.*;
import java.io.*;

class Main {

    static class Node {
        int idx, val;
        public Node(int idx, int val) {
            this.idx = idx;
            this.val = val;
        }
    }

    static int idx;
    static int N, M;
    static int[] h, e, ne, w;
    //a->b
    static void add(int a, int b, int c) {
        w[idx] = c; e[idx] = b; 
        ne[idx] = h[a]; h[a] = idx++;
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int INF = 0x3f3f3f3f;
        int[] in = read(br);
        N = in[0]; M = in[1];
        h = new int[N+1]; e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
        Arrays.fill(h, -1);
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            add(t[0], t[1], t[2]);
        }
        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2)->n1.val-n2.val);
        int[] dis = new int[N+1];
        //记录已经确定最短路的点集 s
        boolean[] vis = new boolean[N+1];
        Arrays.fill(dis, INF);
        dis[1] = 0;
        pq.add(new Node(1, 0));
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            //从未确定最短路的点中找 dis 最小的（如果弹出来的是已经确定过的就会跳过）
            int i = node.idx, v = node.val;
            if (vis[i]) continue;
            //标记该点已经确定最短路
            vis[i] = true;
            //松弛该点出边
            for (int j = h[i]; j != -1; j = ne[j]) {
                if (v+w[j] < dis[e[j]]) {
                    dis[e[j]] = v+w[j];
                    pq.add(new Node(e[j], v+w[j]));
                }
            }
        }
        out.println(dis[N] == INF ? -1 : dis[N]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

Java 其实还有一种更加简洁的写法，利用闭包，不用新建 Node 类

import java.util.*;
import java.io.*;

class Main {

    static int idx;
    static int N, M;
    static int[] h, e, ne, w;
    //a->b
    static void add(int a, int b, int c) {
        w[idx] = c; e[idx] = b; 
        ne[idx] = h[a]; h[a] = idx++;
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int INF = 0x3f3f3f3f;
        int[] in = read(br);
        N = in[0]; M = in[1];
        h = new int[N]; e = new int[M]; ne = new int[M]; w = new int[M];
        Arrays.fill(h, -1);
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            add(t[0]-1, t[1]-1, t[2]);
        }
        int[] dis = new int[N];
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->dis[a]-dis[b]);
        //记录已经确定最短路的点集 s
        boolean[] vis = new boolean[N];
        Arrays.fill(dis, INF);
        dis[0] = 0;
        pq.add(0);
        while (!pq.isEmpty()) {
            int i = pq.poll();
            if (vis[i]) continue;
            //标记该点已经确定最短路
            vis[i] = true;
            //松弛该点能到达的点的 dis
            for (int j = h[i]; j != -1; j = ne[j]) {
                if (dis[i]+w[j] < dis[e[j]]) {
                    dis[e[j]] = dis[i]+w[j];
                    pq.add(e[j]);
                }
            }
        }
        out.println(dis[N-1] == INF ? -1 : dis[N-1]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

853. 有边数限制的最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能存在负权回路 。

输入格式

第一行包含三个整数 n，m，k。

接下来 m 行，每行包含三个整数 x，y，z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出“impossible”。

数据范围： $1≤n,k≤500, 1≤m≤10000$ ，且任意边长的绝对值不超过 $10000$

输入样例：

输出样例：

解法一

Bellman−Ford，负权最短路算法，可以处理负权边，同时可以检测负权回路（回路的总权值为负数）。算法基于动态规划设计， $dis[i][j]$ 为源点 $s$ 经过最多 $i$ 条边到达 $j$ 节点的最短路。一共有 $N$ 个点，所以任意点的最短路最多经过的边数为 $N-1$ （负环没有最短路）

入口： $dis[i][s] = 0, 0 \leq i \leq N-1$
转移：遍历所有的边， $k \stackrel{w}{\longrightarrow} j$ ， $dis[i][j] = \min(dis[i-1][j]，dis[i][j]， dis[i-1][k] + w)$
出口： $dis[N-1][N]$
时间复杂度： $O(MN)$

本题中限制了边数，所以我们外层循环只到 $K$ 就行了，具体代码实现如下：

import java.util.*;
import java.io.*;

class Main {

    static class Edge {
        int s, e;
        int v;
        public Edge(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int INF = 0x3f3f3f3f;
        int N = in[0], M = in[1], K = in[2];
        Edge[] eds = new Edge[M];
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            eds[i] = new Edge(t[0], t[1], t[2]);
        }
        int[][] dis = new int[K+1][N+1];
        for (int i = 0; i <= K; i++) {
            Arrays.fill(dis[i], INF);
            dis[i][1] = 0;
        }
        for (int i = 1; i <= K; i++) {
            for (int j = 0; j < M; j++) {
                int s = eds[j].s, e = eds[j].e;
                if (dis[i-1][s] == INF) continue;
                // 不加 dis[i-1][e] 也能过 OJ，但是最好还是加上
                // dis[i][e] = Math.min(dis[i][e], dis[i-1][s] + eds[j].v); 
                dis[i][e] = Math.min(dis[i-1][e], Math.min(dis[i][e], dis[i-1][s] + eds[j].v));
            }
        }
        out.println(dis[K][N] == INF ? "impossible" : dis[K][N]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

这里存个疑问，为什么这里转移方程不加 $dis[i-1][e]$ 也能 AC？这里加上一定不会错，但是不加会有点迷惑。

这里我的想法是，如果不加 $dis[i-1][e]$ ，状态的定义其实就变成了：恰好经过 $i$ 条边的时候的最短路，这样出口就是 $\min(dp[1\sim M][N])$ ，但是由于我们在入口定义了 $dp[1\sim M][s]=0$ ，误打误撞的导致出口变成了 $dp[M][N]$ ，具体原因不想深究，明白错哪里就行了，总之这是一种不伦不类的写法，不要这样写，正确写法如下：

状态定义为恰好经过 i 条边的写法

import java.util.*;
import java.io.*;

class Main {

    static class Edge {
        int s, e;
        int v;
        public Edge(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int INF = 0x3f3f3f3f;
        int N = in[0], M = in[1], K = in[2];
        Edge[] eds = new Edge[M];
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            eds[i] = new Edge(t[0], t[1], t[2]);
        }
        //恰好经过 i 条边
        int[][] dis = new int[K+1][N+1];
        for (int i = 0; i <= K; i++) {
            Arrays.fill(dis[i], INF);
        }
        dis[0][1] = 0;
        for (int i = 1; i <= K; i++) {
            for (int j = 0; j < M; j++) {
                int s = eds[j].s, e = eds[j].e;
                if (dis[i-1][s] == INF) continue;
                dis[i][e] = Math.min(dis[i][e], dis[i-1][s] + eds[j].v);
            }
        }
        int res = INF;
        for (int i = 0; i <= K; i++) {
            res = Math.min(res, dis[i][N]);
        }
        out.println(res == INF ? "impossible" : res);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

解法二

实际中通常写的都是一维的 Bellman−Ford，降维后在 $dis[e] = \min(dis[e],dis[s] + w)$ 中， $dis[s]$ 不仅包含了前一轮最多经过 $i-1$ 条边到达 $s$ 的最短路，同时也包含了当前轮最多经过 $i$ 条边到达 $s$ 的最短路，所以最终经过 $k$ 次松弛得到的结果 $dis[N]$ 可能不只经过了 $k$ 条边，所以在这题中我们需要保存一下上一轮的状态，用上一轮的 $dis[s]$ 来更新当前轮的 $dis[e]$ ，保证最后结果经过的边不超过 $K$

import java.util.*;
import java.io.*;

class Main {

    static class Edge {
        int s, e;
        int v;
        public Edge(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int INF = 0x3f3f3f3f;
        int N = in[0], M = in[1], K = in[2];
        Edge[] eds = new Edge[M];
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            eds[i] = new Edge(t[0]-1, t[1]-1, t[2]);
        }
        //dis[i][j]: 源点最多经过 i 条边，到达 j 点的最短路
        int[] dis = new int[N];
        //上一轮经过 (i-1) 次松弛后的结果，避免串联更新（当前轮更新当前轮），因为这题需要保证最多只能经过 K 条边
        int[] last = new int[N];
        Arrays.fill(dis, INF);
        dis[0] = 0;
        for (int i = 0; i < K; i++) {
            System.arraycopy(dis, 0, last, 0, N);
            for (int j = 0; j < M; j++) {
                int s = eds[j].s, e = eds[j].e;
                if (last[s] == INF) continue;
                dis[e] = Math.min(dis[e], last[s] + eds[j].v);
            }
        }
        out.println(dis[N-1] == INF ? "impossible" : dis[N-1]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

如果数据量比较大可以改成 SPFA，如下：

import java.util.*;
import java.io.*;

class Main {
    
    static int idx;
    static int N, M, K;
    static int[] h, e, ne, w;
    //a->b
    static void add(int a, int b, int c) {
        w[idx] = c; e[idx] = b; 
        ne[idx] = h[a]; h[a] = idx++;
    }
        
    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] in = read(br);
        int INF = 0x3f3f3f3f;
        N = in[0]; M = in[1]; K = in[2];
        e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
        h = new int[N+1]; Arrays.fill(h, -1);
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            add(t[0], t[1], t[2]);
        }
        //恰好经过 i 条边到达 j 的最短路
        int[][] dis = new int[K+1][N+1];
        boolean[][] vis = new boolean[K+1][N+1];
        for (int i = 0; i <= K; i++) {
            Arrays.fill(dis[i], INF);
        }
        dis[0][1] = 0; vis[0][1] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1, 0});
        while (!queue.isEmpty()) {
            int[] top = queue.poll();
            int i = top[0], step = top[1];
            if (step >= K) continue;
            vis[step][i] = false;
            for (int j = h[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (w[j]==INF || dis[step][i]==INF) continue;
                if (dis[step+1][k] > dis[step][i] + w[j]) {
                    dis[step+1][k] = dis[step][i] + w[j];
                    if (!vis[step+1][k]) {
                        queue.add(new int[]{k, step+1});
                        vis[step+1][k] = true;
                    }
                }
            }
        }
        int res = INF;
        for (int i = 0; i <= K; i++) {
            res = Math.min(res, dis[i][N]);
        }
        out.println(res==INF ? "impossible" : res);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

851. spfa 求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x，y，z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出”impossible”。

数据范围： $1≤n,m≤105$ ，图中涉及边长绝对值均不超过 10000。

输入样例：

输出样例：

解法一

SPFA 基于 Bellman−Ford 进行优化，最坏时间复杂度依然是 $O(MN)$ ，但是常规情况下速度还是很快的，时间复杂度不稳定。

优化的点在于 BF 在松弛过程中有一些顶点可能早已经得到了最短路，后续不会再被松弛，但是依然会进行判断，浪费了时间，所以我们可以考虑只对最短路估计值减小了的顶点的出边进行松弛

具体实现中，我们可以采用一个 FIFO 队列存储松弛成功的顶点，最开始就只有源点 $s$ ，入队的顶点需要进行标记，对队列中顶点的出边进行松弛，将松弛成功并且没有标记的顶点继续加入队列。乍一看和 BFS 类似，但是这里其实有一个很大的区别：SPFA 在队首元素出队后需要将其标记取消，因为队首顶点后续可能还会被其他顶点松弛，这也是 SPFA 时间复杂度不稳定的原因（容易被卡，但是最差也是退化到 $O(NM)$ ）。

import java.util.*;
import java.io.*;

class Main {

    static int idx;
    static int[] e, h, ne, w;
    //a->b
    public static void add(int a, int b, int c){
        e[idx] = b; w[idx] = c;
        ne[idx] = h[a]; h[a] = idx++;
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int INF = 0x3f3f3f3f;
        int[] in = read(br);
        int N = in[0], M = in[1];
        e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
        h = new int[N+1]; Arrays.fill(h, -1);
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            add(t[0], t[1], t[2]);
        }
        Queue<Integer> queue = new LinkedList<>();
        boolean[] vis = new boolean[N+1];
        int[] dis = new int[N+1];
        Arrays.fill(dis, INF);
        dis[1] = 0; vis[1] = true;
        queue.add(1);
        while (!queue.isEmpty()) {
            int top = queue.poll();
            vis[top] = false;
            for (int i = h[top]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dis[j] > dis[top] + w[i]) {
                    dis[j] = dis[top] + w[i];
                    if (!vis[j]) {
                        queue.add(j);
                        vis[j] = true;
                    }
                }
            }
        }
        out.println(dis[N] == INF ? "impossible" : dis[N]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

852. spfa 判断负环

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x，y，z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

如果图中存在负权回路，则输出“Yes”，否则输出“No”。

数据范围： $1≤n≤2000,1≤m≤10000$ ，图中涉及边长绝对值均不超过 10000。

输入样例：

输出样例：

Yes

解法一

题目是判断图有没有负环，但是图不一定是联通的，单纯从某个点出发并不一定能走到负环上，暴力的方法就是对每个点作为源点做一次 spfa，但是这样显然复杂度过高

考虑增加一个虚拟节点，和所有的点增加一条权值为 0 的单向边，新增加的虚拟节点一定能走到负环上，所以我们对虚拟节点做一次 spfa 就能判断出原图是否有负环模拟第一次入队出队，虚拟节点出队后就会将所有的节点入队， $dis[i]$ 为虚拟源点到当前节点的最短路，所以一开始所有的 $dis[v_i]=0$ ，不用初始化为 $\inf$ 。

然后就是关键的判环步骤，我们只需要记录下每个点到虚拟源点的边的数量就行了（初始 $cnt[v_i]=1$ ），如果有负环就会无限制的松弛负环上的边，在负环路上打转，所以如果松弛后某个点到虚拟源点的边的数量大于等于 $N+1$ 就说明存在负环

import java.util.*;
import java.io.*;

class Main {

    static int INF = 0x3f3f3f3f;
    static int N, M;
    static int idx;
    static int[] e, h, ne, w;
    //a->b
    public static void add(int a, int b, int c){
        e[idx] = b; w[idx] = c;
        ne[idx] = h[a]; h[a] = idx++;
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        N = in[0]; M = in[1];
        e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
        h = new int[N+1]; Arrays.fill(h, -1);
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            add(t[0], t[1], t[2]);
        }
        out.println(spfa() ? "Yes" : "No");
        out.flush();
    }

    public static boolean spfa() {
        Queue<Integer> queue = new LinkedList<>();
        int[] dis = new int[N+1];
        boolean[] vis = new boolean[N+1];
        int[] cnt = new int[N+1];
        for (int i = 1; i <= N; i++) {
            queue.add(i);
            vis[i] = true;
            cnt[i] = 1;
        }
        while (!queue.isEmpty()) {
            int top = queue.poll();
            vis[top] = false;
            for (int i = h[top]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dis[j] > dis[top] + w[i]) {
                    dis[j] = dis[top] + w[i];
                    cnt[j] = cnt[top] + 1;
                    if (cnt[j] >= N+1) return true;
                    if (!vis[j]) {
                        queue.add(j);
                        vis[j] = true;
                    }
                }
            }
        }
        return false;
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

854. Floyd 求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出“impossible”。

数据保证图中不存在负权回路。

输入格式：

第一行包含三个整数 n，m，k

接下来 m 行，每行包含三个整数 x，y，z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

接下来 k 行，每行包含两个整数 x，y，表示询问点 x 到点 y 的最短距离。

输出格式

共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。

数据范围： $1≤n≤200,1≤k≤n^2，1≤m≤20000$ , 图中涉及边长绝对值均不超过 10000。

输入样例：

输出样例：

impossible
1

解法一

Floyd 是一个多源的最短路算法，也就是可以同时求出图中任意两点之间的最短路，本质是一个 DP，时间复杂度较高

状态定义： $dis[k][i][j]$ ，从 $i$ 到 $j$ 经过前 $k$ 个点中转后的最短路
入口： $dis[0][i][i]=0,dis[0][i][j] = w_{ij}$
转移： $dis[k][i][j]=\min(dis[k-1][i][j],dis[k-1][i][k]+dis[k-1][k][j])$
出口： $dis[N][i][j]$ ，时间复杂度 $O(N^3)$

由于 $dis[k]$ 仅仅依赖 $dis[k-1]$ ，所以通常我们这里都会降维写二维的

import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int N = in[0], M = in[1], K = in[2];
        int INF = 0x3f3f3f3f;
        int[][] dis = new int[N+1][N+1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dis[i], INF);
            dis[i][i] = 0;
        }
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            int x = t[0], y = t[1];
            dis[x][y] = Math.min(dis[x][y], t[2]);
        }
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (dis[i][k] == INF || dis[k][j] == INF) continue;
                    dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
        for (int i = 0; i < K; i++) {
            int[] q = read(br);
            int res = dis[q[0]][q[1]];
            out.println(res == INF ? "impossible" : res);
        }
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

三维的写法：854. Floyd 求最短路三维 DP 写法，不降维

import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int N = in[0], M = in[1], K = in[2];
        int INF = 0x3f3f3f3f;
        int[][][] dis = new int[N+1][N+1][N+1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dis[0][i], INF);
            dis[0][i][i] = 0;
        }
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            int x = t[0], y = t[1];
            dis[0][x][y] = Math.min(dis[0][x][y], t[2]);
        }
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (dis[k-1][i][k] == INF || dis[k-1][k][j] == INF) {
                        dis[k][i][j] = dis[k-1][i][j];
                    } else {
                        dis[k][i][j] = Math.min(dis[k-1][i][j], dis[k-1][i][k] + dis[k-1][k][j]);   
                    }
                }
            }
        }
        for (int i = 0; i < K; i++) {
            int[] q = read(br);
            int res = dis[N][q[0]][q[1]];
            out.println(res == INF ? "impossible" : res);
        }
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

目录

图论：常见的最短路算法模板

849. Dijkstra 求最短路 I

解法一

解法二

853. 有边数限制的最短路

解法一

解法二

851. spfa 求最短路

解法一

852. spfa 判断负环

解法一

854. Floyd 求最短路

解法一