本节所有算法和优化算法均有对应的题目和 Java 代码，都附在文后了。

最短路算法	Floyd	Bellman-Ford	Dijkstra	Johnson（本文不涉及）
最短路类型	每对结点之间的最短路	单源最短路		每对结点之间的最短路
作用于	任意图		非负权图	任意图
能否检测负环	✅		❌	✅
时间复杂度	$O(N^3)$	$O(NM)$	$O(M\log M)$ （优先队列）	$O(NM\log M)$

本文题目难度标识：🟩简单，🟨中等，🟥困难。

定义与定理

不同教科书对于 walk、trail、path 的中文叫法不尽相同，注意区分！

途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径 $w$ 是一个边的序列 $e_1, e_2, \ldots, e_k$ ，使得存在一个顶点序列 $v_0, v_1, \ldots, v_k$ 满足 $e_i = (v_{i-1}, v_i)$ ，其中 $i \in [1, k]$ 。这样的途径可以简写为 $v_0 \to v_1 \to v_2 \to \cdots \to v_k$ 。通常来说，边的数量 $k$ 被称作这条途径的长度（如果边是带权的，长度通常指途径上的边权之和，题目中也可能另有定义）。

迹 (trail)：对于一条途径 $w$ ，若 $e_1, e_2, \ldots, e_k$ 两两互不相同，则称 $w$ 是一条迹。

路径 (path)，又称 简单路径 (simple path)：对于一条迹 $w$ ，若其连接的点的序列中点两两不同，则称 $w$ 是一条路径。

为了方便叙述，本文约定以下记号的含义：

$n$ 为图上点的数目， $m$ 为图上边的数目；
$s$ 为最短路的源点；
$D(u)$ 为 $s$ 点到 $u$ 点的实际最短路长度；
$dis(u)$ 为 $s$ 点到 $u$ 点的估计最短路长度。任何时候都有 $dis(u) \geq D(u)$ 。特别地，当最短路算法终止时，应有 $dis(u)=D(u)$ 。
$w(u,v)$ 为 $(u,v)$ 这一条边的边权。

一些最短路的性质

性质 1：对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。
性质 2：对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。
性质 3：对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过 n，边数不会超过 n-1。

Floyd 算法

可用于求任意两个结点之间的最短路径，可用于有向图或无向图，边权可正可负但最短路必须存在（不能有负环）。

定义一个数组 f[k][x][y]，表示只允许经过结点 1 到 k（也就是说，在子图 $V'={1, 2, \ldots, k}$ 中的路径，注意，x 与 y 不一定在这个子图中），结点 x 到结点 y 的最短路长度。显然，f[n][x][y] 就是结点 x 到结点 y 的最短路长度。因为 $V'={1, 2, \ldots, n}$ 即为 V 本身，其表示的最短路径就是所求路径。

接下来考虑如何求出 f 数组的值。f[0][i][j] 表示一张图的边权，初始化方式：

当 i 与 j 间有直接相连的边的时，f[0][i][j] = w(i,j)
当 i == j 时，f[0][i][j] = 0
当 i 与 j 没有直接相连的边的时。f[0][i][j] = +∞

推导方式：f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])

f[k-1][x][y]：不经过 k 点的最短路径
f[k-1][x][k]+f[k-1][k][y]：经过了 k 点的最短路

核心代码：

for (k = 1; k <= n; k++)
  for (x = 1; x <= n; x++)
    for (y = 1; y <= n; y++)
      f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);

熟悉站内文章动态规划压缩空间写法的你一眼看出来，第一维对结果无影响可将其省略，于是可以直接改成 f[x][y] = min(f[x][y], f[x][k]+f[k][y])。

综上，算法的复杂度为：

时间复杂度： $O(n^3)$
空间复杂度： $O(n^2)$

Bellman-Ford 算法

Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

对边 (u,v) 进行松弛操作，意味着有： $dis(v) = \min (dis(v), dis(u) + w(u, v))$ 。Bellman–Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

时间复杂度估计：

在最短路存在的情况下，一次松弛操作（ $O(m)$ $O (m)$ 时间复杂度）会使最短路的边数至少 +1，即每一轮松弛可以使某些点的最短路径边数上限增加 1。解释如下：
- Bellman–Ford 的每一轮松弛可以将最短路径的信息沿着边传播一步。
- 第 1 轮松弛后，能正确求出从源点 s 出发、只经过 1 条边 的所有最短路径。
- 第 2 轮松弛后，可以求出所有经过 最多 2 条边 的最短路径。
- 依此类推，第 k 轮后，可以求出最多包含 k 条边的最短路径。
根据性质 3，最短路的边数最多为 n-1
因此总时间复杂度为 $O(nm)$

如果从 S 点出发，抵达一个负环时，松弛操作会无休止地进行下去。前面的论证已经说明对于最短路存在的图松弛操作最多会进行 n-1 轮。如果第 n 轮循环仍出现能松弛的边，说明从 S 点出发，能够抵达负环。

即使第 n 轮循环仍出现能松弛的边，并不意味着图上不存在负环。如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行 Bellman–Ford 算法。

SPFA

Shortest Path Faster Algorithm，SPFA，是 Bellman-Ford 的队列优化算法。它是西南交通大学段凡丁于 1994 年发表的论文中的名字。不过，段凡丁的证明是错误的，且在 Bellman-Ford 算法提出后不久（1957 年）已有队列优化内容，所以国际上不承认 SPFA 算法是段凡丁提出的。一般国内 OI 界中才有 SPFA 的说法。

在 Bellman-Ford 中，有时候我们并不需要那么多无用的松弛操作。很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。

我们用队列来维护「哪些结点可能会引起松弛操作」，就能只访问必要的边了。SPFA 也可以用于判断 S 点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 n 条边时，说明 S 点可以抵达一个负环。

虽然在大多数情况下 SPFA 跑得很快，但其最坏情况下的时间复杂度为 O(nm)。在没有负权边时最好使用 Dijkstra 算法。

更多 Bellman–Ford 算法优化详看：如何看待 SPFA 算法已死这种说法？ - 知乎

Dijkstra 算法

Dijkstra（/ˈdikstrɑ/或/ˈdɛikstrɑ/）算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解 非负权图 上单源最短路径的算法。

算法思想

将图 G(V,E) 中结点集合 V 分成两组：

已确定最短路长度的点集（记为 S 集合）。
未确定最短路长度的点集（记为 T 集合）。一开始所有的点都属于 T 集合。

初始化 $dis(s)=0$ ，其他点的 $dis$ 均为 $+\infty$ 。这样，第一次操作时可将源点加入 S 集合中。

然后重复这些操作：

从 T 集合中，选取一个最短路长度最小的结点，移到 S 集合中。
对那些刚刚被加入 S 集合的结点的所有出边执行松弛操作。
直到 T 集合为空，算法结束。

在操作的过程中每个结点对应一个距离 dis，S 中的结点的距离就是从 s 到此结点的最短路径长度；T 中的结点的距离，是从 s 到此结点只包含 S 中的结点为中间结点的当前最短路径长度。

例子：Dijkstra 算法图示

一个总部和 6 个工地，求从总部到各工地的最短路径。

解：

A-C-B, d(A,B)=13;
A-C, d(A,C)=10;
A-C-E-D, d(A,D)=18;
A-C-E, d(A,E)=14;
A-C-E-F, d(A,F)=16;
A-C-E-F-G, d(A,G)=22.

时间复杂度

时间复杂度分析：

操作 2 总时间复杂度为 $O(m)$
操作 1 总时间复杂度根据实现方式有所不同
- $O(n^2)$ 。朴素的实现方法为每一轮操作执行完毕后，直接在 T 集合中暴力寻找最短路长度最小的结点。
- 可以用堆来优化这一过程：每成功松弛一条边 (u,v)，就将 v 插入堆中（如果 v 已经在堆中，直接执行 Decrease-key），操作 1 直接取堆顶结点即可。共计 O(m) 次 Decrease-key，O(n) 次 pop，选择不同堆可以取到不同的复杂度。
  - $O(n\log n)$ ：这是堆优化可达到最优时间复杂度，可用斐波那契堆实现
  - $O(m\log n)$ ：优先队列。无法执行 Decrease-key 操作，但可以通过每次松弛时重新插入该结点，且弹出时检查该结点是否已被松弛过，若是则跳过，优点是实现较简单。
  - $O(m\log n)$ ：线段树。在一些特殊的非递归线段树实现下，该做法常数比堆更小。并且线段树支持的操作更多，在一些特殊图问题上只能用线段树来维护。

全过程的时间复杂度为：

朴素做法： $O(n^2 + m) = O(n^2)$ 。
堆优化最优复杂度： $O(n\log n+m)$

在稀疏图中， $m = O(n)$ ，堆优化的 Dijkstra 算法具有较大的效率优势；而在稠密图中， $m = O(n^2)$ ，这时候使用朴素实现更优。

例题与代码

Floyd

🟨 B3647 【模板】Floyd - 洛谷

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] f = new int[n+1][n+1];
        // 初始化图
        for(int i=1;i<=n;i++){
            Arrays.fill(f[i],Integer.MAX_VALUE);
            f[i][i]=0;
        }
        for(int i=0;i<m;i++){
            int startNode = in.nextInt();
            int endNode = in.nextInt();
            int weight = in.nextInt();
            int resWeight = Math.min(f[startNode][endNode],weight);
            // 无向图的邻接矩阵为对称矩阵
            f[startNode][endNode] = resWeight;
            f[endNode][startNode] = resWeight;
        }

        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
	                // 本题边权为正整数，这里处理无限值
                    int addRes = f[i][k]==Integer.MAX_VALUE || f[k][j]==Integer.MAX_VALUE? Integer.MAX_VALUE : f[i][k]+f[k][j];
                    // 最短路性质 2
                    f[i][j] = Math.min(f[i][j],addRes);
                }
            }
        }

        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                System.out.print(f[i][j]+" ");
            }
            System.out.println();
        }
    }
}

Bellman-Ford

🟨 P3371 【模板】单源最短路径（弱化版） - 洛谷

下面的代码为 Bellman-Ford 算法的实现，没有进行负环检测。此外，为了降低内存的使用，代码对输入方式进行优化（否则此题内存超限）。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) {
        int n = nextInt();
        int m = nextInt();
        int src = nextInt();
        long[] dis = new long[n+1];
        int[][] edges = new int[m][3];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[src] = 0;
        // 根据题意进行的存边操作
        for (int i = 0; i < m; i++) {
            edges[i][0] = nextInt();
            edges[i][1] = nextInt();
            edges[i][2] = nextInt();
        }
        int u,v,w;
        for (int i = 1; i <= n; i++) {
            boolean flag = false; // 检测是否出现了变动
            for (int j = 0; j < m; j++) {
                v = edges[j][1];
                u = edges[j][0];
                w = edges[j][2];
                // 因为无负权边，且dis为long数组，避免了溢出情况
                // 不可达点 Integer.MAX_VALUE 加上任何数都不可达
                // 此处无需特判可达性
                if (dis[v] > dis[u]+w) {
                    dis[v] = dis[u]+w;
                    flag = true;
                }
            }
            if (!flag)break; // 没有出现变动则提前跳出循环
        }
        // 根据题意进行的输出
        for (int i = 1; i <= n; i++) {
            System.out.print(dis[i] + " ");
        }
    }
    static int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int)in.nval;
    }
}

🟨 P3385 【模板】负环 - 洛谷

此题目中会出现负权的边，判断从指定出发点是否能到达负环。

下面是 Bellman-Ford 检测负环的方法：

import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while(T--!=0){
            int n = in.nextInt();
            int m = in.nextInt();
            int src = 1; // 表示出发点
            int[] dis = new int[n+1];
            int[][] edges = new int[6002][3]; // 根据题意，最多6000条边
            Arrays.fill(dis, Integer.MAX_VALUE); // 初始化所有顶点不可达
            dis[src] = 0;
            int edgeIdx = 0;
            int u,v,w;
            // 根据题意，单纯存边
            for (int i = 0; i < m; i++) {
                u = in.nextInt();
                v = in.nextInt();
                w = in.nextInt();
                edges[edgeIdx][0] = u;
                edges[edgeIdx][1] = v;
                edges[edgeIdx][2] = w;
                edgeIdx++;
                if(w>=0){
                    edges[edgeIdx][0] = v;
                    edges[edgeIdx][1] = u;
                    edges[edgeIdx][2] = w;
                    edgeIdx++;
                }
            }

            int i;
            boolean flag = false; // 检测是否出现了变动
            for (i = 0; i < n-1; i++) {
                flag = false; 
                for (int j = 0; j < edgeIdx; j++) {
                    u = edges[j][0];
                    v = edges[j][1];
                    w = edges[j][2];
                    // 存在负权图中，不可达点的判断是有必要的
                    if (dis[u]!=Integer.MAX_VALUE && dis[v] > dis[u]+w) {
                        dis[v] = dis[u]+w;
                        flag = true;
                    }
                }
                if (!flag)break; // 没有出现变动则提前跳出循环
            }
            boolean hasNegCir = false;
            // 再进行一次松弛
            for (int j = 0; j < edgeIdx; j++) {
                u = edges[j][0];
                v = edges[j][1];
                w = edges[j][2];
                if (dis[u]!=Integer.MAX_VALUE && dis[v] > dis[u]+w) {
                    dis[v] = dis[u]+w;
                    hasNegCir = true;
                    break;
                }
            }
            System.out.println(hasNegCir?"YES":"NO");
        }
    }
}

同样是这道题，下面是 SPFA 解法，使用到了链式前向星的存储结构：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) {  
        int T = nextInt();
        while(T--!=0){
            int n = nextInt();
            int m = nextInt();
            int src = 1; // 表示出发点
            int[] dis = new int[n+1];
            boolean[] vis = new boolean[n+1]; // 表示是否已加入队列，用于避免重复加入队列
            int[] cnt = new int[n+1];   // 表示结点经过的路径数，用于判断负环
            
            // 链式前向星
            int[] head = new int[n+1];
            Edge[] edges = new Edge[6002]; // 根据题意，最多6000条边，分别表示 to,next,w
            Arrays.fill(head,-1);
            
            Arrays.fill(dis, Integer.MAX_VALUE); // 初始化所有顶点不可达
            Queue<Integer> queue = new LinkedList<>();
            dis[src] = 0;
            queue.offer(src);
            vis[src] = true;
            int edgeIdx = 0;
            int u,v,w;
            // 根据题意，使用链式前向星存边
            for (int i = 0; i < m; i++) {
                u = nextInt();
                v = nextInt();
                w = nextInt();
                edges[edgeIdx] = new Edge(v,head[u],w);
                head[u] = edgeIdx;
                edgeIdx++;
                if(w>=0){
                    edges[edgeIdx] = new Edge(u,head[v],w);
                    head[v] = edgeIdx;
                    edgeIdx++;
                }
            }
            boolean hasNegCir = false;

            while(queue.size()>0&&!hasNegCir){
                u = queue.poll();
                vis[u] = false;
                for (int j = head[u]; j!=-1; j=edges[j].next) {
                    v = edges[j].to;
                    w = edges[j].w;
                    // 存在负权图中，不可达点的判断是有必要的
                    if (dis[u]!=Integer.MAX_VALUE && dis[v] > dis[u]+w) {
                        dis[v] = dis[u]+w;
                        cnt[v] = cnt[u]+1;
                        if(cnt[v]>=n){
                            hasNegCir= true;
                            break;
                        }
                        if(!vis[v]){
                            queue.offer(v);
                            vis[v]=true;
                        }
                    }
                }
            }
            
            System.out.println(hasNegCir?"YES":"NO");
        }
    }
    static int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int)in.nval;
    }
}

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

Dijkstra

🟨 P3371 【模板】单源最短路径（弱化版） - 洛谷

以下代码使用了朴素做法查找下一个遍历的点，并对输入进行了优化以通过全部测试用例，使用到了链式前向星的存储结构：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static final int INF = 0x3f3f3f3f;
    public static void main(String[] args) {
        int n = nextInt();
        int m = nextInt();
        int src = nextInt();
        int[] dis = new int[n+1];
        boolean[] vis = new boolean[n+1]; // 表示 S / T 集合
        Arrays.fill(dis, INF);
        dis[src] = 0;
        
        // 链式前向星
        int[] head = new int[n+1];
        Edge[] edges = new Edge[m]; // 根据题意，最多6000条边，分别表示 to,next,w
        Arrays.fill(head,-1);
        
        // 获取边
        int u,v,w;
        for (int i = 0; i < m; i++) {
            u = nextInt();
            v = nextInt();
            w = nextInt();
            edges[i] = new Edge(v,head[u],w);
            head[u] = i;
        }
        int minDis;
        for(int i=1;i<=n;i++){
            u = src; // 默认为起点，有利于第一次操作时找到它
            minDis = INF;
            // 试图暴力找到下一个 T 集合中的点
            for(int j=1;j<=n;j++){
                if(!vis[j]&& dis[j]<minDis){
                    minDis = dis[j];
                    u = j; // 更新候选点
                }
            }
            vis[u] = true; // 将候选点加入 S 集合
            for(int j = head[u];j!=-1;j=edges[j].next){
                v = edges[j].to;
                w = edges[j].w;
                if(dis[u]+w<dis[v]){
                    dis[v] = dis[u]+w;
                }
            }
        }

        // 构造输出
        for (int i = 1; i <= n; i++) {
            System.out.print((dis[i]==INF? Integer.MAX_VALUE : dis[i]) + " ");
        }
    }
    static int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int)in.nval;
    }
}

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

以下代码是优先队列版本。需要注意的是，优先队列进队时需要将结点 dis 信息绑定进队，这样当 dis 数组发生变化时，优先队列能及时响应变化。

注意到，优先队列会存在一些重复的结点，并携带着过时的 dis 数据。但这并不影响优先队列的正确性。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Queue;
import java.util.PriorityQueue;

public class Main {
    public static final int INF = 0x3f3f3f3f;
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) {
        int n = nextInt();
        int m = nextInt();
        int src = nextInt();
        int[] dis = new int[n+1]; // 即使Node中存有，此数组也要保留，用于支持随机访问
        boolean[] vis = new boolean[n+1]; // 表示 S / T 集合 ，单纯使用vis数组优化内存
        Arrays.fill(dis, INF);
        dis[src] = 0;
        Queue<Node> q = new PriorityQueue<>((o1,o2)->(o1.dis-o2.dis));
        q.offer(new Node(src,0));
        
        // 链式前向星
        int[] head = new int[n+1];
        Edge[] edges = new Edge[m]; // 根据题意，最多6000条边，分别表示 to,next,w
        Arrays.fill(head,-1);
        
        // 获取边
        int u,v,w;
        for (int i = 0; i < m; i++) {
            u = nextInt();
            v = nextInt();
            w = nextInt();
            edges[i] = new Edge(v,head[u],w);
            head[u] = i;
        }
        int minDis;
        Node node;
        while(q.size()>0){
            node = q.poll();
            u = node.id;
            if(vis[u])continue; // 此操作保证不使用重复的结点中过时的dis数据
            vis[u] = true; // 将候选点加入 S 集合
            for(int j = head[u];j!=-1;j=edges[j].next){
                v = edges[j].to;
                w = edges[j].w;
                if(dis[u]+w<dis[v]){
                    dis[v] = dis[u]+w;
                    q.offer(new Node(v,dis[v]));
                }
            }
        }

        // 构造输出
        for (int i = 1; i <= n; i++) {
            System.out.print((dis[i]==INF? Integer.MAX_VALUE : dis[i]) + " ");
        }
    }
    static int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int)in.nval;
    }
}

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

class Node{
    int id;
    int dis; // 用于排序
    // 不需要在此处增加 vis 标记。因为我们的Node会加很多个，可能不止n个！ 
    // 当然，我们可以复用Node进行进一步内存优化
    Node(int id,int dis){
        this.id = id;
        this.dis = dis;
    }
}

本文参考

洛谷 P3371 单源最短路径（Java版）_洛谷3371 java-CSDN博客
最短路 - OI Wiki
【模板】负环问题题解（spfa和bellman解决）_3385 负权环 bellman-CSDN博客
SPFA算法_百度百科
研究生课程《离散数学》笔记

最短路径算法