1. 最短路

1.1. 概念

给定一个有权图，图中有 n 个点和 m 条边，边的权值可正可负，不一定有向。现在给定起点 s 和终点 t，在 s 到 t 的所有路径中，寻找经过的边的权值之和最小的一条路径，这就是最短路问题。

1.2. 多源最短路和单源最短路

多源最短路，指的是一类可能有多组询问且起点和终点均不固定的最短里问题；单源最短路，指的是一类起点固定但终点不固定的最短路问题。

1.3. 算法

通常求解最短路问题，根据类型和图的特性的不同，会采用不同的算法：

2. 多源最短路

2.1. Floyd-Warshall 算法简介

求解多源最短路问题，通常采用 Floyd-Warshall 算法（简称 Floyd 算法），通过基于动态规划的预处理，一次性得到图中任意两个节点的最短路。时间复杂度 $O(n^3)$。

2.2. 算法过程

维护一个三维数组 $f$，定义 $f_{k, i, j}$ 为只经过点 $1 \sim k$，点 $i$ 到点 $j$ 的最短路。第 $k$ 层的状态从第 $k-1$ 层继承而来。若新路径不经过点 $k$，则 $f_{k, i, j} = f_{k-1, i, j}$；反之，若新路径经过点 $k$，则点 $i$ 到点 $j$ 的最短路就是点 $i$ 到点 $k$ 的最短路加上点 $k$ 到点 $j$ 的最短路，随后在两种情况中取较小值，状态转移方程如下：

若点 $i$ 和点 $j$ 有邻边，初始化 $f_{0, i, j}$ 为边长；否则，初始化 $f_{0, i, j}$ 为无穷大。初始化 $f_{0, i, i}$ 为 $0$。为达到初始化目的，可以直接使用邻接矩阵存图。根据上面的状态转移方程求解即可。

2.3. 滚动数组优化

三维数组太费空间了，特别是数据范围较大的时候。我们可以对最外层的 $k$ 使用滚动数组进行优化，压缩到二维。注意到：

又：

所以：

所以，上述状态转移方程中，每个元素更新所用的值并未发生改变，所以可以省略第一维，此时状态转移方程为：

核心代码：

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

除了多源最短路外，Floyd-Warshall 算法也适适用于传递闭包问题和最小环问题。

2.4. 传递闭包问题

传递闭包问题是离散数学中的概念。给定一个集合 $S$ 及集合中若干元素之间的传递关系，求所有元素之间的传递关系。在图论中，传递闭包问题被转化为如下的一个问题：给定一个有向图，求所有点对之间的联通性问题。

有了多源最短路问题的铺垫，我们很容易列出如下的状态转移方程：

其中 $f_{i,j}$ 代表从点 $i$ 出发是否能够到达点 $j$ ，$\land$ 是合取（逻辑与）符号。在实际代码中，我们可以先判断 $f_{i, k}$ 是否为真，若其为假，则无需继续枚举 $j$。 核心代码如下：

for (int k=1; k<=n; k++) {
    for (int i=1; i<=n; i++) {
        if (f[i][k])
            for (int j=1; j<=n; j++) {
                if (f[k][j]) f[i][j] = 1;
            }
    }
}

或者也可用位运算进行操作，这里不再叙述。

2.5. 最小环问题

给定一个图，求其中由 $n (n > 3)$个节点构成的边权最小的环的大小。这便是最小环问题。图的最小环也叫作图的围长。

我们分析：选定最小环上两点 $i$ 和 $j$，则该环是由 $i$ 和 $j$ 之间不经过点 $k$ 的最短路和经过点 $k$ 的最短路构成的。记 $f_{k, i,j}$ 为只经过点 $1 \sim k$，点 $i$ 到点 $j$ 的最短路，$w_{i, j}$为 $i$ 到 $j$ 的直接距离，可以得出以下的状态转移方程：

核心代码请读者自行编写，该问题也可使用滚动数组优化。

3. 单源最短路

3.1. Dijkstra 朴素算法

Dijkstra 算法是求解单源最短路问题最常用的算法，基本思想是贪心。Dijkstra 朴素算法通常用于稠密图，堆优化算法通常用于稀疏图。算法的基本过程是，每次确定一个到源点最近的点 $t$，用 $t$ 更新最短路，重复 $n$ 次即可。使用邻接矩阵存图。时间复杂度为 $O(n^2)$。核心代码（其中 $dis_i$ 代表起始点 $s$ 到点 $i$ 的最短路长度）：

memset(dis, 0x3f, sizeof dis);
dis[s] = 0;

for (int i=1; i<=n; i++) {
    int t = -1;
    for (int j=1; j<=n; j++) {
        if (!vis[j] && (t == -1 || dis[t] > dis[j])) {
            t = j;
        }
    }

    vis[t] = 1;
    for (int j=1; j<=n; j++) {
        dis[j] = min(dis[j], dis[t] + g[t][j]);
    }
}

3.2. Dijkstra 堆优化算法

我们借助堆对上述过程进行优化。首先将起始点压入堆中，随后循环执行下面操作，直到堆空：取出并弹出堆顶 $u$，则该点就是上面要找的 $t$ 点，用点 $u$ 更新临界点的距离，若更新了就将被更新的点压入到堆中。数据结构定义如下：

struct edge {
    int v, w;
};
struct node {
    int dis, u;
    bool operator<(const node &b) const {
        return dis > b.dis;
    }
};

const int N = 5e5 + 100;
int n, m, s, dis[N];
bool vis[N];
vector<edge> g[N];
priority_queue<node> pq;

核心代码如下：

memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
pq.push({0, s});

while (!pq.empty()) {
    int u = pq.top().u;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = 1;

    for (const auto &p : g[u]) {
        int v = p.v, w = p.w;
        if (dis[v] > dis[u] + w) {
            dis[v] = dis[u] + w;
            pq.push({dis[v], v});
        }
    }
}

时间复杂度 $O((m+n) \log n)$。

3.3. Bellman-Ford 算法

Dijkstra 算法不能处理负权边。为此，我们可以使用 Bellman-Ford 算法。Bellman-Ford 算法是一种基于动态规划和松弛算法的最短路算法。我们对图上的每一条边进行松弛。每进行一轮循环，就对所有边进行一次松弛操作：对于一条边 $\{u, v, w\}$， $dis_v = \min\{dis_v, dis_u + w_{u, v}\}$。而当某一次操作没有进行任何松弛操作时，代表已经求解完成，即可直接停止（类似于冒泡排序的优化）。最坏时间复杂度 $O(nm)$。如果存在负环，松弛操作会一直进行，所以该算法可以用来判断负环。请读者自行完成代码。

3.4. SPFA 算法

SPFA 算法（Shortest Path Faster Algorithm）是使用队列优化的 Bellman-Ford 算法，其优化步骤在于：只有上一次被松弛操作所连接而影响到的边，才有可能引起松弛操作，于是我们可以用队列来维护节点。核心代码如下：

memset(dis, 0x3f, sizeof dis);
vis[1] = 1;
dis[1] = 0;
q.push(1);

while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (const edge &i : g[u]) {
        int v = i.v, l = i.l;
        if (dis[v] > dis[u] + l) {
            dis[v] = dis[u] + l;
            vis[v] = 1;
            q.push(v);
        }
    }
}

4. 总结

最短路算法是图论中一类常用的算法，在 GESP 七 ~ 八级以及 NOI 系列赛事中也有涉及。学习最短路算法，能够更好地帮助我们完成图论相关题目。