第 24 章 单源最短路径

本章对应原书第 24 章。最短路径是图算法里最"实用"的一类问题：路线规划、网络路由、任务排期都离不开它。对量化交易来说，它有一个几乎原样照搬的应用：把汇率取负对数作为边权，一组可以套利的兑换环恰好是图里的一个负权环，Bellman-Ford 算法检测负权环的那一步，就是套利检测。本章先建立"初始化 + 松弛"这一统一框架，再依次讲 Bellman-Ford、DAG 上的线性时间算法、Dijkstra 算法和差分约束系统，最后用一个完整的外汇三角套利检测例子收尾。

学习目标

读完本章，你应当能够：

1. 说清最短路径权重 \(\delta(u,v)\) 的定义，以及负权边、负权环对它的影响（何时为 \(-\infty\)、何时为 \(+\infty\)）。
2. 理解"松弛"操作和六条性质（三角不等式、上界、无路径、收敛、路径松弛、前驱子图），并能用它们解释每个算法为什么正确。
3. 写出 Bellman-Ford（\(O(VE)\)，可检测负权环）、DAG 最短路（\(\Theta(V+E)\)）、Dijkstra（\(O((V+E)\lg V)\)，要求非负权）三种算法，知道各自的适用条件。
4. 把差分约束系统 \(x_j-x_i\le b_k\) 转化为约束图上的最短路径问题，并判断其可行性。
5. 用 \(w=-\ln R\) 把外汇套利检测化为负权环检测，能从 Bellman-Ford 的前驱数组中回溯出具体的套利环，并理解手续费、点差对结果的影响。

读前导读

这一章在解决什么问题。 给你一张"地图"：一些地点（顶点），地点之间有单向通道（边），每条通道有一个"代价"（边权）。问：从起点出发，到每个地点的最便宜走法是什么、要花多少？这就是单源最短路径。"代价"不一定是距离，可以是时间、费用，也可以是负数（走这条路反而赚钱）。一旦允许负数，就会出现一个怪现象：如果有一圈通道的代价之和为负，你可以无限绕圈，越绕越"便宜"——这叫负权环，此时"最短"失去意义。

这对你最有用的落点是外汇三角套利。把每种货币当作一个地点，"1 单位货币 \(i\) 换成 \(R[i,j]\) 单位货币 \(j\)"当作一条通道。兑换是连乘的，而最短路径是相加的；取对数就把乘法变成了加法，再取负号把"赚得多"变成"代价小"。于是"兑换一圈钱变多"恰好等价于"图里有负权环"。你在 CFA 里学过无套利定价：远期价格之所以等于 \(S_0(1+r)^T\)，是因为偏离就有人套利。本章给出的是这个思想在多币种报价表上的检测算法：把几十种货币、几百个报价扔进去，机器自动告诉你哪一圈报价自相矛盾。24.9.2 节还会把"无套利"翻译成"存在一组自洽的价格"，这正是资产定价基本定理的离散版。

算法部分的主线只有一条："先给每个地点一个保守的估计（起点 0，其余无穷大），然后反复用'经过邻居走过来会不会更便宜'去改进它"。这个改进动作叫松弛。三个算法只是改进的顺序不同：Bellman-Ford 笨但通用、能发现负权环；DAG 算法利用"没有环"一遍搞定；Dijkstra 很快，但要求代价都不为负。

需要先想起来的数学。

• 对数把乘法变加法。 \(\ln(ab)=\ln a+\ln b\)；\(\ln x>0\iff x>1\)，\(\ln x<0\iff 0<x<1\)。所以 \(-\ln x\) 是"递减"的：\(x\) 越大，\(-\ln x\) 越小。例：\(\ln1.0486\approx0.0474\)，即一圈赚 4.86% 对应对数收益 0.0474；连续复利收益率可以直接相加，就是同一个原因。见 第 00 册第 04 章 级数与收敛。
• 求和记号与"望远镜求和"。 \(\sum_{i=1}^{k}a_i=a_1+\cdots+a_k\)。若每一项都是"前后之差" \(a_i=h_{i-1}-h_i\)，相加时中间全部抵消，只剩 \(h_0-h_k\)；如果走的是一个环（\(h_0=h_k\)），总和就是 0。例：\((5-3)+(3-7)+(7-5)=0\)。本章 Bellman-Ford 的正确性、差分约束、无套利的势函数都靠这一招。见 第 00 册第 07 章 概率中的分析工具。
• 反证法与归纳法。 反证法：先假设结论不成立，推出矛盾（例如推出 \(0<0\)），从而结论成立。归纳法：证明"第 1 步对"和"第 \(k\) 步对则第 \(k+1\) 步也对"，于是所有步都对。本章几乎每个证明都是其中之一。见 第 00 册第 08 章 读懂数学证明与符号。
• 渐近记号 \(O\)、\(\Theta\)。 \(O(VE)\) 读作"运行时间不超过顶点数乘边数的某个常数倍"，只关心规模变大时增长有多快，不关心常数。例：10 个币种的全连接图有 90 条边，\(VE=900\)；100 个币种时 \(VE\approx10^6\)，规模涨 10 倍、工作量涨约 1000 倍。\(\lg V\) 是以 2 为底的对数，\(\lg1024=10\)，增长极慢。详见本册第 03 章。
• \(\min\)、\(\infty\) 与集合记号。 \(\min\{\cdots\}\) 是"花括号里所有数的最小值"；\(\infty\) 表示"根本到不了"；\(v\in V\) 读作"\(v\) 属于顶点集合 \(V\)"。见 第 00 册第 01 章 函数极限与连续。

另外，图的基本词汇（顶点、有向边、路径、环、邻接表、拓扑序、BFS）在本册第 22 章；"优先队列""堆"在本册第 06 章。读到 Dijkstra 的运行时间时如果不熟，只需记住：优先队列是一个"随时能以很低代价取出最小值"的容器。

怎么读这一章。 必读：24.1.1、24.1.4（负权环）、24.2.1（松弛）、24.3.1–24.3.3（Bellman-Ford）、24.9 全节（套利检测）。建议顺序是先读 24.1 和 24.2.1，然后直接跳到 24.9.1 看套利问题怎么变成负权环，再回头读 Bellman-Ford，动机会清楚很多。24.2.2 的六条性质第一次只需看懂第 5 条"路径松弛性质"；24.5 Dijkstra 读懂算法和"为什么不能有负权"即可；24.6 差分约束建议读，因为它和 24.9.2 的"无套利 = 存在一组价格"是同一件事。24.7 证明要点和 24.8 思考题第一次可以跳过。代码部分不需要会写 Python，读注释和输出、对照 24.9.5 的解释即可。

24.1 问题的提出

24.1.1 定义

Patrick 教授想找从 Phoenix 到 Indianapolis 的最短路线。把所有路线枚举一遍显然不现实——路线数量巨大，绝大多数根本不值得考虑（比如绕道 Seattle）。本章和第 25 章给出高效的方法。

形式化地，给定带权有向图 \(G=(V,E)\) 和权函数 \(w:E\to\mathbb R\)。路径 \(p=\langle v_0,v_1,\dots,v_k\rangle\) 的权重（weight）是各边权之和：

从 \(u\) 到 \(v\) 的最短路径权重（shortest-path weight）定义为

任何满足 \(w(p)=\delta(u,v)\) 的路径都叫最短路径（shortest path）。边权不一定是距离，可以是时间、成本、罚款、损失——任何沿路径线性累加、希望最小化的量都可以。第 22 章的广度优先搜索就是所有边权为 1 时的最短路径算法。

白话解释：上面几行符号逐个翻译。\(G=(V,E)\)：一张图由顶点集合 \(V\)（地点）和边集合 \(E\)（单向通道）组成，"有向"指 \((u,v)\) 只能从 \(u\) 走到 \(v\)。\(w:E\to\mathbb R\)：给每条边配一个实数（可正可负），就像给每笔交易标一个成本。\(u\overset{p}{\leadsto}v\)：存在一条名叫 \(p\) 的、从 \(u\) 出发、可能经过很多条边、最终到达 \(v\) 的路径。\(\delta(u,v)\) 就是"所有这样的路径里，成本合计最低的那个数"；一条路都没有，就记作 \(\infty\)。 一个小例子：从 USD 到 JPY 有两条路，直接换（成本 3）或经过 EUR（成本 \(1+1.5=2.5\)），则 \(\delta(\text{USD},\text{JPY})=2.5\)，最短路径是经过 EUR 的那条。

这句话值得在量化语境下再读一遍：只要一个量能沿路径"相加"，就能用最短路径。汇率是沿路径相乘的，但取对数后就变成了相加——这正是本章量化实战的出发点。

24.1.2 问题的几种变体

本章研究单源最短路径问题（single-source shortest-paths problem）：给定源点 \(s\)，求 \(s\) 到每个顶点 \(v\) 的最短路径。它能解决以下几种变体：

• 单目的地最短路径：求每个顶点到给定终点 \(t\) 的最短路径。把所有边反向，就变成单源问题。
• 单对顶点最短路径：求给定 \(u\) 到 \(v\) 的最短路径。以 \(u\) 为源解单源问题即可。已知的所有单对算法，最坏情况下的渐近时间都和最好的单源算法一样。
• 所有顶点对最短路径：对每对 \(u,v\) 求最短路径。可以从每个顶点各跑一次单源算法，但通常有更快的方法，这是第 25 章的内容。

24.1.3 最优子结构

最短路径算法几乎都依赖一个性质：最短路径的子路径也是最短路径。这是动态规划（第 15a 章）和贪心算法（第 16 章）可能适用的信号——本章的 Dijkstra 算法是贪心算法，第 25 章的 Floyd-Warshall 算法是动态规划算法。

引理 24.1（最短路径的子路径是最短路径）　设 \(p=\langle v_0,v_1,\dots,v_k\rangle\) 是从 \(v_0\) 到 \(v_k\) 的一条最短路径，则对任意 \(0\le i\le j\le k\)，子路径 \(p_{ij}=\langle v_i,\dots,v_j\rangle\) 是从 \(v_i\) 到 \(v_j\) 的最短路径。

证明（剪切粘贴论证）：把 \(p\) 拆成 \(v_0\overset{p_{0i}}{\leadsto}v_i\overset{p_{ij}}{\leadsto}v_j\overset{p_{jk}}{\leadsto}v_k\)，于是 \(w(p)=w(p_{0i})+w(p_{ij})+w(p_{jk})\)。若有一条 \(v_i\) 到 \(v_j\) 的路径 \(p'_{ij}\) 满足 \(w(p'_{ij})<w(p_{ij})\)，把它"粘"进去替换 \(p_{ij}\)，得到的 \(v_0\) 到 \(v_k\) 路径比 \(p\) 更短，矛盾。\(\square\)

24.1.4 负权边与负权环

某些实例里会有负权边。这本身不是问题：

• 如果从 \(s\) 出发不能到达任何负权环（negative-weight cycle），那么对所有 \(v\)，\(\delta(s,v)\) 都有良好定义（可以是负数）。
• 如果从 \(s\) 能到达一个负权环，那么最短路径权重就没有良好定义：到达环上任一顶点后，可以沿负权环多绕一圈，得到更小的权重，而且可以无限绕下去。若 \(s\) 到 \(v\) 的某条路径上有负权环，定义 \(\delta(s,v)=-\infty\)。

例（原书图 24.1）　源点为 \(s\)：

• \(s\to a\) 只有一条路径，\(\delta(s,a)=w(s,a)=3\)；\(s\to b\) 也只有一条，\(\delta(s,b)=3+(-4)=-1\)。
• \(s\) 到 \(c\) 有无穷多条路径：\(\langle s,c\rangle\)、\(\langle s,c,d,c\rangle\)、……。环 \(\langle c,d,c\rangle\) 的权重是 \(6+(-3)=3>0\)，绕它只会变长，所以 \(\delta(s,c)=w(s,c)=5\)，\(\delta(s,d)=5+6=11\)。
• \(s\) 到 \(e\)：环 \(\langle e,f,e\rangle\) 的权重是 \(3+(-6)=-3<0\)，可以绕任意多圈，所以 \(\delta(s,e)=\delta(s,f)=-\infty\)。\(g\) 可从 \(f\) 到达，\(\delta(s,g)=-\infty\)。
• 顶点 \(h,i,j\) 也构成一个负权环，但从 \(s\) 不可达，所以 \(\delta(s,h)=\delta(s,i)=\delta(s,j)=\infty\)。

最后一条容易被忽视：负权环只在从源点可达时才"污染"结果。这一点后面讲套利检测时会用到——要检测全图任意位置的负权环，需要加一个能到达所有顶点的超级源点。

金融直觉：负权环就是一台"印钞机"。在汇率图里（边权取 \(-\ln R\)，见 24.9 节），绕一圈总成本为 \(-0.0474\)，意味着每绕一圈本金乘以 \(e^{0.0474}\approx1.0486\)。只要能绕圈，就可以绕任意多圈，钱"无限多"，对应成本"\(-\infty\)"。所以 \(\delta=-\infty\) 不是数学怪癖，而是"存在无风险无限获利"的数学表达；它也说明了为什么正常定价的市场里不能有负权环。 至于"从源点不可达"的负权环（如 \(h,i,j\)）：你手里只有美元，而这个印钞机只接受一种你根本换不到的货币，那它对你没用，你到那几种货币的成本仍是"到不了"，即 \(\infty\)。

各算法对负权的态度不同：Dijkstra 要求所有边权非负；Bellman-Ford 允许负权边，只要从源点不可达负权环就能给出正确答案，并且能检测出可达的负权环。

24.1.5 最短路径不含环

最短路径可以取为简单路径（simple path）：

• 不能含负权环——否则没有最短路径；
• 不会含正权环——删掉环得到更短的路径；
• 零权环可以删掉而不改变权重。

所以不失一般性，最短路径至多含 \(|V|\) 个不同顶点、\(|V|-1\) 条边。这就是 Bellman-Ford 要做 \(|V|-1\) 轮的原因。

24.1.6 最短路径的表示

除了权重，我们还要知道路径本身。每个顶点维护一个前驱（predecessor）\(v.\pi\)（另一个顶点或 NIL），沿前驱链往回走就得到从 \(s\) 到 \(v\) 的最短路径（逆序）。由 \(\pi\) 诱导的前驱子图 \(G_\pi=(V_\pi,E_\pi)\) 为

算法结束时 \(G_\pi\) 是一棵最短路径树（shortest-paths tree）：以 \(s\) 为根，包含所有从 \(s\) 可达的顶点，树上从 \(s\) 到 \(v\) 的唯一路径就是 \(G\) 中的一条最短路径。它像 BFS 树，只是用边权而非边数度量距离。最短路径和最短路径树都不一定唯一（原书图 24.2 给出了同一个图、同一个根的两棵不同的最短路径树）。

24.2 松弛：所有算法的公共骨架

24.2.1 初始化与松弛

每个顶点维护一个属性 \(v.d\)，它是 \(\delta(s,v)\) 的上界，叫最短路径估计（shortest-path estimate）。

def initialize_single_source(G, s):     # Θ(V)
    for v in G.V:
        v.d = INF
        v.pi = None
    s.d = 0

def relax(u, v, w):                      # O(1)
    if v.d > u.d + w(u, v):
        v.d = u.d + w(u, v)
        v.pi = u

松弛（relaxation）边 \((u,v)\) 就是检查"先走到 \(u\) 再走边 \((u,v)\)"能否改进当前到 \(v\) 的估计；能，就更新 \(v.d\) 和 \(v.\pi\)。原书图 24.3：\(w(u,v)=2\)，若 \(u.d=5,v.d=9\)，松弛后 \(v.d=7\)；若 \(u.d=5,v.d=6\)，因为 \(6\le7\)，什么也不变。

"松弛"这个名字有点反直觉——它其实在收紧上界。历史来由是：可以把它看作对约束 \(v.d\le u.d+w(u,v)\) 的"放松"，约束已满足时就没有"压力"。

白话解释：\(v.d\) 是"目前为止找到的、从 \(s\) 到 \(v\) 的最便宜方案的成本"，\(v.\pi\) 记录这个方案里 \(v\) 的上一站。一开始除起点外一律记作 \(\infty\)（还没找到任何方案）。松弛 \((u,v)\) 就是问一句："如果先按目前的最佳方案到 \(u\)，再走一步到 \(v\)，是否比 \(v\) 现在的最佳方案还便宜？"是，就改写 \(v.d\) 并把上一站记为 \(u\)。 这像比价：你手里有一张"每种货币当前最优获取成本"的表，每看到一个新报价，就检查能不能借它刷新表中某一格。表里的数只会变小、不会变大，而且永远不低于真实的最低成本（这就是下面的"上界性质"）。所有算法都在用不同的顺序刷新这张表。

本章所有算法都是：先初始化，再以某种顺序反复松弛边。区别只在于松弛哪些边、松弛多少次、按什么顺序：

24.2.2 六条性质

以下性质是各算法正确性证明的积木（证明见 24.7 节）。后五条都假设先调用了初始化，之后只通过松弛修改 \(d\) 和 \(\pi\)。

1. 三角不等式（triangle inequality，引理 24.10）：对任意边 \((u,v)\in E\)，\(\delta(s,v)\le\delta(s,u)+w(u,v)\)。
2. 上界性质（upper-bound property，引理 24.11）：始终有 \(v.d\ge\delta(s,v)\)；一旦 \(v.d\) 达到 \(\delta(s,v)\)，就不再改变。
3. 无路径性质（no-path property，推论 24.12）：若 \(s\) 到 \(v\) 没有路径，则始终 \(v.d=\delta(s,v)=\infty\)。
4. 收敛性质（convergence property，引理 24.14）：若 \(s\leadsto u\to v\) 是最短路径，且在松弛 \((u,v)\) 之前的某时刻 \(u.d=\delta(s,u)\)，则此后始终 \(v.d=\delta(s,v)\)。
5. 路径松弛性质（path-relaxation property，引理 24.15）：若 \(p=\langle v_0,v_1,\dots,v_k\rangle\) 是 \(s=v_0\) 到 \(v_k\) 的最短路径，且松弛序列中按顺序出现了 \((v_0,v_1),(v_1,v_2),\dots,(v_{k-1},v_k)\)，则之后 \(v_k.d=\delta(s,v_k)\)——无论中间穿插了多少其他边的松弛。
6. 前驱子图性质（predecessor-subgraph property，引理 24.17）：一旦对所有 \(v\) 都有 \(v.d=\delta(s,v)\)，前驱子图就是以 \(s\) 为根的最短路径树。

其中第 5 条最关键：它告诉我们，只要沿最短路径的边按顺序被松弛过，结果就对了。Bellman-Ford 用"每轮松弛所有边"来保证这一点，DAG 算法用拓扑序保证，Dijkstra 用贪心选择保证。

白话解释：路径松弛性质可以想成接力赛。设最短路径是 \(s\to a\to b\to t\)。先松弛 \((s,a)\)，\(a.d\) 就对了；之后某个时刻松弛 \((a,b)\)，\(b.d\) 就对了；再之后松弛 \((b,t)\)，\(t.d\) 就对了。中间穿插再多无关的松弛也不要紧，因为 \(d\) 只降不升、又不会低于真值，已经对了的不会被弄错。关键只是"按顺序"：如果先松弛 \((b,t)\)、后松弛 \((a,b)\)，那么 \((b,t)\) 那一次用的是 \(b\) 尚未正确的 \(d\)，得不出正确的 \(t.d\)，必须等 \((b,t)\) 再被松弛一次。Bellman-Ford 每轮把所有边都松弛一遍，跑够 \(|V|-1\) 轮，无论边的排列顺序如何，第 \(i\) 轮总能把接力棒往前传一棒。

关于无穷大的运算约定：对实数 \(a\ne-\infty\)，\(a+\infty=\infty+a=\infty\)；对 \(a\ne\infty\)，\(a+(-\infty)=-\infty\)。图都用邻接表存储，边权随边存放。

24.3 Bellman-Ford 算法

24.3.1 算法

Bellman-Ford 算法解决一般情形（边权可以为负）的单源最短路径问题。它返回一个布尔值：若存在从源点可达的负权环，返回 FALSE，表示问题无解；否则返回 TRUE，同时给出最短路径和权重。

def bellman_ford(G, w, s):
    initialize_single_source(G, s)           # Θ(V)
    for i in range(1, len(G.V)):             # |V|-1 轮
        for (u, v) in G.E:                   # 每轮 Θ(E)
            relax(u, v, w)
    for (u, v) in G.E:                       # O(E)：负权环检测
        if v.d > u.d + w(u, v):
            return False
    return True

时间 \(O(VE)\)：初始化 \(\Theta(V)\)，\(|V|-1\) 轮每轮 \(\Theta(E)\)，最后检测 \(O(E)\)。空间 \(O(V)\)。

例（原书图 24.4）　5 个顶点 \(s,t,x,y,z\)，源点 \(s\)。边权：\(s\to t=6\)，\(s\to y=7\)，\(t\to x=5\)，\(t\to y=8\)，\(t\to z=-4\)，\(x\to t=-2\)，\(y\to x=-3\)，\(y\to z=9\)，\(z\to x=7\)，\(z\to s=2\)。每轮按 \((t,x),(t,y),(t,z),(x,t),(y,x),(y,z),(z,x),(z,s),(s,t),(s,y)\) 的顺序松弛：

最终 \(d(s,t,x,y,z)=(0,2,4,7,-2)\)，返回 TRUE。最短路径 \(s\to y\to x\to t\to z\) 用了 4 条边，恰好需要 \(|V|-1=4\) 轮。

24.3.2 正确性

引理 24.2　若 \(G\) 不含从 \(s\) 可达的负权环，则 \(|V|-1\) 轮之后，对所有从 \(s\) 可达的 \(v\)，\(v.d=\delta(s,v)\)。

证明：取 \(s\) 到 \(v\) 的一条最短简单路径 \(p=\langle v_0,\dots,v_k\rangle\)，\(k\le|V|-1\)。第 \(i\) 轮松弛了所有边，其中包括 \((v_{i-1},v_i)\)。所以这 \(k\) 条边按顺序被松弛过，由路径松弛性质得证。\(\square\)

推论 24.3　在同样假设下，\(s\) 到 \(v\) 有路径当且仅当算法结束时 \(v.d<\infty\)。

定理 24.4（Bellman-Ford 的正确性）　若 \(G\) 不含从 \(s\) 可达的负权环，算法返回 TRUE，所有 \(v.d=\delta(s,v)\)，前驱子图是最短路径树；若含有，算法返回 FALSE。

证明要点：

• 无负权环：可达顶点由引理 24.2、不可达顶点由无路径性质得 \(v.d=\delta(s,v)\)；再由前驱子图性质得最短路径树。对任意边，三角不等式给出 \(v.d=\delta(s,v)\le\delta(s,u)+w(u,v)=u.d+w(u,v)\)，检测不会触发，返回 TRUE。
• 有可达负权环 \(c=\langle v_0,\dots,v_k\rangle\)，\(v_0=v_k\)，\(\sum_{i=1}^k w(v_{i-1},v_i)<0\)。反设返回 TRUE，则对环上每条边 \(v_i.d\le v_{i-1}.d+w(v_{i-1},v_i)\)。沿环求和：

因为 \(v_0=v_k\)，左右两个 \(d\) 的和是同一组数；由推论 24.3 它们都有限，可以消去，得 \(0\le\sum w(v_{i-1},v_i)\)，与负权环矛盾。\(\square\)

推导拆解：第二部分用三个货币的环走一遍。设环为 USD→INR→JPY→USD，三条边权 \(w_1,w_2,w_3\)，和为负。 第 1 步（反设）：假设检测没触发，那么每条边都"松弛不动"：\(\text{INR}.d\le\text{USD}.d+w_1\)，\(\text{JPY}.d\le\text{INR}.d+w_2\)，\(\text{USD}.d\le\text{JPY}.d+w_3\)。 第 2 步（三式相加）：左边是 \(\text{INR}.d+\text{JPY}.d+\text{USD}.d\)，右边是 \(\text{USD}.d+\text{INR}.d+\text{JPY}.d+(w_1+w_2+w_3)\)。因为走的是环，左右两边出现的 \(d\) 是同一组数，只是排列顺序不同。 第 3 步（消去）：两边同减这三个 \(d\)，得 \(0\le w_1+w_2+w_3\)。这一步要求这些 \(d\) 都是有限数（\(\infty-\infty\) 没有意义），推论 24.3 保证了这一点，因为环从 \(s\) 可达。 第 4 步（矛盾）：而环的权重和是负的，矛盾。所以检测一定会在环上某条边触发。 换成白话：在一个负权环上，不可能每条边都"已经满意"，总有一条边还能继续改进。

24.3.3 直观理解：按"边数"做动态规划

第 \(i\) 轮结束后，所有"至多用 \(i\) 条边的最短路径"都已经求对。这是一个按"允许使用的边数"递推的动态规划（第 25 章会把它写成矩阵乘法的形式）。负权环检测的含义也就清楚了：\(|V|-1\) 轮后还能松弛，说明存在边数 \(\ge|V|\) 的更短路径——这种路径必然重复经过某个顶点，即含环，而让路径变短的环只能是负权环。

24.3.4 工程上的三个改进

提前终止（习题 24.1-3）　如果某一轮没有任何 \(d\) 值改变，后面的轮次也不会再改变，可以直接结束。设 \(m\) 为所有顶点的"最短路径中最少边数"的最大值，算法在 \(m+1\) 轮后就能停下。实际图中 \(m\) 往往远小于 \(|V|-1\)。

找出负权环本身（习题 24.1-6）　返回 FALSE 只说"有环"，套利交易需要知道是哪个环。做法：取第 \(|V|\) 轮中仍能被松弛的某个顶点 \(v\)，沿 \(\pi\) 回溯 \(|V|\) 步，必然落在一个负权环上；再从这个顶点沿 \(\pi\) 走一圈回到自身，就得到环（顺序是逆的）。原因是：一个顶点的 \(d\) 值能被无限改进，它的前驱链往回追溯必然进入负权环，而走 \(|V|\) 步后一定已经走进环内。

白话解释：为什么"回溯 \(|V|\) 步"就一定在环上？\(\pi\) 就是"上一站"。从 \(v\) 出发不停地问"你的上一站是谁"，最多 \(|V|\) 个不同顶点，问到第 \(|V|\) 次时必然有顶点出现第二次（抽屉原理：\(|V|\) 个抽屉放 \(|V|+1\) 个球，必有一个抽屉放了两个）。一旦重复，就进入了一个圈，之后会一直在圈里打转。所以回溯 \(|V|\) 步后落脚的顶点一定在圈上；再从它出发沿 \(\pi\) 走到它自己第一次重新出现，就把整个圈取出来了。这个圈正是负权环（原书习题 24.1-6 和本章练习 7 要求证明这一点）。在套利检测里，这一步把"有套利"变成了"按 USD→EUR→JPY→USD 这个顺序下单"。

检测全图的负权环　Bellman-Ford 只能检测从源点可达的负权环。要检测全图，加一个超级源点 \(v_0\)，到每个顶点连一条权 0 的边。等价的写法是：把所有 \(d\) 初始化为 0（而不是 \(s.d=0\)、其余 \(\infty\)），然后照常跑。24.6 节的差分约束和第 25 章的 Johnson 算法都用这个技巧。

Yen 的改进（思考题 24-1）　给顶点一个任意线性序 \(v_1,\dots,v_{|V|}\)，把边分为"前向" \(E_f=\{(v_i,v_j):i<j\}\) 和"后向" \(E_b=\{(v_i,v_j):i>j\}\)，两者各自是一个 DAG。每轮先按 \(v_1,\dots,v_{|V|}\) 的顺序松弛 \(E_f\) 的出边，再按逆序松弛 \(E_b\) 的出边。无可达负权环时只需 \(\lceil|V|/2\rceil\) 轮——渐近仍是 \(O(VE)\)，但常数减半。

24.4 有向无环图上的最短路径

对带权有向无环图（DAG，directed acyclic graph），按拓扑序松弛每个顶点的出边，就能在 \(\Theta(V+E)\) 时间内求出单源最短路径。DAG 里即使有负权边也没有环，最短路径总是有定义的。

def dag_shortest_paths(G, w, s):
    order = topological_sort(G)        # Θ(V+E)，见第 22 章
    initialize_single_source(G, s)     # Θ(V)
    for u in order:                    # 每个顶点一次
        for v in G.Adj[u]:             # 每条边恰好松弛一次
            relax(u, v, w)

例（原书图 24.5）　拓扑序 \(r,s,t,x,y,z\)，源点 \(s\)。边：\(r\to s=5\)，\(r\to t=3\)，\(s\to t=2\)，\(s\to x=6\)，\(t\to x=7\)，\(t\to y=4\)，\(t\to z=2\)，\(x\to y=-1\)，\(x\to z=1\)，\(y\to z=-2\)。结果 \(d(r,s,t,x,y,z)=(\infty,0,2,6,5,3)\)。\(r\) 在 \(s\) 之前，不可达，保持 \(\infty\)。

定理 24.5　若 \(G\) 无环，算法结束时所有 \(v.d=\delta(s,v)\)，前驱子图是最短路径树。证明：对可达顶点取最短路径 \(\langle v_0,\dots,v_k\rangle\)，拓扑序保证这些边按顺序被松弛，由路径松弛性质得证。

应用：关键路径（PERT 图）　在 PERT（program evaluation and review technique）图中，边代表任务，边权代表耗时；边 \((u,v)\) 进入 \(v\)、\((v,x)\) 离开 \(v\)，表示任务 \((u,v)\) 必须先于 \((v,x)\) 完成。关键路径（critical path）是 DAG 中的最长路径，它的长度是完成全部任务所需总时间的下界。求法有两种：把边权取负后跑 DAG-SHORTEST-PATHS；或者初始化为 \(-\infty\)、把 RELAX 中的 ">" 换成 "<"。

注意：一般图上的最长简单路径是 NP 难问题，只有在 DAG 上才能这样线性求解。这个区别和引理 24.1 有关——最长简单路径不具有最优子结构。

量化系统里，日终批处理（行情落地 → 清洗 → 因子计算 → 模型 → 优化 → 生成订单）就是一个 DAG，关键路径决定了整批任务的最短完成时间，也指出了该优先优化哪一步。第 27 章会看到，并行计算的"跨度"本质上就是计算 DAG 的关键路径长度。

24.5 Dijkstra 算法

24.5.1 算法

Dijkstra 算法要求所有边权非负，\(w(u,v)\ge0\)。在这个前提下，好的实现比 Bellman-Ford 快得多。

思想是贪心：维护集合 \(S\)，其中顶点的最终最短路径权重已经确定。反复从 \(V-S\) 中取出 \(d\) 值最小的顶点 \(u\)，加入 \(S\)，并松弛 \(u\) 的所有出边。用一个以 \(d\) 为键的最小优先队列 \(Q\) 来实现"取最小"。

def dijkstra(G, w, s):
    initialize_single_source(G, s)
    S = set()
    Q = MinPriorityQueue(G.V, key=lambda v: v.d)   # 隐含 |V| 次 INSERT
    while Q:                                        # 恰好 |V| 次
        u = Q.extract_min()
        S.add(u)
        for v in G.Adj[u]:                          # 总计 |E| 次
            relax(u, v, w)                          # 可能触发 DECREASE-KEY

循环不变式：每次迭代开始时 \(Q=V-S\)。每个顶点恰好出队一次，所以 while 循环恰好执行 \(|V|\) 次。

例（原书图 24.6）　边：\(s\to t=10\)，\(s\to y=5\)，\(t\to x=1\)，\(t\to y=2\)，\(x\to z=4\)，\(y\to t=3\)，\(y\to x=9\)，\(y\to z=2\)，\(z\to s=7\)，\(z\to x=6\)。

最终 \(d=(s{:}0,\ t{:}8,\ x{:}9,\ y{:}5,\ z{:}7)\)。

24.5.2 正确性

定理 24.6　在非负权有向图上，Dijkstra 算法结束时对所有 \(u\) 有 \(u.d=\delta(s,u)\)。

证明（循环不变式：每次迭代开始时，\(S\) 中所有 \(v\) 满足 \(v.d=\delta(s,v)\)）。只需证明每个顶点 \(u\) 加入 \(S\) 时 \(u.d=\delta(s,u)\)。反设 \(u\) 是第一个加入时 \(u.d\ne\delta(s,u)\) 的顶点。显然 \(u\ne s\)，且 \(s\) 到 \(u\) 必有路径（否则由无路径性质 \(u.d=\infty=\delta\)）。取一条最短路径 \(p\)，设 \(y\) 是 \(p\) 上第一个不在 \(S\) 中的顶点，\(x\) 是它的前驱（\(x\in S\)）：

• \(x\) 加入 \(S\) 时 \(x.d=\delta(s,x)\)（\(u\) 是第一个出错的），当时松弛了 \((x,y)\)，由收敛性质 \(y.d=\delta(s,y)\)。
• \(y\) 在最短路径上位于 \(u\) 之前，且 \(p_2\) 上边权非负，所以 \(\delta(s,y)\le\delta(s,u)\)。于是 \(y.d=\delta(s,y)\le\delta(s,u)\le u.d\)。
• 但 \(u\)、\(y\) 都在 \(V-S\) 中，算法选了 \(u\)，说明 \(u.d\le y.d\)。

两个不等式合起来全部取等，\(u.d=\delta(s,u)\)，矛盾。\(\square\)

证明中唯一用到非负权的地方是"\(\delta(s,y)\le\delta(s,u)\)"。有负权边时这一步失效，Dijkstra 可能给出错误结果（习题 24.3-2）。一个例外：若只有从源点出发的边为负、且无负权环，Dijkstra 仍正确（习题 24.3-10）。

推导拆解：用一个 4 顶点的反例看清失效点。边：\(s\to a=2\)，\(s\to b=3\)，\(a\to c=1\)，\(b\to a=-2\)。真实答案：\(\delta(s,a)=3-2=1\)（经过 \(b\)），\(\delta(s,c)=1+1=2\)。 Dijkstra 的过程：取出 \(s\)，得 \(a.d=2,b.d=3\)；取出 \(d\) 最小的 \(a\)（2），宣布"\(a\) 已定"，松弛出边得 \(c.d=3\)；接下来 \(b\) 和 \(c\) 都是 3，无论先取哪个，取出 \(b\) 时松弛 \(b\to a\) 会把 \(a.d\) 改成 1，但 \(a\) 早已出队，它的出边 \(a\to c\) 不会再被检查，于是 \(c.d=3\) 是错的（正确值是 2）。 失效的正是"\(\delta(s,y)\le\delta(s,u)\)"这一步：贪心的前提是"眼下最便宜的点，不可能被一条更远的路反超"。只有边权都非负时这才成立，因为多走一步只会更贵。在汇率图里，\(-\ln R\) 正负都有，所以套利检测只能用 Bellman-Ford。

推论 24.7　结束时前驱子图是以 \(s\) 为根的最短路径树。

24.5.3 运行时间

INSERT 与 EXTRACT-MIN 各 \(|V|\) 次；每条边只在其起点出队时被检查一次，所以 DECREASE-KEY 至多 \(|E|\) 次（聚合分析）。总时间取决于优先队列的实现：

稀疏图（\(E=o(V^2/\lg V)\)）用二叉堆更好，稠密图用数组即可。斐波那契堆正是为 Dijkstra 发明的：它的 DECREASE-KEY 调用远多于 EXTRACT-MIN，把前者降到摊还 \(O(1)\) 就能渐近加速。Python 实践中常用 heapq 加"懒删除"（重复入队，出队时跳过已处理的顶点）代替 DECREASE-KEY，复杂度为 \(O(E\lg E)=O(E\lg V)\)。

Dijkstra 与另外两个算法很像：它像 BFS——\(S\) 对应 BFS 中已染黑的顶点；也像第 23 章的 Prim 算法——都用最小优先队列找集合外"最轻"的顶点，加入集合后调整其余顶点的键。

几个常用变形（原书习题）：

• 最可靠路径（习题 24.3-6）：边上的值 \(r(u,v)\in[0,1]\) 是独立的成功概率，求成功概率最大的路径。取 \(w=-\log r\ge0\) 后跑 Dijkstra。这与套利检测用的是同一个"乘积取对数"技巧，只是这里权重天然非负。
• 小整数权（习题 24.3-8）：权值是 \(\{0,1,\dots,W\}\) 中的整数时，用桶代替堆（Dial 算法），时间 \(O(WV+E)\)。

24.6 差分约束与最短路径

24.6.1 线性规划的一个特例

线性规划（linear programming）在第 29 章详细讨论：给定 \(m\times n\) 矩阵 \(A\)、\(m\) 维向量 \(b\) 和 \(n\) 维向量 \(c\)，求 \(x\) 使 \(\sum c_ix_i\) 最大，满足 \(Ax\le b\)。有时我们不关心目标，只求一个可行解（feasible solution），或者判定不存在——这是可行性问题。

若 \(A\) 的每一行恰有一个 \(1\) 和一个 \(-1\)、其余为 0，\(Ax\le b\) 就是 \(m\) 个形如

的约束，称为差分约束系统（system of difference constraints）。

例　5 个未知数、8 个约束：

一个解是 \(x=(-5,-3,0,-1,-4)\)，另一个是 \(x'=(0,2,5,4,1)\)，每个分量都大 5。这不是巧合：

引理 24.8　若 \(x\) 是差分约束系统的解，则对任意常数 \(d\)，\(x+d\) 也是解（差值不变）。

差分约束的典型含义是事件的时间安排：\(x_i\) 是事件 \(i\) 发生的时刻。胶水在 \(x_1\) 时刻涂上、需 2 小时凝固才能在 \(x_2\) 安装零件：\(x_1-x_2\le-2\)。要求零件在涂胶之后、但不晚于凝固一半时安装：\(x_1-x_2\le0\) 且 \(x_2-x_1\le1\)。

24.6.2 约束图

把约束 \(x_j-x_i\le b_k\) 改写成 \(x_j\le x_i+b_k\)，它和松弛后的状态 \(v.d\le u.d+w(u,v)\) 一模一样。这提示我们构造约束图（constraint graph）\(G=(V,E)\)：

约束 \(x_j-x_i\le b_k\) 对应边 \((v_i,v_j)\)，权为 \(b_k\)；附加源点 \(v_0\) 到每个顶点的边权为 0，保证所有顶点都可达。

定理 24.9　若约束图无负权环，则

是一个可行解；若有负权环，则系统无可行解。

证明：无负权环时，对任意边 \((v_i,v_j)\)，三角不等式给出 \(\delta(v_0,v_j)\le\delta(v_0,v_i)+w(v_i,v_j)\)，即 \(x_j-x_i\le b_k\)。有负权环 \(c=\langle v_1,\dots,v_k\rangle\)（\(v_0\) 无入边，不在环上）时，环上的边对应约束 \(x_2-x_1\le w(v_1,v_2),\dots,x_k-x_{k-1}\le w(v_{k-1},v_k)\)。若有解，把它们相加，左边每个未知数一加一减，和为 0，右边为 \(w(c)<0\)，得 \(0<0\)，矛盾。\(\square\)

白话解释：约束 \(x_j\le x_i+b_k\) 读成"\(x_j\) 最多比 \(x_i\) 大 \(b_k\)"，正好是"到 \(v_j\) 的成本最多是到 \(v_i\) 的成本加上边权"。最短路径 \(\delta\) 天然满足所有这类不等式（三角不等式），所以拿它当答案就行。附加的 \(v_0\) 只是一个"统一起跑线"，每条边权都是 0，让所有变量都有定义。 矛盾的那一半用一个最小例子看：\(x_2-x_1\le1\) 与 \(x_1-x_2\le-2\)。前者说"\(x_2\) 最多比 \(x_1\) 大 1"，后者说"\(x_2\) 至少比 \(x_1\) 大 2"，显然冲突；两式相加正好得 \(0\le-1\)，对应约束图里一个权为 \(1+(-2)=-1\) 的环。 即可：返回 TRUE 时最短路径权重就是可行解，返回 FALSE 时无解。上例的约束图（原书图 24.8）中，\(\delta(v_0,v_i)\) 恰为 \((-5,-3,0,-1,-4)\)。\(m\) 个约束、\(n\) 个未知数时约束图有 \(n+1\) 个顶点、\(n+m\) 条边，用时 \(O(n^2+nm)\)（习题 24.4-5 可改进到 \(O(nm)\)）。

Bellman-Ford 给出的解还有额外的最优性：它在 \(x_i\le0\) 下使 \(\sum x_i\) 最大（习题 24.4-8），并使跨度 \(\max x_i-\min x_i\) 最小（习题 24.4-9）——在施工排期中就是总工期最短。

24.6.3 负权环 = 一组自相矛盾的约束

定理 24.9 的证明揭示了一个深刻的对应：负权环就是一组相加后得出 \(0<0\) 的约束。这个"把约束沿环相加得到矛盾"的论证，和 Bellman-Ford 正确性证明、外汇套利的"无套利条件"是同一个结构。下一节会看到：无套利等价于存在一组"价格" \(h\)，使所有约化成本非负——这正是差分约束 \(h_j-h_i\le w(i,j)\) 的可行性。第 29 章的线性规划对偶会把这个对应推广到一般情形（Farkas 引理）。

24.7 性质的证明要点

原书 24.5 节逐一证明了 24.2.2 的六条性质，这里只保留思路。

• 三角不等式：\(s\) 到 \(v\) 的最短路径不会比"先走 \(s\) 到 \(u\) 的最短路径、再走边 \((u,v)\)"这条特定路径更长。
• 上界性质：对松弛次数归纳。松弛 \((u,v)\) 若改变了 \(v.d\)，则 \(v.d=u.d+w(u,v)\ge\delta(s,u)+w(u,v)\ge\delta(s,v)\)。达到下界后不能再减，松弛又从不增大 \(d\)，所以不再改变。
• 收敛性质：由引理 24.13（松弛后立即有 \(v.d\le u.d+w(u,v)\)），\(v.d\le\delta(s,u)+w(u,v)=\delta(s,v)\)，再结合上界性质取等。
• 路径松弛性质：对路径上的边数归纳，每一步用收敛性质。
• 前驱子图是有根树（引理 24.16）：难点是证明 \(G_\pi\) 无环。若某次松弛 \((v_{k-1},v_k)\) 在 \(G_\pi\) 中造成环 \(c\)，则环上每个顶点在最后一次被赋前驱后，有 \(v_i.d\ge v_{i-1}.d+w(v_{i-1},v_i)\)，而 \(v_k\) 刚被严格改进，有 \(v_k.d>v_{k-1}.d+w(v_{k-1},v_k)\)。沿环求和后两边 \(d\) 的和相同，得 \(0>w(c)\)——\(c\) 是可达负权环，与假设矛盾。这又是"沿环求和"的论证。
• 前驱子图是最短路径树（引理 24.17）：树上路径各边满足 \(w(v_{i-1},v_i)\le\delta(s,v_i)-\delta(s,v_{i-1})\)，望远镜求和得 \(w(p)\le\delta(s,v)\)，而 \(\delta\) 是下界，所以取等。

24.8 思考题选讲

• 24-2 嵌套盒子：\(d\) 维盒子 \(x\) 能嵌入 \(y\)，当且仅当把两者的边长各自排序后逐维 \(x_{(i)}<y_{(i)}\)。嵌套关系是传递的，构成 DAG；求最长嵌套序列就是 DAG 最长路径，\(O(n^2d+nd\lg d)\)。
• 24-3 套利：本章量化实战的原型。1 美元换 49 卢比，1 卢比换 2 日元，1 日元换 0.0107 美元，则 \(49\times2\times0.0107=1.0486\)，转一圈获利 4.86%。给定汇率表 \(R[i,j]\)，(a) 判断是否存在货币序列使 \(R[i_1,i_2]R[i_2,i_3]\cdots R[i_k,i_1]>1\)；(b) 若存在，输出该序列。解法：令 \(w(i,j)=-\ln R[i,j]\)，乘积大于 1 当且仅当权和小于 0，即负权环；Bellman-Ford 用时 \(O(n^3)\)，再用习题 24.1-6 的方法回溯出环。
• 24-4 Gabow 缩放算法：非负整数权，\(W=\max w\)。按二进制位逐位精化：\(w_i\) 取 \(w\) 的最高 \(i\) 位，由 \(\delta_{i-1}\) 推 \(\delta_i\)；用重新赋权 \(\hat w_i(u,v)=w_i(u,v)+2\delta_{i-1}(s,u)-2\delta_{i-1}(s,v)\ge0\) 使每步的最短路径值不超过 \(|E|\)，可用桶式 Dijkstra 在 \(O(E)\) 内完成，总时间 \(O(E\lg W)\)。重新赋权的思想在第 25 章 Johnson 算法里还会出现。
• 24-5 Karp 最小平均权环：环 \(c\) 的平均权重 \(\mu(c)=\frac1k\sum w(e_i)\)，最小值

其中 \(\delta_k(s,v)\) 是恰好用 \(k\) 条边的最短路径权重。用动态规划算出所有 \(\delta_k\)，总时间 \(O(VE)\)。在汇率图上，最小平均权环对应"每一步平均收益最大"的循环兑换。

• 24-6 双调最短路径：若每条最短路径上的边权序列先增后减（双调），把边按权排序，做一次递增顺序、一次递减顺序的松弛即可，\(O(E\lg E)\)。

24.9 量化实战：外汇三角套利检测

24.9.1 从乘积到求和

设 \(R[i,j]\) 是 1 单位货币 \(i\) 能换到的货币 \(j\) 的数量（已包含买卖价差，即"可成交汇率"）。沿环 \(i_1\to i_2\to\cdots\to i_k\to i_1\) 兑换一圈，手里的钱变成原来的

\(G>1\) 就是套利。取边权 \(w(i,j)=-\ln R[i,j]\)，则

套利机会恰好是负权环。又因为套利环可能出现在图中任何位置，我们要检测全图的负权环，所以用 24.3.4 节的技巧：所有 \(d\) 初始化为 0（等价于加一个超级源点）。

推导拆解：用思考题 24-3 的数字把整件事手算一遍。报价：1 USD 换 49 INR，1 INR 换 2 JPY，1 JPY 换 0.0107 USD。 第 1 步（直接连乘）：\(49\times2\times0.0107=1.0486>1\)，转一圈赚 4.86%。 第 2 步（取对数，乘变加）：\(\ln49\approx3.8918\)，\(\ln2\approx0.6931\)，\(\ln0.0107\approx-4.5375\)，三者之和 \(\approx0.0474=\ln1.0486\)。这就是"对数收益可以相加"。 第 3 步（取负号，赚钱变成负成本）：边权 \(w=-\ln R\) 分别是 \(-3.8918\)、\(-0.6931\)、\(+4.5375\)，环的总权重 \(\approx-0.0474<0\)。取负号只是为了套用"求最小"的框架：赚得越多，成本越低。 第 4 步（看 Bellman-Ford 怎么"发现"它）：以 USD 为源，\(\text{USD}.d=0\)。松弛 USD→INR 得 \(\text{INR}.d=-3.8918\)；松弛 INR→JPY 得 \(\text{JPY}.d=-4.5849\)；松弛 JPY→USD 得 \(-4.5849+4.5375=-0.0474<0\)，比 USD 自己的 0 还小，于是 \(\text{USD}.d\) 被改成 \(-0.0474\)。\(d\) 的含义是"\(-\ln\)（1 单位 USD 最多能换到多少该货币）"，所以 \(\text{USD}.d<0\) 就是在说："1 美元绕一圈能换回多于 1 美元。"此后每绕一圈，三个 \(d\) 都再降 0.0474，永远停不下来——这正是 \(|V|-1\) 轮后检测仍会触发的原因。 第 5 步（为何初值可以全设 0）：初值相当于"假装每种货币都有一个零成本的起点"，它只影响 \(d\) 的具体数值，不影响"负权环上的 \(d\) 会无限下降"这一事实，所以用来检测环是合法的。

两个实务细节要先想清楚：

1. 为什么不能用 Dijkstra：\(-\ln R\) 经常是负的。1 美元换 150 日元，\(-\ln150<0\)。即使没有任何套利，边权也有正有负，Dijkstra 的前提不成立。
2. 为什么点差会自然消除"伪套利"：如果市场报价自洽（\(R[i,j]=V_i/V_j\)，\(V_i\) 是货币 \(i\) 的美元价值），任何环的乘积都是 \(\prod V_{i_t}/V_{i_{t+1}}=1\)；扣掉每一步的点差后严格小于 1。只有当某个报价偏离了其余报价隐含的交叉汇率、且偏离超过沿途点差之和时，才出现负权环。

24.9.2 势函数视角：无套利就是存在一组"价格"

把 24.6 节的差分约束反过来读。若存在一组数 \(h_i\)（不妨理解为货币 \(i\) 的对数美元价值），使每条边的约化成本（reduced cost）

那么任何环的权重 \(w(c)=\hat w(c)\ge0\)（\(h\) 在环上望远镜相消），不存在套利。反过来，若不存在负权环，取 \(h_i=\delta(v_0,i)\) 就满足所有约化成本非负（三角不等式）。所以：

这是资产定价基本定理（"无套利 ⟺ 存在正的定价函数"）在汇率图上的离散版本，第 29 章会用线性规划对偶（Farkas 引理）在一般情形下证明它。用"真实"的对数价值做 \(h\) 时，约化成本恰好等于 \(-\ln(1-\text{半点差})\approx\) 点差成本；哪条边的约化成本为负，哪条报价就是"错价"。这个视角也是第 25 章 Johnson 算法重新赋权的金融版解释。

推导拆解：为什么"\(h\) 在环上望远镜相消"？取环 \(i_1\to i_2\to i_3\to i_1\)，把三条边的约化成本相加：\([w(i_1,i_2)+h_{i_1}-h_{i_2}]+[w(i_2,i_3)+h_{i_2}-h_{i_3}]+[w(i_3,i_1)+h_{i_3}-h_{i_1}]\)。每个 \(h\) 正负各出现一次，全部抵消，剩下的正是 \(w(c)\)。所以重新赋权不改变任何环的总权重；如果每条边的约化成本都 \(\ge0\)，那么任何环都 \(\ge0\)，没有套利。 再看为什么取 \(h_i=\ln V_i\)（\(V_i\) 是货币 \(i\) 的美元价值）时约化成本等于点差成本：若报价自洽，\(R[i,j]=\frac{V_i}{V_j}(1-s_{ij})\)，\(s_{ij}\) 是半点差。于是 \(w(i,j)=-\ln V_i+\ln V_j-\ln(1-s_{ij})\)，加上 \(h_i-h_j=\ln V_i-\ln V_j\) 后只剩 \(-\ln(1-s_{ij})\approx s_{ij}>0\)。 这和用一条拟合好的收益率曲线给债券算理论价、再看谁偏贵谁偏便宜是同一种操作：\(h\) 是"曲线"，约化成本是"偏离"。正常报价只比理论价贵一个点差；约化成本为负、且大到足以抵消环上其他边的点差，就是可以锁定的套利。

24.9.3 代码：先核对原书例题

下面的工具函数与本章伪代码一一对应，先用原书的四个例子核对。

import heapq
from collections import defaultdict

INF = float("inf")

def bellman_ford(vertices, edges, s):
    """edges: list of (u, v, w)。返回 (ok, d, pi)；ok=False 表示有从 s 可达的负权环。"""
    d = {v: INF for v in vertices}; pi = {v: None for v in vertices}
    d[s] = 0
    for _ in range(len(vertices) - 1):
        changed = False
        for u, v, w in edges:
            if d[u] + w < d[v]:
                d[v] = d[u] + w; pi[v] = u; changed = True
        if not changed:                 # 习题 24.1-3：一轮无变化即可提前结束
            break
    ok = all(d[u] + w >= d[v] for u, v, w in edges)
    return ok, d, pi

def dag_shortest_paths(order, adj, s):
    d = {v: INF for v in order}; d[s] = 0
    for u in order:                     # 按拓扑序，每条边恰好松弛一次
        for v, w in adj[u]:
            d[v] = min(d[v], d[u] + w)
    return d

def dijkstra(vertices, adj, s):
    d = {v: INF for v in vertices}; d[s] = 0
    pq, done, order = [(0, s)], set(), []
    while pq:
        du, u = heapq.heappop(pq)
        if u in done:                   # 懒删除：代替 DECREASE-KEY
            continue
        done.add(u); order.append((u, du))
        for v, w in adj[u]:
            if du + w < d[v]:
                d[v] = du + w; heapq.heappush(pq, (d[v], v))
    return d, order

# 图 24.4：Bellman-Ford
E244 = [("t","x",5),("t","y",8),("t","z",-4),("x","t",-2),("y","x",-3),
        ("y","z",9),("z","x",7),("z","s",2),("s","t",6),("s","y",7)]
ok, d, pi = bellman_ford("stxyz", E244, "s")
print("图24.4 Bellman-Ford:", ok, d)

# 图 24.5：DAG 最短路
adj245 = defaultdict(list)
for u, v, w in [("r","s",5),("r","t",3),("s","t",2),("s","x",6),("t","x",7),("t","y",4),
                ("t","z",2),("x","y",-1),("x","z",1),("y","z",-2)]:
    adj245[u].append((v, w))
print("图24.5 DAG:", dag_shortest_paths("rstxyz", adj245, "s"))

# 图 24.6：Dijkstra
adj246 = defaultdict(list)
for u, v, w in [("s","t",10),("s","y",5),("t","x",1),("t","y",2),("x","z",4),("y","t",3),
                ("y","x",9),("y","z",2),("z","s",7),("z","x",6)]:
    adj246[u].append((v, w))
d, order = dijkstra("stxyz", adj246, "s")
print("图24.6 Dijkstra 出队顺序:", order)

# 24.4 节差分约束：x_j - x_i <= b  ->  边 (v_i, v_j)，权 b
cons = [(1,2,0),(1,5,-1),(2,5,1),(3,1,5),(4,1,4),(4,3,-1),(5,3,-3),(5,4,-3)]  # (j, i, b)
edges = [(i, j, b) for (j, i, b) in cons] + [(0, k, 0) for k in range(1, 6)]
ok, d, _ = bellman_ford(range(6), edges, 0)
print("差分约束可行:", ok, " x =", [d[k] for k in range(1, 6)])

输出：

图24.4 Bellman-Ford: True {'s': 0, 't': 2, 'x': 4, 'y': 7, 'z': -2}
图24.5 DAG: {'r': inf, 's': 0, 't': 2, 'x': 6, 'y': 5, 'z': 3}
图24.6 Dijkstra 出队顺序: [('s', 0), ('y', 5), ('z', 7), ('t', 8), ('x', 9)]
差分约束可行: True  x = [-5, -3, 0, -1, -4]

四个结果都与原书一致。

24.9.4 代码：8 种货币的套利检测

模拟一个 8 币种的报价矩阵：美元直盘点差最窄，主要交叉盘次之，CNH、CAD 与非美元货币的交叉盘最宽。然后注入一个"过期报价"：EUR/JPY 的双边报价没跟上日元走弱，整体偏高 0.12%（12 个基点）。

import numpy as np
from itertools import permutations

rng = np.random.default_rng(2024)
ccy = ["USD", "EUR", "JPY", "GBP", "CHF", "CNH", "AUD", "CAD"]
n = len(ccy)
# 1) 每种货币的"真实"美元价值（中间价），加一点随机扰动
usd_value = np.array([1.0, 1.08, 1/150, 1.27, 1.12, 1/7.2, 0.66, 0.73])
usd_value *= np.exp(rng.normal(0, 0.002, n)); usd_value[0] = 1.0
# 2) 报价矩阵 R[i, j] = 1 单位 i 能换到的 j 的数量 = 中间价 × (1 - 半个点差)
# 半点差：美元直盘 0.5~1bp，主要交叉盘 2~4bp，CNH/CAD 与非美元货币的交叉盘 10~25bp
half_spread = rng.uniform(2e-4, 4e-4, (n, n))
half_spread[0, :] = half_spread[:, 0] = rng.uniform(0.5e-4, 1e-4, n)
for k in (ccy.index("CNH"), ccy.index("CAD")):
    half_spread[k, 1:] = half_spread[1:, k] = rng.uniform(10e-4, 25e-4, n - 1)
half_spread = (half_spread + half_spread.T) / 2
R = usd_value[:, None] / usd_value[None, :] * (1 - half_spread)
np.fill_diagonal(R, 1.0)
# 3) 注入一个"过期报价"：EUR/JPY 双边报价没跟上 JPY 走弱，整体偏高 0.12%
i_eur, i_jpy = ccy.index("EUR"), ccy.index("JPY")
R[i_eur, i_jpy] *= 1.0012; R[i_jpy, i_eur] /= 1.0012

def find_arbitrage(R, fee=0.0):
    """在 w(i,j) = -ln(R[i,j]*(1-fee)) 上跑 Bellman-Ford（等价于加超级源点，所有 d 初值 0）。
    返回一个负权环（货币下标列表），没有则返回 None。"""
    n = len(R)
    W = -np.log(R * (1 - fee))
    edges = [(i, j, W[i, j]) for i in range(n) for j in range(n) if i != j]
    d = np.zeros(n); pi = [-1] * n
    for _ in range(n - 1):
        for i, j, w in edges:
            if d[i] + w < d[j] - 1e-15:
                d[j] = d[i] + w; pi[j] = i
    x = None
    for i, j, w in edges:                     # 第 n 轮仍能松弛 => 有负环
        if d[i] + w < d[j] - 1e-15:
            pi[j] = i; x = j; break
    if x is None:
        return None
    for _ in range(n):                        # 习题 24.1-6：沿 pi 回溯 n 步必落在环上
        x = pi[x]
    cycle, y = [x], pi[x]
    while y != x:
        cycle.append(y); y = pi[y]
    return cycle[::-1]                        # pi 是"前驱"，反转得到兑换方向

def cycle_return(R, cyc, fee=0.0):
    g = 1.0
    for a, b in zip(cyc, cyc[1:] + cyc[:1]):
        g *= R[a, b] * (1 - fee)
    return g

cyc = find_arbitrage(R)
print("检测到的套利环:", " -> ".join(ccy[k] for k in cyc + cyc[:1]))
print(f"一圈收益: {(cycle_return(R, cyc) - 1) * 1e4:.2f} bp")

# 用暴力枚举所有三角环核对（O(n^3)），看看最赚钱的几个
tri = []
for a, b, c in permutations(range(n), 3):
    if a < b and a < c:                       # 每个有向三角环只数一次
        tri.append(((cycle_return(R, [a, b, c]) - 1) * 1e4, (a, b, c)))
tri.sort(reverse=True)
for g, (a, b, c) in tri[:3]:
    print(f"  三角环 {ccy[a]}->{ccy[b]}->{ccy[c]}->{ccy[a]}: {g:+.2f} bp")

# 交易费：每笔 fee 后套利是否还存在
for fee_bp in [0.5, 1.0, 2.0, 3.0]:
    c2 = find_arbitrage(R, fee_bp * 1e-4)
    msg = "无套利" if c2 is None else f"{len(c2)} 腿环, {(cycle_return(R, c2, fee_bp*1e-4)-1)*1e4:+.2f} bp"
    print(f"每笔费用 {fee_bp} bp: {msg}")

# 势函数视角：以 h = ln(美元价值) 重新赋权，约化成本 = 点差成本 >= 0，只有被注入的边为负
W = -np.log(R); h = np.log(usd_value)
reduced = W + h[:, None] - h[None, :]
np.fill_diagonal(reduced, 0)
neg = np.argwhere(reduced < 0)
print("约化成本为负的边:", [(ccy[i], ccy[j], round(reduced[i, j] * 1e4, 2)) for i, j in neg], "(bp)")

# 去掉注入的错误报价后，求 EUR 到各币种的最优兑换路径（无负环 => 最短路有定义）
R_clean = R.copy(); R_clean[i_eur, i_jpy] /= 1.0012; R_clean[i_jpy, i_eur] *= 1.0012
src = ccy.index("EUR")
W = -np.log(R_clean); d = np.full(n, np.inf); d[src] = 0; pi = [-1] * n
for _ in range(n - 1):
    for i in range(n):
        for j in range(n):
            if i != j and d[i] + W[i, j] < d[j] - 1e-15:
                d[j] = d[i] + W[i, j]; pi[j] = i
for j in [ccy.index("JPY"), ccy.index("CNH"), ccy.index("CAD")]:
    path, k = [j], j
    while pi[k] != -1:
        k = pi[k]; path.append(k)
    path = path[::-1]
    gain = (np.exp(-d[j]) / R_clean[src, j] - 1) * 1e4
    print(f"EUR->{ccy[j]} 最优路径 {'->'.join(ccy[k] for k in path)}，比直接兑换多得 {gain:.2f} bp")

输出：

检测到的套利环: USD -> EUR -> JPY -> USD
一圈收益: 7.49 bp
  三角环 USD->EUR->JPY->USD: +7.49 bp
  三角环 EUR->JPY->AUD->EUR: +3.75 bp
  三角环 EUR->JPY->CHF->EUR: +3.56 bp
每笔费用 0.5 bp: 3 腿环, +5.99 bp
每笔费用 1.0 bp: 3 腿环, +4.49 bp
每笔费用 2.0 bp: 3 腿环, +1.49 bp
每笔费用 3.0 bp: 无套利
约化成本为负的边: [('EUR', 'JPY', np.float64(-9.12))] (bp)
EUR->JPY 最优路径 EUR->USD->JPY，比直接兑换多得 1.24 bp
EUR->CNH 最优路径 EUR->USD->CNH，比直接兑换多得 20.64 bp
EUR->CAD 最优路径 EUR->USD->CAD，比直接兑换多得 19.31 bp

24.9.5 读结果

检测与回溯。Bellman-Ford 找到的环是 USD → EUR → JPY → USD：用美元买欧元，用偏高的报价把欧元换成日元，再把日元换回美元，一圈赚 7.49 bp。12 bp 的错价扣掉三条腿的半点差（EUR/JPY 约 3 bp，两个美元直盘各不到 1 bp）后剩下这么多。暴力枚举所有三角环（\(\binom{8}{3}\times2=112\) 个有向三角环）确认它就是最赚钱的三角环，其余含 EUR→JPY 的环因为交叉盘点差更宽，利润更薄。

Bellman-Ford 不保证找到"最赚钱"的环。它只保证"若有负权环，就找到一个"。本例碰巧是最优的那个，一般情况下不一定。找"平均每步收益最大"的环可以用思考题 24-5 的 Karp 算法；找"总收益最大的简单环"则是 NP 难的（它包含了最长简单路径问题）。实践中常见的做法是：Bellman-Ford 检测 + 对涉及的货币做小规模枚举。

费用阈值。每笔加收 \(f\) 的费用相当于每条边权加 \(-\ln(1-f)\approx f\)，三腿环共多付约 \(3f\)。7.49 bp 的毛利在 \(f=2\) bp 时还剩 1.49 bp，到 \(f=3\) bp 时消失。这说明：对低频参与者看似存在的套利，对高费率参与者根本不存在，这也是三角套利基本只属于做市商和高频机构的原因之一。

约化成本定位错价。用真实对数价值作势函数 \(h\) 重新赋权后，只有 EUR→JPY 这一条边的约化成本为负（−9.12 bp = 半点差 − 12 bp 错价），其余边都等于各自的点差成本。实际中我们不知道"真实价值"，但可以用最近一次无套利状态下 Bellman-Ford 算出的 \(d\) 作为 \(h\)。

最优兑换路径。去掉错价后图中没有负权环，最短路径有定义。EUR → CNH 的直接报价点差很宽，绕道美元（EUR→USD→CNH）反而多得 20.64 bp；EUR → JPY 绕道美元也略好。这就是最短路径在执行层面的用法：多币种、多交易所的最优兑换路由。

24.9.6 真实系统还要考虑什么

上面的代码抓住了算法核心，但离实盘还差很多，下面几条是常见的工程要点。

• 数量与深度：\(R[i,j]\) 只对盘口第一档的数量有效。套利能做的规模受环上最薄的一档限制（这和第 26 章增广路径的"残存容量取最小值"是同一个结构）。
• 延迟与过期报价：本例的错价来自"过期报价"。现实中这种机会往往存在几毫秒到几百毫秒，抢到它靠的是速度。检测算法本身 \(O(n^3)\) 对几十个币种只需微秒级，瓶颈在行情和下单链路。
• 增量更新：每次只有少数报价变化。可以只把变化边的端点放入队列重新松弛（这就是 SPFA，即带队列的 Bellman-Ford），而不是每次从头跑 \(n-1\) 轮。
• 执行风险：三条腿不是同时成交的，第一腿成交后价格可能已变，留下单边敞口（leg risk）。
• 数值精度：利润以基点计，\(-\ln R\) 求和的舍入误差约 \(10^{-15}\)，远小于 1 bp，用浮点数没问题；但比较时应留一个阈值（代码中的 1e-15），实盘中这个阈值应设为最低可接受利润。

本章小结

单源最短路径的所有算法都建立在"初始化 + 松弛"的框架上，差别只在松弛的顺序和次数。最短路径具有最优子结构，且可以取为至多 \(|V|-1\) 条边的简单路径。Bellman-Ford 适用于任意实数权，\(O(VE)\)，并能检测可达负权环；DAG 上按拓扑序松弛一遍即可，\(\Theta(V+E)\)，还能求最长路径（关键路径）；Dijkstra 要求非负权，二叉堆实现 \(O((V+E)\lg V)\)。差分约束系统等价于约束图上的最短路径：无负权环时 \(x_i=\delta(v_0,v_i)\) 是可行解，有负权环则不可行。量化上最直接的应用是套利检测：取 \(w=-\ln R\)，套利环就是负权环；无套利等价于存在一组"价格"使所有约化成本非负。

练习

基础

1. 在原书图 24.4 上以 \(z\) 为源点运行 Bellman-Ford，写出每轮后的 \(d\) 和 \(\pi\)。再把 \(w(z,x)\) 改为 4，以 \(s\) 为源点运行，说明算法如何发现负权环。（原书 24.1-1。提示：改后 \(x\to t\to z\to x\) 的权重为 \(-2-4+4=-2\)。）
2. 修改 Bellman-Ford，使所有能被负权环"污染"的顶点 \(v\) 都得到 \(v.d=-\infty\)。（原书 24.1-4。提示：第 \(|V|\) 轮仍可松弛的顶点标为 \(-\infty\)，再从它们出发做一次 BFS/DFS 传播。）
3. 构造一个含负权边的有向图，使 Dijkstra 给出错误答案，并指出定理 24.6 的证明在哪一步失效。（原书 24.3-2。）
4. 每条边有独立的成功概率 \(r(u,v)\in[0,1]\)，求从 \(u\) 到 \(v\) 成功概率最大的路径。（原书 24.3-6。提示：\(w=-\log r\ge0\)，跑 Dijkstra。）
5. 给出一个线性时间算法，计算 DAG 中的路径总数。（原书 24.2-4。提示：按拓扑序做动态规划。）
6. 求下列差分约束系统的可行解或说明无解：\(x_1-x_2\le1\)，\(x_1-x_4\le-4\)，\(x_2-x_3\le2\)，\(x_2-x_5\le7\)，\(x_2-x_6\le5\)，\(x_3-x_6\le10\)，\(x_4-x_2\le2\)，\(x_5-x_1\le-1\)，\(x_5-x_4\le3\)，\(x_6-x_3\le-8\)。（原书 24.4-1。提示：建约束图跑 Bellman-Ford，答案之一为 \((-5,-3,0,-1,-6,-8)\)，可自行验证每条约束。）

进阶

7. 证明习题 24.1-6 的回溯方法正确：若第 \(|V|\) 轮中 \(v\) 仍可被松弛，则从 \(v\) 沿 \(\pi\) 回溯 \(|V|\) 步后必然位于一个负权环上。
8. 在 24.9.4 的代码基础上，实现 SPFA：维护一个"待松弛顶点"队列，只有 \(d\) 值变化的顶点才把出边重新放入。比较它与朴素版本在 50 个币种、每次只更新 3 个报价时的松弛次数。
9. 实现思考题 24-5 的 Karp 算法，在 24.9.4 的汇率图上求最小平均权环，与 Bellman-Ford 找到的环比较。说明在有交易费时两者的差异。
10. 把 24.9 节的套利检测扩展到"多交易所"：同一币对在两个交易所有不同报价，交易所之间转账有固定费率。如何建图？顶点和边分别代表什么？（提示：顶点为"（交易所，币种）"对，转账是一条权为 \(-\ln(1-\text{转账费})\) 的边。）

原书推荐习题：24.1-3、24.1-6、24.2-4、24.3-2、24.3-6、24.3-8、24.3-10、24.4-1、24.4-9，思考题 24-3（强烈推荐）、24-5。

原书对照

页码换算：原书页码 = PDF 页码 − 21。