第十章 最短路
最短路是图论中最经典的模型之一，在生活中也有很多应用。
除了解决给定图的最短路问题，最短路模型还可以解决许多看起来不是图的问题。如果解决一个问题的最佳方案的过程中涉及很多状态，这些状态是明确的且数量合适，而且状态之间可以转移，可以考虑建立图论模型，使用最短路算法求解。
单源最短路径
例1：P3371 【模板】单源最短路径（弱化版）
解法 $1$：$\text{Dijkstra}$ 算法。
- 将起始点的 $dis$ 置 $0$；
- 选择当前为标记的点中 $dis$ 值最小的一个；
- 对该点的所有连边依次进行松弛操作；
- 对该点进行标记；
- 重复第二步置第四步，直到不存在一条从已标记点通往未标记点的连边。
void Dijkstra(int s) {
std::priority_queue<Vertex> q;
for (int i = 1; i <= n; i++) vertex[i].dis = inf;
vertex[s].dis = 0;
q.push(vertex[s]);
while (!q.empty()) {
int u = q.top().vertex;
q.pop();
if (vertex[u].vis) continue;
for (int e = vertex[u].head; e; e = edge[e].next) {
int v = edge[e].head;
int w = edge[e].weight;
if (vertex[v].dis > vertex[u].dis + w) {
vertex[v].dis = vertex[u].dis + w;
q.push(vertex[v]);
}
}
}
return;
}
如果是无向图，每加入一条边，都可以认为是加入两条方向相反的有向边。这个时候需要特别注意，链式前向星需要定义的数组元素数量上限，需要超过边数的两倍。
由于每条边最多被入堆、出堆一次，而且堆内元素最多为 $m$ 个，其时间复杂度为 $\mathcal O(m \log m)$。
$\text{Dijkstra}$ 算法的优势是时间复杂度较低，缺点是一旦边长出现负数其正确性就无法保证。
解法 $2$：$\text{SPFA}$ 算法。
- 将起始点的 $dis$ 置 $0$ 并放入队列；
- 选择当前队列中的第一个点并将其从队列中删除；
- 对该点的所有连边依次进行松弛操作；
- 将第三步中松弛成功且不在队列内的点放入队列；
- 重复第二步置第四步，直到队列为空。
void SPFA(int s) {
std::queue<int> q;
for (int i = 1; i <= n; i++) vertex[i].dis = inf;
vertex[s].dis = 0;
vertex[s].inq = true;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
vertex[u].inq = false;
for (int e = vertex[u].head; e; e = edge[e].next) {
int v = edge[e].head;
int w = edge[e].weight;
if (vertex[v].dis > vertex[u].dis + w) {
vertex[v].dis = vertex[u].dis + w;
if (!vertex[v].inq) {
q.push(v);
vertex[v].inq = true;
}
}
}
}
return;
}
在 $\text{SPFA}$ 的过程中会有一个点可能多次入对，这使寻找最短路的效率大大降低。实际上，$\text{SPFA}$ 的时间复杂度在最劣情况下可以达到 $\mathcal O(nm)$，因此只要数据稍大且构造特定图就可能超时，但它在随机数据下速度较快，且当边长出现负数时依然正确。因此在算法竞赛中，如果确定图中边长非负且没有特殊的限制时，不应使用 $\text{SPFA}$ 算法。
例2：P4568 [JLOI2011] 飞行路线
由于购买机票需要花费金钱，所以肯定不会重复乘坐多次同样的航线或者多次访问同一个城市。如果 $k = 0$，本题就是最基本的最短路问题。但题目中提供了一些特殊的情况（对有限条边设置为免费），可以使用分层图的方式。将图多复制 $k$ 次，原编号为 $i$ 的结点复制为编号 $i + jn (1 \le j \le k)$ 的结点，然后对于原图存在的边，第 $j$ 层第 $j + 1$ 层的对应结点也需要连上，看起来就是相同的图上下堆叠起来，因此被称为分层图。
从上面一层跳到下面一层就是乘坐免票的飞机，花费的代价是 $0$。这个过程时不可逆的，每乘坐一次飞机就跳到下一层图中，因此上一层到下一层到边是单向边。从编号为 $s$ 到结点开始，计算到其他结点的单源最短路径。因为并不一定要坐满 $k$ 次免费航班，所以查找所有编号 $t + jn (0 \le j \le n)$ 的结点，找到最小的值就是的答案。
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
graph::addEdge(a, b, c);
graph::addEdge(b, a, c);
for (int j = 1; j <= k; j++) {
graph::addEdge(j * n + a, j * n + b, c);
graph::addEdge(j * n + b, j * n + a, c);
graph::addEdge((j - 1) * n + a, j * n + b, 0);
graph::addEdge((j - 1) * n + b, j * n + a, 0);
}
}
graph::Dijkstra();
for (int i = 0; i <= k; i++) ans = std::max(ans, graph::vertex[t + i * n].dis);
例3：P1629 邮递员送信
由于邮递员必须每次都要从结点 $1$ 出发，到达结点 $i$，然后返回 $1$，因此就是求从 $1$ 到 $i$ 的最短路，加上 $i$ 到 $1$ 的最短路。考虑到是有向图，从 $1$ 到 $i$ 的距离不一定等于从 $i$ 到 $1$ 的距离。于是可以建立另外一个图，将读入的边起点和终点对调后存入这个新图中，从 $1$ 开始计算到其他点的单源最短路径，得到的距离就是其他点到起点到最短路径。一来一回加起来就是送货的最短路径。
for (int i = 1; i <= m; i++) {
int u, v, w;
std::cin >> u >> v >> w;
graph::addEdge(u, v, w);
graph::addEdge(n + v, n + u, w);
}
Graph::Dijkstra(1);
Graph::Dijkstra(n + 1);
for (int i = 2; i <= n; i++) ans += Graph::vertex[i].dis;
for (int i = n + 2; i <= n * 2; i++) ans += Graph::vertex[i].dis;
一些最短路相关问题的小技巧：
- 某些边只能走有限的次数，可以将图复制多遍，成为分层图；
- 给出若干个关键点，求其他点离这些关键点的距离，可以建立一个超级源点，并使用长度为 $0$ 的边将超级源点和这些关键点相连；
- 查找有向图中，所有结点到某个节点的最短路，可以将图反向建边；
- 注意图中是否存在负环、自环、重边等情况。
负环与差分约束
例4：P3385 【模板】负环
在图论中边权之和为负数的环称为负环。显然，如果一个连通图中存在一个从顶点 $s$ 出发能到的负环，$s$ 到该负环上的任意一点不存在最短路。
可以从最短路径上点数入手。如果一个点进队超过 $n$ 次，它的当前最短路径上的点数就超过了 $n$ 个点，这就意味着出现了负环。
if (vertex[v].dis > vertex[u].dis + w) {
vertex[v].dis = vertex[u].dis + w;
if (!vertex[v].inq) {
vertex[v].inq = true;
vertex[v].cnt++;
if (vertex[v].cnt >= n) return true;
q.push(v);
}
}
if (vertex[v].dis > vertex[u].dis + w) {
vertex[v].dis = vertex[u].dis + w;
vertex[v].cnt = vertex[u].cnt + 1;
if (vertex[v].cnt >= n) return true;
if (!vertex[v].inq) {
vertex[v].inq = true;
q.push(v);
}
}
例5：P5960 【模板】差分约束算法
对于形如 $x_u - x_v \le y$ 的条件，可以将其转化为 $x_u \le x_v + y$。容易发现这个不等式很像最短路中的 $dis_v \le dis_u + w$。因此可以对于每一组 $x_u - x_v \le y$ 建一条 $v$ 到 $u$ 边权为 $y$ 的边，使途中的边和不等式一一对应，于是问题就被引到了最短路的方向上。
如果出现了形如 $x_i - x_j \ge y$ 的条件，处理方法是在不等式两旁同时乘 $-1$，得到 $x_j - x_i \le -y$。如果出现了形如 $x_i \ x_j = y$，则只需将它拆分成 $x_i - x_j \le y$ 与 $x_i - x_j \ge y$ 两个约束条件进行处理。
for (int i = 1; i <= n; i++) graph::addEdge(0, i, 0);
for (int i = 1; i <= m; i++) std::cin >> c >> c_ >> y, graph::addEdge(c_, c, y);
if (graph::SPFA(0)) std::cout << "NO";
else for (int i = 1; i <= n; i++) std::cout << graph::vertex[i].dis << ' ';
次短路
例6：P2865 [USACO06NOV]Roadblocks G
在任何时刻，如果发现了一条新的从 $1$ 到 $i$ 的路径，则该路径可能存在以下几种情况：
- 该路径长度小于目前的 $1$ 到 $i$ 的最短路。此时的处理方法是将目前的次短路用目前的最短路代替，而最短路替换为新路径；
- 该路径长度等于目前的最短路，直接舍去；
- 该路径长度大于目前的最短路且小于目前的最短路。此时的处理方式是直接用这条路径替换当前的次短路径；
- 该路径长度大于或等于目前的次短路。
由于只有最短路和次短路有效，因此这个点的所有可能的有效路径全部都在优先队列中。当这个点第一次从优先队列中出来时，其最短路值就不会再被更改；第二次从优先队列中出来时，其次短路值就不会再更改。
for (int e = vertex[u].head; e; e = edge[e].next) {
int v = edge[e].head;
int w = edge[e].weight;
if (vertex[v].dis1 > d + w) {
vertex[v].dis2 = vertex[v].dis1;
vertex[v].dis1 = d + w;
q.push((Node) {v, vertex[v].dis1});
}
if (vertex[v].dis2 > d + w && vertex[v].dis1 < d + w) {
vertex[v].dis2 = d + w;
q.push((Node) {v, vertex[v].dis2});
}
}
多源最短路径与传递闭包
例7：P2910 [USACO08OPEN]Clear And Present Danger S
对于多源最短路，可以使用 $\text{Floyd-Warshall}$ 算法更便捷地解决此类问题。
$\text{Floyd}$ 算法既可以处理无向图，也可以处理有向图，注意设置 $dis$ 的初始值即可。
例8：B3611 【模板】传递闭包
许多算法竞赛题目看起来和图没什么关系，但是如果可以找到状态结点和连接不同结点的边，也可以将其建立图模型，使用图论算法解决。