地铁网络最短路算法讲解

TL;DR

同一张地铁网络图上，「最短路径」并不是一个算法，而是一族算法。本文按推进方式把项目里实现的五种算法串起来：Dijkstra 按距离从小到大逐个「确定」节点，Bellman-Ford 按轮次一圈圈向外铺，SPFA 是 Bellman-Ford 的队列优化，Floyd 则用「逐个解禁中转站」的办法一次性算出全源距离。在这之上，项目还叠加了两个把算法变成生活工具的扩展：多目标巡回（先用最短路算距离矩阵，再用状态压缩 DP 求访问顺序）与碰头点选址（同一张图，换一个目标函数，答案就完全不同）。

一、问题背景与数据模型

这一章先交代清楚两件事：我们在什么图上计算，以及算出来的数字到底代表什么。后面所有算法的讨论，都建立在这两个前提之上。

（一）要解决什么

给定一张城市地铁网络（站点 + 区间 + 区间耗时），回答三类问题：

1. 单对最短路：从 A 站到 B 站最少要多久，走哪条线。
2. 多目标巡回：从起点出发，把若干个目标站都走一遍，总耗时最小，顺序是什么。
3. 碰头点选址：几个人从不同位置出发，约在哪个站见面最合适。

三类问题的内核是同一个——图上的最短路径。区别只在于「在最短路上优化什么」。

（二）图模型：邻接表与邻接矩阵双存

项目用 Graph 类同时维护两份存储：

• 邻接表 g_[u]：只存真实存在的边，遍历一个点的邻居是 O(deg(u))。所有单源算法（Dijkstra / SPFA / Bellman-Ford）都走它。
• 邻接矩阵 a_[u][v]：O(1) 判断两点是否相邻、查询边权，Floyd 初始化与「是否有这条边」的检查走它。

用 INF 表示不可达，用 alive_ 标记点是否还存在（删点后不重建整张表）。读取数据时会丢弃自环、重边与越界编号，丢弃条数记在 dropped_ 里，供界面提示。

  设计取舍：双存带来约两倍内存，换来的是「遍历快」和「查询快」两种访问模式都不必妥协。地铁网络点数在几百量级，这个代价完全可以接受。

（三）边权的真实含义

边权不是直线距离，而是区间通行耗时（分钟）。实际计算前，基础耗时会乘上拥堵系数，组成 gWork_：

gWork_ = 基础耗时 × 拥堵系数      （封路的边权置为 INF）

所以算法输出的 dis 就是真实路上的分钟数。这一点很关键：它意味着后面所有「最优解」都是时间意义上的最优，而不是几何意义上的最近。

二、单源最短路：三种推进方式

单源最短路要回答的是「从 s 出发到每一个点的最小耗时」。三种算法的目标相同，区别在于用什么顺序去确定一个点的最终距离。

（一）Dijkstra：按距离从小到大逐个确定

Dijkstra 是最基础的贪心版本，它的全部威力来自一条不变式。下面先说明这条不变式为什么成立，再看它的两种实现。

1. 核心不变式

维护一个「已确定集合」S。每一轮从未确定的点里取出 dis 最小的那个 u，把它加入 S，然后用 u 去松弛它的所有邻居：

dis[v] = min(dis[v], dis[u] + w(u, v))

为什么可以「一旦确定就不再更改」：因为所有边权非负。如果 u 是剩余点里距离最小的，那么任何「绕一圈再回到 u」的路径都不可能更短——绕路只会让距离增加。

  前提条件：边权必须非负。这也是后面还要实现 Bellman-Ford 和 SPFA 的原因。

2. 朴素版与堆优化版

朴素版每轮用一次线性扫描找出当前最小距离的点：

for i in 0 .. n-1:
    u = 未确定点中 dis 最小的       // 这一步 O(n)
    vis[u] = 1
    for 每条 u -> v 的边: 松弛

总复杂度 O(n² + m)，适合稠密图或点数很小的场景，写起来最直观。

堆优化版把「找最小」交给优先队列：

while 堆非空:
    (d, u) = 堆顶弹出
    if vis[u]: continue            // 过期项，丢弃
    vis[u] = 1
    for 每条 u -> v 的边:
        if dis[u] + w < dis[v]:
            dis[v] = dis[u] + w
            压入 (dis[v], v)

复杂度降到 O((n + m) log n)，是项目里实际计算与算法对比时默认使用的版本。

3. 惰性删除：vis 判断为什么不能省

堆优化版没有实现「修改堆中元素的优先级」，而是允许同一个点被多次压入堆。这就带来一个问题：堆里可能同时存在 (dis_old, v) 和 (dis_new, v) 两项，其中 dis_old > dis_new。

if vis[u]: continue 就是用来丢弃这类过期项的。当 (dis_new, v) 先被弹出并处理时 vis[v] 被置 1，之后 (dis_old, v) 弹出时直接被跳过。

如果省掉这一行，会用已经过时的较大距离去松弛邻居，在稠密图上会产出偏大的错误结果。这正是「惰性删除（lazy deletion）」这个技巧存在的意义。

4. 记录型：为动画重放服务

dijkstraRecorded 的逻辑与堆优化版完全一致，只多输出一个 order 数组，记录节点被确定的先后顺序。界面上的算法动画就是按这个数组逐帧回放的——动画放出来的顺序，就是算法真实的确定顺序，而不是事后编排的视觉效果。

（二）Bellman-Ford：一轮一轮地铺

Bellman-Ford 不去挑「当前最近的点」，而是每一轮把所有边都扫一遍：

dis[s] = 0
for round in 1 .. n-1:
    changed = false
    for 每条边 (u, v, w):
        if dis[u] + w < dis[v]:
            dis[v] = dis[u] + w
            changed = true
    if not changed: break          // 提前收敛

为什么最多 n-1 轮：任何一条最短路径最多包含 n-1 条边（不含环）。第 i 轮结束时，已经能正确求出「边数不超过 i」的最短路。所以 n-1 轮之后必然全部收敛。

changed 标志是纯粹的优化：某一轮没有任何改进，说明已经收敛，可以直接跳出。

复杂度 O(n·m)，比堆优化 Dijkstra 慢，但换来两个能力：

1. 不要求边权非负，负权边也能正确处理。
2. 可以检测负环：如果跑完 n-1 轮后再扫一遍还能松弛，说明存在可以无限绕圈变短的负环，此时最短路径无定义。

记录型版本额外输出 roundInfo（每轮的松弛次数），使得动画能表现 Bellman-Ford 特有的「一轮一轮向外铺开」——这是它与 Dijkstra 在视觉上最直观的区别。

（三）SPFA：Bellman-Ford 的队列优化

观察 Bellman-Ford 可以发现：一轮里绝大多数边其实是无效扫描。只有上一轮距离真正变小的那些点，才可能带动邻居更新。

SPFA 用队列维护「距离刚被更新的点」：

dis[s] = 0; 队列 = [s]; inq[s] = 1
while 队列非空:
    u = 队首出队; inq[u] = 0
    for 每条 u -> v 的边:
        if dis[u] + w < dis[v]:
            dis[v] = dis[u] + w
            if not inq[v]:
                入队; inq[v] = 1
                cnt[v] += 1
                if cnt[v] >= n: 存在负环

inq 保证同一个点不会在队列里重复出现，cnt 统计入队次数——一个点入队达到 n 次，说明它在被负环反复缩短。

  复杂度要诚实地说：SPFA 的期望复杂度是 O(k·m)（k 为平均入队次数，通常很小），但最坏可以退化到 O(n·m)，与 Bellman-Ford 相同。它在网格图等特定结构上会被构造数据卡到最坏情况，因此不建议作为生产的默认选择。项目保留它，主要是为了对比教学——「队列优化在平均情况下有多快、在最坏情况下有多脆」本身就是很好的教材。

（四）三者的关系与选择

三、全源最短路：Floyd

Floyd 一次性求出所有点对之间的最短距离，代码只有三层循环。

（一）状态定义

把「中转站」逐个解禁。第 k 轮的含义是：只允许使用编号 0..k 的点作为中转。

for k in 0 .. n-1:                 // 第 1 层：本轮允许把 k 当中转站
    for i in 0 .. n-1:             // 第 2 层：起点
        for j in 0 .. n-1:         // 第 3 层：终点
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

（二）为什么 k 必须是最外层

这是 Floyd 最容易被写错的地方。把 k 放到内层，等价于只允许使用一个中转站——而真实的最短路径可能需要连续中转多次。

举例：若答案是 A → B → C → D，需要同时经过 B、C 两个中转点。只有 k 在最外层、逐个解禁，dis[A][C] 才会在 B 解禁时先被更新，dis[A][D] 才能在 C 解禁时利用到已经更新过的 dis[A][C]。

  错误不会报错，只会静默算出偏大的距离。这是它危险的地方。

（三）路径还原：next 矩阵

只记录长度无法还原路径，所以额外维护 next[i][j]——「从 i 到 j 的最短路上，i 的下一个点是谁」。更新距离时同步更新它：

if dis[i][k] + dis[k][j] < dis[i][j]:
    dis[i][j] = dis[i][k] + dis[k][j]
    next[i][j] = next[i][k]

复原时从 i 开始沿 next 一路跳到 j 即可。

（四）负环检测

Floyd 的收尾检查非常优雅：跑完后如果某个 dis[i][i] < 0，说明从 i 出发绕一圈回到 i 反而更短，即存在负环。

四、算法对比总表

（一）一个实测结论

在 411 个节点、5 个目标站的路网上跑巡回求解，几组策略的实测表现差异极大：

这张表说明了两件事。第一，Floyd 在这里慢得没有道理：它执行了约 800 倍的耗时，结果却和 k 次 Dijkstra 完全一致——因为目标只有 5 个（k = 6），Floyd 却把整个 411×411 的全源矩阵都算了。第二，贪心不是最优：它比精确 DP 少算了 12 分钟。

五、从单对到多目标：巡回问题

巡回看起来是一个全新的问题，但它并不需要新的最短路算法——它把已经实现的单源算法当成零件，换个方式组合起来。

（一）把问题拆成两步

「从起点出发按最优顺序走完所有目标」听起来比单对最短路复杂得多，但它可以干净地拆成两个独立子问题：

1. 距离矩阵：求出「起点 + 各目标点」两两之间的最短距离。
2. 顺序求解：在这个小规模距离矩阵上，决定访问顺序。

拆开的好处是两步可以各自换算法，组合出不同的性能/精度取舍。

（二）第一步：距离矩阵

设目标数为 m，节点表大小为 k = m + 1（含起点）。三种底座可选：

• k 次 Dijkstra：对表中每个点跑一次堆优化 Dijkstra，复杂度 O(k·(n+m)·log n)。
• k 次 SPFA：同上，最坏 O(k·n·m)。
• 一次 Floyd：O(n³)，与 k 无关。

取舍点很清晰：k 小时多次 Dijkstra 划算；k 接近 n 时 Floyd 更优。上一节的实测正是这个结论的极端案例——k 很小时，Floyd 的巨大固定开销完全无法摊薄。

（三）第二步：顺序求解

距离矩阵备好之后，剩下的就是一个纯粹的组合优化问题：在 m 个目标上找一条代价最小的访问顺序。规模不同，解法也不同。

1. 状态压缩 DP

有了距离矩阵 D，问题变成「以最小总代价访问所有目标」。用状态压缩 DP（Held-Karp）：

dp[mask][i] = 已访问集合为 mask、当前停在目标 i 的最小总耗时
dp[1 << j][j] = D[起点][j]                              // 初始：从起点直达第一个目标
dp[mask | (1 << j)][j] = min( dp[mask][i] + D[i][j] )   // 从 i 走到未访问的 j

mask 的每一位表示一个目标是否已访问。逐层扩展后，取 dp[全集][i] 的最小值即最优总耗时，再顺着父指针回溯即可得到访问顺序。

注意「已访问 {A, B} 且停在 B」和「已访问 {A, B} 且停在 A」是两个不同状态——因为下一步能走的边不同。这正是需要 mask 和 i 两个维度共同描述状态的原因。

2. 最近邻贪心

目标数变多时，DP 的 2^m 规模会爆炸。此时退化为最近邻贪心：每一步都走向「最近的未访问目标」。

它是近似解，不保证最优——上一节实测中它比精确解多花了 12 分钟。但当 m 超过 12 时，它是唯一可行的选择。

3. 规模边界

这一边界是显式写死在代码里的，而不是「跑跑看会不会超时」。显式声明「此配置下不可用」，比让用户等待一个可能几分钟都不返回的计算更诚实。

六、换个目标函数：碰头点选址

碰头点是把最短路「用出去」的典型场景。算法内核没有任何新东西，新的只是判断标准——而恰恰是这个标准决定了答案。

（一）问题与算法内核

三个人从不同位置出发，约在哪个站见面。算法上，对每个出发点各跑一次单源最短路，得到「每个人到每个候选点的耗时」，然后在候选点上选一个。选的标准就是目标函数。

（二）两种目标函数

设第 k 个人到候选点 v 的耗时为 d_k(v)：

• 最省（minisum）：min over v of sum_k d_k(v) —— 所有人的总耗时最短。
• 最公平（minimax）：min over v of max_k d_k(v) —— 让「最吃亏的那个人」尽量不吃亏。

实现上只需要在遍历候选点时维护两个量：sum 与 mx，分别取最小即可。若有人到不了该候选点，直接淘汰这个候选点。

（三）两个答案为什么不同

用一个具体场景说明。A、B 两个人在同一片区，C 在城另一头。

• 最省准则选前者：总路程 370 分钟，但 C 要独自走 330 分钟。
• 最公平准则选后者：总路程涨到 515 分钟，但最远的人也只要 185 分钟。

两个答案完全不同，而且都不是错的——它们只是优化了不同的东西。

  这个例子也是整个项目最想说明的一点：最短路的结果，取决于你要优化什么。换一个目标函数，同一张图上会得出完全不同的「最优解」。

七、让权重更真实：拥堵系数建模

前面所有算法的输入都依赖边权。如果边权本身不真实，算法再快也只是更快地给出一个不准的答案。这一章专门处理输入的来源。

（一）为什么要建模

项目自带的部分城市数据只有三列（起点、终点、耗时），没有拥堵系数。这意味着「按拥堵计算」在这些数据上等于没算——系数恒为 1.0，所有边等比放大，最短路结果完全不变。

（二）用真实经纬度与拓扑推算系数

真随机数是没有说服力的，所以系数由三个有现实依据的因素推算：

factor = 1.0 + 0.55 * centrality + 0.25 * hub - 0.08 * long_ratio

centrality = (1 - rel) ^ 2      // rel 为该区间中点到城市质心的归一化距离
hub                             // 该区间端点是否为换乘站（度数 >= 3）
long_ratio                      // 该区间长度占全市最长区间的比例

三个因素各有物理含义：

• 向心性：通勤潮汐是所有城市地铁的真实规律，越靠近市中心越挤。
• 换乘站加成：与换乘站相邻的区间，客流会叠加。
• 长区间减免：站间距越长，通常是郊区快线段，客流相对小。

（三）为什么衰减指数必须大于 1

这是整个建模里最关键的一个决策。centrality 使用 (1 - rel) ^ 2 而不是线性衰减：

• 线性衰减时：连「离质心不算远」的区间也拿到了较高系数，实测系数中位数达到 1.66——几乎全城一起堵，区分度极差，最短路和碰头点照样不变。
• 平方衰减后：系数被压缩到 1.00 ~ 1.76 的区间，拥堵真正集中在核心区。以北京为例，最堵的是西单—灵境胡同区间，系数 1.76。

指数大于 1 带来的不是「更好看」，而是空间差异真正被拉开，拥堵才会真的改变路径选择。

（四）一个诚实的反例

值得一提的是：光有真实的拥堵系数，碰头点往往还是不变。原因是各人来的方向不同，但都经过核心区，来路的平均拥堵程度接近，耦合后互相抵消。

真正让选址发生移动的，是叠加高峰模拟（按站点度数模拟高峰期拥堵）之后。这个反例本身很有价值——它说明「数据更真实」和「结论会改变」是两件事，中间还隔着「模型是否对结果敏感」。

八、总结：什么时候用哪个

最后一条也许是整个项目最值得记住的：前七个问题问的是「怎么算得更快」，只有最后一个问的是「到底要算什么」。而在真实场景里，后者的价值常常更高。

元信息

• 目标读者：具备基础数据结构知识（图、队列、堆）的中级开发者，或正在学习最短路径算法的学生
• 前置知识：图的存储方式、优先队列、动态规划入门
• 技术栈版本：C++17；Qt 6.8（Widgets + OpenGL Widgets）；算法核心与界面解耦，算法部分不依赖 Qt
• 预计阅读时间：约 15 分钟