4.4 Shortest Paths：松弛、Dijkstra、DAG与Bellman-Ford

4.4 · Shortest Paths覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“4.4 · Shortest Paths”如何以松弛为统一操作，按非负权、DAG 或一般权重前提选择 Dijkstra、拓扑序或 Bellman-Ford
能逐项核对最短路径、加权有向图、松弛、Dijkstra算法、无环图最短路径、Bellman-Ford算法与负权环，并区分作者站内容与本页独立补充
能按“relax(v→w)：若 dist[w] > dist[v]+weight(v,w)，同时更新 dist[w] 与 edgeTo[w]”手算一个最小输入，逐步检查“所有边满足三角不等式，edgeTo 紧边链从可达顶点回到源点且路径权重等于 dist”
能注入“在存在可达负权边时仍把 Dijkstra 出队顶点永久 settle，或只更新 dist 不更新 edgeTo”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“4·4 · Shortest Paths”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“4·4 · Shortest Paths”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“4·4 · Shortest Paths”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：4.4 · Shortest Paths

1. 最短路径：在本页通过“初始化源点标签”连接解释、交互状态和练习验收。
2. 加权有向图：在本页通过“选择待松弛顶点”连接解释、交互状态和练习验收。
3. 松弛：在本页通过“计算候选距离”连接解释、交互状态和练习验收。
4. Dijkstra算法：在本页通过“更新标签与前驱”连接解释、交互状态和练习验收。
5. 无环图最短路径：在本页通过“验证路径或负环”连接解释、交互状态和练习验收。
6. Bellman-Ford算法与负权环：在本页通过“初始化源点标签”连接解释、交互状态和练习验收。

从“到达同一点的两条路线，哪条才值得保留”开始

导航、网络路由、任务调度与货币兑换都在问同一个问题：从source s出发，到target t的所有directed paths中，哪一条total weight最小？最短路径（shortest paths）并不是“边最少”的路径；weight可以表示距离、时间、费用、风险或损失。

先预测：已知从s到v的best known distance为0.7，edge v→w权重0.2，而当前distTo[w]是1.3，应该改成多少？候选path为0.9，因此同时把distTo[w]改成0.9，并把edgeTo[w]改成v→w。若只改distance不改predecessor，之后无法重建certificate；若只改predecessor不改distance，两者不再相等。

本节的统一核心不是某个priority queue，而是松弛（relaxation）。Dijkstra's algorithm、acyclic shortest paths与Bellman-Ford algorithm只是在不同输入前提下安排relaxation order，并决定何时可以宣布某个label最终正确。

DirectedEdge = 2→1@0.10

from()

to()

weight()

0.10

adj(2) = 2→1@0.10 · 2→3@0.90 · 2→4@0.80

DirectedEdge只有from端的outgoing adjacency list持有它；direction与weight都是path contract的一部分。

4.4.1 Edge-weighted digraphs：direction决定path能否继续

加权有向图（edge-weighted digraphs）把edge表示为ordered triple ((v,w,weight))。与4.3的undirected Edge不同，DirectedEdge不提供 either/other，而是明确提供 from/to：

public final class DirectedEdge {
    private final int v;
    private final int w;
    private final double weight;
 
    public DirectedEdge(int v, int w, double weight) {
        if (v < 0 || w < 0) throw new IllegalArgumentException();
        if (Double.isNaN(weight)) throw new IllegalArgumentException();
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
    public int from() { return v; }
    public int to() { return w; }
    public double weight() { return weight; }
}

EdgeWeightedDigraph.addEdge(e)只把e加入 adj[e.from()]，因为从vertex v做vertex relaxation时只应scan outgoing edges。Indegree可另存以支持topological sorting：

public void addEdge(DirectedEdge e) {
    int v = e.from();
    int w = e.to();
    validateVertex(v);
    validateVertex(w);
    adj[v].add(e);
    indegree[w]++;
    E++;
}

Adjacency-list space为Theta(V+E)，遍历 adj(v) 成本与outdegree(v)成正比。Parallel edges与self-loops可以存在；算法比较的是edge objects及其weights，而不应只用endpoint pair作唯一key。

Shortest-path input的边界必须先说清：

Path必须遵循edge direction；v能到w不代表w能到v。
Target可能从source不可达，此时distTo是positive infinity，pathTo不存在。
Multiple shortest paths可以同权；返回任意一条即可，除非client额外规定tie-break。
Zero-weight cycle无需出现在simple shortest path中。
Negative edge不一定让问题无解；reachable negative cycle才会让某些distances没有finite minimum。

4.4.2 Shortest-path tree：distTo是数值，edgeTo是可复查结构

给定source s，shortest-path tree（SPT）由两个vertex-indexed arrays表示：

distTo[v]：当前已知s到v的minimum path weight上界。
edgeTo[v]：实现当前distTo[v]的最后一条directed edge。

初始化为：

distTo[s]=0,\qquad distTo[v]=+\infty\quad(v\ne s),\qquad edgeTo[v]=null

若v可达且不是source，沿 edgeTo[v].from() 反复回溯应最终到s；逆序这些edges得到source-to-v path。Path reconstruction的cost与输出path length成正比：

public Iterable<DirectedEdge> pathTo(int v) {
    if (!hasPathTo(v)) return null;
    Stack<DirectedEdge> path = new Stack<>();
    for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])
        path.push(e);
    return path;
}

edgeTo不是随便一组parents。对每个reachable non-source vertex v，parent edge必须进入v，并满足tight equality：

distTo[v]=distTo[e.from()]+e.weight(), \qquad e=edgeTo[v]

这条等式让数字label与具体path互相认证。若出现predecessor cycle，或回溯停在非source vertex，candidate结构无效。

4.4.3 Relaxation：把global optimum拆成local inequality

Relax edge (e=v\to w) 时，已有s到v的best known path，再接e得到s到w的candidate。只有strictly better时才更新：

private void relax(DirectedEdge e) {
    int v = e.from();
    int w = e.to();
    double candidate = distTo[v] + e.weight();
    if (distTo[w] > candidate) {
        distTo[w] = candidate;
        edgeTo[w] = e;
    }
}

数学上，successful relaxation修复一条被违反的triangle inequality：

distTo[w]\le distTo[v]+w(v,w)

Vertex relaxation只是依次relax某个v的全部outgoing edges。若distTo[v]仍是infinity，所有candidate仍是infinity，不会产生伪reachability。

为什么local inequalities足以认证global shortest paths？任取从s到t的path (s=v_0\to v_1\to\cdots\to v_k=t)。若所有edges都满足inequality，逐项相加可得：

distTo[t]\le \sum_{i=0}^{k-1}w(v_i,v_{i+1})

所以distTo[t]不大于任何path weight；而tight edgeTo chain又提供一条weight恰为distTo[t]的真实path，两边夹住，distTo[t]就是shortest distance。算法构造完后，可用这一证明做独立validator，而不必重演其内部control flow。

4.4.4 Generic relaxation：正确性来自“没有可改善edge”

最宽泛的single-source算法可以反复relax任意edge，直到一整轮没有successful update。若输入中不存在source-reachable negative cycle，distances会逐步下降到最短值；但任意schedule可能做大量无效工作。

Optimal substructure解释edgeTo为何可组成tree：若s到t的shortest path经过v，那么path上s到v的prefix也必须是shortest path。否则用更短prefix替换，就会得到更短的s到t path，矛盾。

不同算法通过输入结构减少“还需再看哪些edges”的不确定性：

input promise	relaxation schedule	finalize rule	worst-case time
nonnegative weights	minimum distTo first	delMin后settled	(O(E\log V))
edge-weighted DAG	topological order once	order经过即完成	(\Theta(V+E))
no reachable negative cycle	repeated / changed queue	no update or cycle certificate	(O(VE))

不存在一个不检查前提就能套用的“万能最快版本”。算法选择本身是correctness contract。

4.4.5 Dijkstra's algorithm：minimum label何时可以settle

Dijkstra算法（Dijkstra's algorithm）初始化source key为0，其余为infinity。IndexMinPQ只保存尚未settled且有finite label的vertices；每轮 delMin 得到v，relax adj(v)，successful update执行 decreaseKey 或首次insert。

distTo[s] = 0.0;
pq.insert(s, 0.0);
while (!pq.isEmpty()) {
    int v = pq.delMin();
    for (DirectedEdge e : G.adj(v)) {
        int w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
            else pq.insert(w, distTo[w]);
        }
    }
}

正确性关键是nonnegative weights。设v是当前minimum-key non-tree vertex。任何尚未被发现、之后绕回v的path，必须先从settled set跨到某个unsettled x；到x的prefix不小于当前minimum distTo[v]，后续nonnegative edges又不能降低weight，所以无法产生更短的s-to-v path。于是v一经 delMin 就可settle。

每条edge最多引发一次relaxation attempt；每个vertex最多一次insert与delMin，successful improvement触发decreaseKey。Binary-heap IndexMinPQ给出：

T_{\mathrm{Dijkstra}}=O((V+E)\log V)=O(E\log V)

最后一步使用connected reachability相关的 (E\ge V-1)；不连通部分根本不进PQ。Extra space为Theta(V)加graph storage。

Dijkstra不是Prim

两者都使用IndexMinPQ，却优化不同key：

Dijkstra key是source-to-v整个path的distTo[v]。
Eager Prim key是current tree到v的一条minimum crossing edge weight。

Dijkstra输出shortest-path tree，不保证tree edge total minimum；Prim输出MST，不保证source-to-target tree paths最短。把两者的 distTo 含义混用，会得到看似合理但没有相应certificate的结果。

4.4.6 Acyclic shortest paths：拓扑序让一次扫描足够

无环图最短路径（acyclic shortest paths）不要求weights nonnegative。DAG没有edge返回已完成topological prefix；处理v时，所有进入v的possible predecessor paths都已经处理，所以distTo[v]已最终正确。

distTo[s] = 0.0;
Topological topological = new Topological(G);
if (!topological.hasOrder()) throw new IllegalArgumentException("not a DAG");
 
for (int v : topological.order())
    for (DirectedEdge e : G.adj(v))
        relax(e);

Topological sort加一次all-edge scan，time与extra state为：

T_{\mathrm{DAG-SP}}=\Theta(V+E)

Negative edge安全，是因为它无法参与cycle，后面不会出现“回头改善已完成vertex”。若graph含cycle，任意DFS finish order都不能冒充topological order；必须先给出acyclic certificate。

Longest paths与Critical Path Method

DAG longest paths只需把non-source labels初始化为negative infinity，并把relax inequality反向。General cyclic graph的longest simple path很难，但DAG topological order仍让每条edge只处理一次。

Critical Path Method把precedence-constrained jobs转成edge-weighted DAG：每个job拆为start/end vertices，duration edge从start指向end；precedence constraint用zero-weight edge连接前一job end与后一job start；super-source连所有starts，所有ends连super-sink。Source到job start的longest distance就是earliest start。

Project makespan是source-to-sink longest distance；构成该distance的jobs是critical path。推迟critical job会推迟project finish，而非critical job可能有slack。验收schedule时应逐constraint检查finish(predecessor)不晚于start(successor)，再核对critical path tight equalities。

4.4.7 Negative edges与negative cycles：问题可能没有finite答案

负权环（negative cycle）与单条negative edge不同。Negative edge仍可能有well-defined shortest paths；reachable negative cycle允许path绕行k次：

w(P_k)=w(P_0)+k\,w(C) \longrightarrow -\infty \qquad\text{when }w(C)\lt 0

所以对cycle及其downstream vertices不存在finite shortest path。与source不连通的negative cycle不影响该source的single-source query；检测结论必须带reachability范围。

Shortest path从s到v存在，当且仅当至少有一条s-to-v directed path，并且任何可位于s-to-v route上的vertex都不受reachable negative cycle影响。Unreachable vertex与negative-cycle-affected vertex都没有finite shortest distance，但原因和API结果不同，不能混成同一个infinity状态而不附status。

4.4.8 Bellman-Ford algorithm：允许label被反复修正

Bellman-Ford算法与负权环（Bellman-Ford algorithm and negative cycles）不把vertex永久settle。Generic version按任意顺序relax所有edges，共做V轮；若第V轮仍有successful relaxation，source-reachable predecessor subgraph中存在negative cycle。

Queue-based version观察到：只有distTo刚改变的vertex，其outgoing edges才可能在下一步带来新改进。维护FIFO queue与 onQ[]：

queue.enqueue(s);
onQ[s] = true;
while (!queue.isEmpty() && !hasNegativeCycle()) {
    int v = queue.dequeue();
    onQ[v] = false;
    for (DirectedEdge e : G.adj(v)) {
        int w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            if (!onQ[w]) {
                queue.enqueue(w);
                onQ[w] = true;
            }
        }
        if (++cost % G.V() == 0) findNegativeCycle();
    }
}

onQ只表示当前是否已排队，不表示settled。Vertex可以在dequeue后因其他edge改善而再次入队。漏掉这一点会让negative-edge propagation过早停止；允许同一vertex在尚未dequeue时重复入队又会制造大量冗余。

Worst case time为 (O(VE))，extra space为Theta(V)。Queue optimization常减少实际relaxations，但不改变worst-case guarantee。若输入是DAG，优先使用linear topological algorithm；若全部nonnegative，Dijkstra提供更强bound。

从edgeTo中提取negative-cycle certificate

每进行V次edge relaxations，官方实现用当前 edgeTo[] 构造predecessor subgraph，并在其中做weighted directed-cycle detection。若找到cycle，必须独立求其edge-weight sum并确认strictly negative；仅看到predecessor cycle不够，因为zero或positive cycle不使distance无界。

Cycle certificate应满足：

Consecutive edges head-tail相接且最后回到start。
每条edge确实来自original graph。
Cycle从source可达。
Edge weights之和strictly negative。

Arbitrage：乘法收益转成加法negative cycle

若currency edge exchange rate为r，把weight设为 (-\log r)。Cycle上rates乘积大于1当且仅当transformed weights之和小于0：

\prod_i r_i>1 \iff \log\!\left(\prod_i r_i\right)>0 \iff \sum_i-\log r_i<0

于是arbitrage opportunity就是reachable negative cycle。Certificate还应把cycle换回original rates，逐步计算本金变化，避免log rounding造成虚假微小收益。

4.4.9 Independent certificate：不信任算法名，只验收labels与edges

最短路径证书不需要知道candidate由Dijkstra还是Bellman-Ford产生。对声称“无reachable negative cycle且已求得SPT”的结果，检查：

distTo[s] 为0，edgeTo[s] 为null。
Unreachable vertices保留infinity和null predecessor。
对每条edge (v\to w)，满足 distTo[w] 不大于 distTo[v] + weight。
对每个reachable non-source v，edgeTo[v]进入v并满足tight equality。
沿edgeTo回溯无cycle且终止于s。

for (DirectedEdge e : G.edges()) {
    int v = e.from(), w = e.to();
    if (distTo[w] > distTo[v] + e.weight() + EPS)
        return false; // violated edge inequality
}
for (int w = 0; w < G.V(); w++) {
    DirectedEdge e = edgeTo[w];
    if (w != s && hasPathTo(w)
        && (e == null || e.to() != w
            || Math.abs(distTo[w] - distTo[e.from()] - e.weight()) > EPS))
        return false;
}

Floating-point implementation应使用一致的EPS policy，但不能让tolerance大到接受实质改进。还应在algorithm entry拒绝NaN weights；NaN会让所有ordered comparisons失去可靠语义。

若candidate声明有negative cycle，则走另一套certificate：验证cycle connectivity与negative total。若两类certificate都给不出，结果不能仅凭“程序结束了”通过验收。

4.4.10 选择算法与逐步验收路线

先根据input promise选择算法：

Unweighted graph或所有weights相同：BFS，Theta(V+E)。
Nonnegative edge-weighted digraph：Dijkstra，(O(E\log V))。
Edge-weighted DAG，允许negative：topological shortest paths，Theta(V+E)。
General digraph，允许negative且需检测negative cycle：Bellman-Ford，(O(VE))。

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“4.4 · Shortest Paths”的两个最小情境间切换，再逐项选择正式概念。预测“relax(v→w)：若 dist[w] > dist[v]+weight(v,w)，同时更新 dist[w] 与 edgeTo[w]”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

4.4 · Shortest Paths：对象、操作与不变量

以松弛为统一操作，按非负权、DAG 或一般权重前提选择 Dijkstra、拓扑序或 Bellman-Ford

选择最小情境

切换正式概念

非负权图: s→a=2、s→b=5、a→b=1
当前观察: shortest paths：Dijkstra 先 settle a，再把 b 从 5 改进为 3

relax(v→w)：若 dist[w] > dist[v]+weight(v,w)，同时更新 dist[w] 与 edgeTo[w]

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

最短路径：在实验 1 中指出对应状态，并写出一个通过条件。
加权有向图：在实验 2 中指出对应状态，并写出一个通过条件。
松弛：在实验 3 中指出对应状态，并写出一个通过条件。
Dijkstra算法：在实验 1 中指出对应状态，并写出一个通过条件。
无环图最短路径：在实验 2 中指出对应状态，并写出一个通过条件。
Bellman-Ford算法与负权环：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“relax(v→w)：若 dist[w] > dist[v]+weight(v,w)，同时更新 dist[w] 与 edgeTo[w]”不是孤立结论？

问题 3：故障恢复。 怎样证明“在存在可达负权边时仍把 Dijkstra 出队顶点永久 settle，或只更新 dist 不更新 edgeTo”已经修复？

保存图与源点、distTo、edgeTo、松弛次序、优先队列、负环证书与全边校验器作为正常基线；注入该故障并标记第一个违反“所有边满足三角不等式，edgeTo 紧边链从可达顶点回到源点且路径权重等于 dist”的状态；撤销后用完全相同的输入、版本和随机种子重放。只有全部状态与独立预言机重新一致，才可发布修复结论。

小结

Shortest paths在edge-weighted digraphs中最小化directed path的total weight；unreachable与negative-cycle-affected是不同状态。
distTo保存best label，edgeTo保存实现它的last edge；relaxation成功时二者必须同步。
Dijkstra's algorithm依赖nonnegative weights，并以minimum-key vertex的settled invariant达到 (O(E\log V))。
Acyclic shortest paths按topological order一次relax每个vertex，允许negative edges并在线性时间完成。
Bellman-Ford algorithm允许labels反复下降，用queue避免无关扫描，并在worst case (O(VE)) 内求解或给出reachable negative cycle。
Independent certificate检查source label、all-edge inequalities、tight predecessor chain；negative-cycle结果则检查closed reachable cycle与negative sum。