10.2 最短路径

最短路径问题是图论中最经典的问题之一——从导航系统到网络路由，无处不在。在量化金融中，支付系统路由和外汇套利检测都依赖最短路径算法。

---

Dijkstra 算法

算法简述

Dijkstra 算法求解单源最短路径（边权非负）：

1. 初始化：源点距离 $=0$，其余 $\infty$；所有节点未访问
2. 从未访问节点中选取距离最小的节点 $u$
3. 对 $u$ 的所有邻居 $v$：若 $dist[u] + w(u,v) < dist[v]$，更新 $dist[v]$
4. 标记 $u$ 为已访问
5. 重复 2-4 直到所有节点访问完

时间复杂度：$\mathcal{O}((V+E)\log V)$（使用优先队列实现）

---

手算实例：5 节点图（源点 = 节点 1）

使用与 10.1 节相同的 5 节点加权无向图。

初始状态

节点	距节点 1 距离	前驱	已访问
1	0	—	否
2	$\infty$	—	否
3	$\infty$	—	否
4	$\infty$	—	否
5	$\infty$	—	否

第 1 步：选中节点 1

访问节点 1（距离最小=0）。更新邻居 2, 3, 4：

边	当前距离	$dist[1] + w$	是否更新？	新距离	新前驱
(1,2)	$\infty$	$0 + 2 = 2$	是	2	1
(1,3)	$\infty$	$0 + 4 = 4$	是	4	1
(1,4)	$\infty$	$0 + 3 = 3$	是	3	1

节点	距离	前驱	已访问
1	0	—	是
2	2	1	否
3	4	1	否
4	3	1	否
5	$\infty$	—	否

第 2 步：选中节点 2

未访问节点中最小距离 = 2（节点 2）。访问节点 2，更新邻居：

边	当前距离	$dist[2] + w$	更新？	新距离	新前驱
(2,4)	3	$2 + 1 = 3$	否（相等）	3	不变

节点	距离	前驱	已访问
1	0	—	是
2	2	1	是
3	4	1	否
4	3	1	否
5	$\infty$	—	否

第 3 步：选中节点 4

未访问中最小距离 = 3（节点 4）。访问节点 4，更新邻居：

边	当前距离	$dist[4] + w$	更新？	新距离	新前驱
(4,3)	4	$3 + 1 = 4$	否（相等）	4	不变
(4,5)	$\infty$	$3 + 5 = 8$	是	8	4

节点	距离	前驱	已访问
1	0	—	是
2	2	1	是
3	4	1	否
4	3	1	是
5	8	4	否

第 4 步：选中节点 3

未访问中最小距离 = 4（节点 3）。访问节点 3。节点 3 的所有邻居（1, 4）都已访问，无更新。

第 5 步：选中节点 5

最后选中节点 5。已无更多更新。

最终最短路径

起点 → 终点	最短距离	路径
1 → 2	2	1 → 2
1 → 3	4	1 → 3 或 1 → 4 → 3
1 → 4	3	1 → 4
1 → 5	8	1 → 4 → 5

---

Python 示例

import networkx as nx

# 构建加权无向图
G = nx.Graph()
edges = [
    (1, 2, 2),
    (1, 3, 4),
    (1, 4, 3),
    (2, 4, 1),
    (3, 4, 1),
    (4, 5, 5)
]
G.add_weighted_edges_from(edges)

# Dijkstra 最短路径
for target in [2, 3, 4, 5]:
    path = nx.dijkstra_path(G, source=1, target=target, weight='weight')
    dist = nx.dijkstra_path_length(G, source=1, target=target, weight='weight')
    print(f"1 → {target}: 距离 = {dist}, 路径 = {path}")

# --- 输出 ---
# 1 → 2: 距离 = 2, 路径 = [1, 2]
# 1 → 3: 距离 = 4, 路径 = [1, 3]    （也可通过 1→4→3，同距离）
# 1 → 4: 距离 = 3, 路径 = [1, 4]
# 1 → 5: 距离 = 8, 路径 = [1, 4, 5]

---

Quant Link：支付网络路由

在支付系统结算（如 CHIPS 或 Fedwire）中，Dijkstra 算法用于寻找银行间资金转移的最优路径——最小化中间行数量或总手续费的支付路径。

区块链闪电网络

区块链中的闪电网络也使用类似的路由算法。在闪电网络中：

• 顶点：支付通道节点
• 边：双向支付通道，权重为通道容量或手续费
• 目标：找到从发送方到接收方、有足够流动性的路径

外汇套利检测

Dijkstra 算法的一个变种也用于检测三角套利机会——将汇率取负对数后，寻找负权环等价于寻找套利机会。

注意：Dijkstra 算法要求边权非负。当图中存在负权边（如某些转换后的成本）时，应使用 Bellman-Ford 算法。Bellman-Ford 通过对图中所有边重复松弛操作（Relaxation——检查"经过当前节点 $u$ 到 $v$ 是否比原来记录的路径更短"，如果是则更新距离）$|V|-1$ 轮（$|V|$ 为顶点数）来找到最短路径。每轮遍历所有边，尝试用 $dist[u] + w(u,v)$ 更新 $dist[v]$。若第 $|V|$ 轮还能更新，则说明存在负权环（可无限缩小距离）。算法时间复杂度 $O(|V||E|)$，比 Dijkstra 的 $O((|V|+|E|)\log|V|)$ 慢，但能处理负权边。 \n> 下一步：继续学习 10.3 最小生成树