简介

现在给你 $n$ 个节点（编号为 $1\cdots n$）和它们之间的边长，求任意两个节点之间的最短路径。

松弛操作

使用 邻接矩阵 $g$ 存图。如果 $g[i,k]+g[k,j]<g[i,j]$，则路径 $i\to k\to j$ 比原先 $i$ 到 $j$ 的路径更短，那么就令 $g[i,j]=g[i,k]+g[k,j]$。这就是松弛操作。

@LR;
ranksep=0.7;
i -> k[@n="g[i,k]"]
k -> j[@n="g[k,j]"]
i -> j[label="g[i,j]", constraint=false]

Floyed 算法

一开始，我们将所有节点全部拨到图外面，然后按 $1$ 号到 $n$ 号顺序依次往图中加入节点。

$g[k,i,j]$：当图中已经加入了 $1\cdots k$ 号节点时，从节点 $i$ 到 $j$ 的最短路径。

当节点 $k$ 被加入图中时，枚举节点 $i$ 和 $j$，利用新加入的 $k$ 对路径 $i-j$ 进行 松弛操作：

• 若路径 $i-j$ 不经过节点 $k$，则 $g[k,i,j]=g[k-1,i,j]$；
• 若路径 $i-j$ 经过节点 $k$，则 $g[k,i,j]=g[k-1,i,k]+g[k-1,k,j]$。

$$g[k,i,j]=min\{g[k-1,i,j],g[k-1,i,k]+g[k-1,k,j]\}$$

for (int k = 1; k <= n; k ++)
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            g[k][i][j] = min(g[k - 1][i][j], g[k - 1][i][k] + g[k - 1][k][j]);

实际上，$g$ 数组的第一维不影响结果，可以摘掉。

for (int k = 1; k <= n; k ++)
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

Floyed 算法适用于任何图，但图中必须存在最短路。时间复杂度为 $O(n^3)$。

Bellman-Ford 算法

Bellman-Ford 算法是基于 Floyed 算法 的优化版本，但是只能处理「单源最短路径」：每跑一次 Bellman-Ford，都需要给定源节点 $s$，并且只能求得 $s$ 到其它节点的最短路长度。

Floyed 枚举节点的效率太低，于是 Bellman-Ford 改为枚举边。

$n$ 个节点 $m$ 条边的图中，如果存在最短路径，则最短路径所包含的边数 $\le n-1$。故每条路最多被松弛 $n-1$ 次。

$\mathrm{dis}[i]$ 表示 $s$ 到 $i$ 的最短路长度，初始时要设为正无穷。

时间复杂度为 $O(nm)$。

void bellman_ford(int s) {
    memset(dis, 0x7f, sizeof dis);
    for (int i = 1; i < n; i ++) // 松弛 n - 1 次
        for (int j = 1; j <= m; j ++)
            dis[to[j]] = min(dis[to[j]], dis[from[j]] + len[j]);
}

判断负权回路

若图中存在长度为负数的 回路，则此回路称为 负权回路（负环）。

有负权回路的图不存在最短路。

在 Bellman-Ford 运行时，如果存在一条路径被松弛了 $n$ 次或更多，则一定存在负权回路。

bool check(int s) {
    memset(dis, 0x7f, sizeof dis);
    for (int i = 1; i < n; i ++)
        for (int j = 1; j <= m; j ++)
            dis[to[j]] = min(dis[to[j]], dis[from[j]] + len[j]);
    for (int j = 1; j <= m; j ++)
        if (dis[to[j]] > dis[from[j]] + len[j])
            return false; // 松弛了 n - 1 次后，还能进行松弛操作，则存在负权回路
    return true;
}

SPFA 算法

SPFA 算法是 Bellman-Ford 算法 的队列优化版本。其基本思想是：

• 只有上一次被松弛的节点的出边，才有可能引起下一次的松弛操作。

每次取队首节点，对其出边进行松弛，将松弛到的节点加入队列。

时间复杂度为 $O(kn)$。平均情况下，$k$ 为 $(1,2)$ 中的常数。

const int N = 1e6;
bool in[N], dis[N]; // in[i]: u 是否在栈中 
struct node {
    int val, len;
};
vector<int> g[N]; // g[u]: u 节点的邻接节点集合

void spfa(int s) {
    memset(in, false, sizeof in);
    memset(dis, 0x7f, sizeof dis);
    dis[s] = 0;
    queue<int> Q;
    Q.push(s), in[s] = true;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop(), in[u] = false;
        for (int i = 0; i < (int) g[u].size(); i ++) {
            int v = g[u][i].val;
            int d = g[u][i].len;
            if (dis[v] > dis[u] + d) {
                dis[v] = dis[u] + d;
                if (!in[v]) { // 已经在栈里的节点没必要再进栈一次
                    Q.push(v), in[v] = true;
                }
            }
        }
    }
}

判断负权回路

const int N = 1e6;
bool in[N], dis[N], relax[N]; // relax[u]: dis[u] 被松弛的次数
struct node {
    int val, len;
};
vector<int> g[N];

bool spfa(int s) {
    memset(in, false, sizeof in);
    memset(dis, 0x7f, sizeof dis);
    dis[s] = 0;
    queue<int> Q;
    Q.push(s), in[s] = true;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop(), in[u] = false;
        for (int i = 0; i < (int) g[u].size(); i ++) {
            int v = g[u][i].val;
            int d = g[u][i].len;
            if (dis[v] > dis[u] + d) {
                dis[v] = dis[u] + d;
                if (++ relax[v] >= n) // 松弛了 n 次及以上，存在负权回路
                    return false;
                if (!in[v]) {
                    Q.push(v), in[v] = true;
                }
            }
        }
    }
    return true;
}

Dijkstra 算法

从节点 $s$ 出发。首先把所有节点分成两个集合：已确定最短路长度的，和未确定的。一开始只有 $s$ 在第一个集合，且 $\mathrm{dis}[s]=0,\mathrm{dis}[$其他节点$]=+\mathrm{\infty }$。

重复以下操作直到第二个集合中没有节点：

1. 松弛刚加入第一个集合的节点的所有出边；
2. 从第二个集合中，选取 $\mathrm{dis}$ 值最小的节点，加入第一个集合。

只能处理单源最短路径，不能处理负权路径。时间复杂度为 $O(n^2)$。

const int N = 1e6;
int avl[N], dis[N];

void dijkstra(int s) {
    memset(avl, true, sizeof avl);
    memset(dis, 0x7f, sizeof dis);
    dis[s] = 0;
    for (int i = 1; i <= n; i ++) {
        int minn = INF, minp = 0;
        for (int j = 1; j <= n; j ++)
            if (avl[j] && dis[j] < minn)
                minn = dis[j], minp = j;
        if (!minp) continue;
        avl[minp] = false;
        for (int j = 1; j <= n; j ++)
            if (avl[j] && dis[j] > minn + g[minp][j])
                dis[j] = minn + g[minp][j];
    }
}