lessons/课程/05-最短路与类最短路/03-最短路树次短路与差分约束.md

类最短路：最短路树、严格次短路与差分约束

本节目标

学完后，你应能在最短距离之外优化前驱树，维护每点前两种不同到达长度，并把形如 $x_v-x_u\le c$ 的约束转成有向边，理解“求最大值却跑最短路”的对偶含义。

前置知识与课前自测

前置：Dijkstra、树、Bellman-Ford、负环。

1. 每个点任选一条满足 dist[u]+w=dist[v] 的边，是否一定形成树？需要什么边权条件？
2. “第二短”是否把另一条与最短路等长的路线算进去？
3. 约束 $x_B-x_A\ge D$ 怎样改写成 <= 形式？

自测答案

1. 正权时距离沿父边严格下降，必回到源且无环；零权时可能形成等距环，需额外处理。 2. 依题意。本节 `Roadblocks` 要求长度严格大于最短路，等长不同路线不算。 3. $x_A-x_B\le-D$，建边 $B\to A$ 权 $-D$。

问题动机

“类最短路”并非换一个模板，而是仍使用松弛语言处理不同目标：

• 距离固定后，在所有最短前驱中选附加代价最小者；
• 每个点保留两个不同距离标签；
• 把不等式的传递上界看作路径权和。

关键是明确标签语义、比较顺序和能丢弃哪些候选。

核心知识与实现指南

• 多目标比较要先固定主目标：只有主距离相等时才比较父边权。
• 多标签最短路必须明确“等长是否算不同一档”；本节次短标签使用严格不等式。
• 差分约束统一成 x_v <= x_u + c 后再建边，负号和方向同时从公式读取。
• 负边图不能使用 Dijkstra；规模允许时，确定性的 Bellman-Ford 比未经证明的 SPFA 复杂度更可靠。

精选例题 1：Paths and Trees

来源信息与题意

• VJudge：CodeForces-545E Paths and Trees
• 原题：Codeforces Round 303 (Div. 2)
• 难度：2000；考点：最短路树、相等距离的次级目标

连通简单带权无向图有 $n,m\le3\times10^5$、正权至 $10^9$，给源点 $s$。在保持 $s$ 到每点距离都与原图最短距离相同的生成树中，最小化树边权总和，并输出边编号。

Hint 1

先求距离；对每个 $v\ne s$，父边必须满足 `dist[u]+w=dist[v]`。

Hint 2

正权使父亲距离严格小于儿子，所以各点独立选父边不会成环。

Hint 3

Dijkstra 松弛距离相等时，若新边权更小，只替换父边，不必重新入堆。

Observations、Editorial 与证明

对每个非源点，从所有最短前驱边中选权值最小者。由于权值为正，沿父边距离严格下降，最终到源点且不成环；每点恰一条父边，因此组成生成树。任一最短路树也必须为每点选一条最短前驱边，而总权是这些独立选择之和，所以逐点取最小达到全局最小。

Dijkstra 中严格变短时更新距离和父边；相等时只比较父边权。复杂度 $O((n+m)\log n)$。

核心伪代码与参考实现附件

run Dijkstra from source
on shorter distance to v: replace distance and parent edge
on equal distance: replace parent edge only if its own weight is smaller
because all weights are positive, chosen parents strictly decrease distance
output sum and IDs of one chosen parent edge for every non-source vertex

完整 GNU C++17 参考实现见附件：CodeForces-545E.cpp

复盘与变式

若有零权边，逐点独立选最小父边可能在同距离点之间成环；需在等距零权子图中额外构造连向较小距离层的森林。

精选例题 2：Roadblocks

来源信息与题意

• VJudge：POJ-3255 Roadblocks
• 原来源：USACO 2006 November Gold
• 大致难度：提高；考点：每点两标签、严格次短路

无向正权图有 $N\le5000,R\le10^5$，边权 $1..5000$。求 1 到 $N$ 的严格第二短路线长度；路线允许重复经过边和点。若有多条等长最短路，它们仍只占“最短长度”这一档。

Hint 1

为每点维护最短 `first[v]` 与严格更大的次短 `second[v]`。

Hint 2

候选比最短还小时，先把旧最短交换出来，它仍可能更新次短。

Hint 3

只有 `first[v] < candidate < second[v]` 才更新次短；等于最短的候选丢弃。

Observations、Editorial 与证明

优先队列中的标签既可能是最短也可能是次短。松弛到 $v$ 时，若候选成为新最短，把旧最短继续作为次短候选；否则仅在严格介于两者时更新次短。

任一到达 $v$ 的第三种或更长标签，后接任意正权后缀仍不可能优于从同点的前两种标签接该后缀，所以可丢弃。目标点的第二标签即全局严格第二短。复杂度 $O((N+R)\log N)$。

核心伪代码与参考实现附件

first[source] = 0; second[*] = infinity
pop a distance label d at u
for edge u-v:
    candidate = d + weight
    if candidate < first[v]: swap(candidate, first[v]); push first[v]
    if first[v] < candidate < second[v]: set and push second[v]
output second[destination]

完整 GNU C++17 参考实现见附件：POJ-3255.cpp

复盘与变式

若题目禁止重复点，变成简单路径的第二短问题，不能直接使用本算法；允许回走是两标签支配性成立的重要背景。

精选例题 3：Layout

来源信息与题意

• VJudge：POJ-3169 Layout
• 原来源：USACO 2005 December Gold
• 大致难度：省选入门；考点：差分约束、负环、无上界

$2\le N\le1000$ 头牛按编号顺序站在数轴上，允许重合。至多 $10^4$ 条喜欢约束要求 $A,B$ 距离不超过 $D$，至多 $10^4$ 条讨厌约束要求距离至少 $D$，$A<B$。求满足约束时 $x_N-x_1$ 的最大值；无解输出 -1，无上界输出 -2。

Hint 1

统一写成 `x_v <= x_u + c`，对应边 `u -> v` 权 `c`。

Hint 2

编号顺序给出 `x_i <= x_{i+1}`，即边 `i+1 -> i` 权 0。

Hint 3

喜欢：`A->B (D)`；讨厌：`B->A (-D)`。

Hint 4

任意路径给出 $x_N-x_1$ 的上界，最紧上界是 1 到 N 的最短路；负环表示约束矛盾，不可达表示没有上界。

Observations

1. 最短路不是在计算实际走路，而是在传递“变量最多是多少”的上界。
2. 从 1 不可达的负环仍会让整个约束系统无解，所以要先用所有点为源检测全局负环。
3. “最大可行距离”由所有上界中最紧者决定，因此数值上是最短路径。

Editorial 与证明

建立差分约束图。先把所有距离初始化为 0，做 $N$ 轮 Bellman-Ford；第 $N$ 轮仍能松弛则有负环，沿环相加得到 $0<负数$ 的矛盾，输出 -1。

再令 dist[1]=0、其余无穷，做至多 $N-1$ 轮松弛。每条从 1 到 $N$ 的路径都推出 $x_N-x_1\le$ 路径权，故最短路是最紧上界；无负环时最短距离标签本身满足所有可达约束，未达变量可平移安排，所以上界可达。若 $N$ 不可达，没有任何约束链限制两者距离，输出 -2。

边数不超过约 $2.1\times10^4$，确定性的 Bellman-Ford 为 $O(NE)$。先用 $N$ 轮从超级源检测全局负环（约 $2.1\times10^7$ 次松弛），再用 $N-1$ 轮求最短路（约 $2.1\times10^7$ 次松弛），合计约 $4.2\times10^7$ 次，可接受。

核心伪代码与参考实现附件

convert every constraint to x[v] <= x[u] + weight and add edge u->v
add order edges (i+1)->i with weight 0
if Bellman-Ford from a super-source finds a negative cycle: output -1
dist = Bellman-Ford(source=1)
if N is unreachable: output -2
else: output dist[N], the tightest upper bound on x[N]-x[1]

完整 GNU C++17 参考实现见附件：POJ-3169.cpp

复盘与变式

若要求一组具体坐标，可从可行势能恢复并整体平移；若额外规定 $x_1=0$ 且所有变量有上下界，把这些边一并加入超级源系统即可。

扩展与联系

• 最短路 DAG 上可计最短路条数、判必经边；有零权边时先处理等距环。
• 第 $k$ 短路线不能为每点简单保留固定两个标签；通常需 A*、可持久化堆或专门的 k-shortest 算法，并明确是 walk、trail 还是 simple path。
• 差分约束与势能重标号相连：无负环时，最短距离是一组满足三角不等式的势能。

总结与自检

1. 最短路树中相等距离时优化了什么？为何可逐点独立？
2. 次短标签为何必须严格大于最短标签？
3. 第三到达标签为何不会产生目标的第二短路线？
4. 差分约束的边方向怎样从公式读出？
5. 为什么最大可行差值等于最短路径上界？

课后训练建议

第一题对拍所有小图生成树，确认总权最小；第二题用允许回走的朴素优先队列枚举前若干路径长度对拍；第三题每条约束先手写不等式再建边，禁止靠背方向。复盘分别记录三个标签的语义：距离、父边权、第一/第二距离、变量上界。