还是第一章的五个虚构站点。S—A、A—T各需4分钟，S—B、B—C、C—T各需2分钟；连接均可双向通行，没有新增线路。上方路线P是S→A→T，全程不换乘；下方路线Q是S→B→C→T，要在C换一次车。
这次把C站的实际换乘时间固定为1分钟，仍不计其他候车与进出站时间。于是P用8分钟，换乘0次；Q用7分钟，换乘1次。
只问最快，答案已经是Q。可是，一个人说：“我不介意换车。”另一个人说：“为少换一次，我愿意多坐两分钟。”他们看的是同一张图，为什么不该收到同一个推荐？
前五章给了我们足够的工具。本章不另开一套理论，而是把规则、集合、图和算法接起来，完整回答一次“我该怎么走”。
先确定哪些路线有资格参加比较
为什么只需要比较P和Q？沿用第三章删去绕行的办法：路线若回到同一个状态，删掉中间那段，仍能接上后面的路。在这里，各段用时为正，换乘负担非负，删去绕行不会增加代价。因此，至少有一条最优路线不重复状态；逐条检查原图的连接，这样的S到T路线只有P和Q。我们不是随便挑两条示范，而是覆盖了这个模型中需要比较的选择。
再处理一个比偏好更强的条件：这位乘客不能走某条楼梯。
为这一情形补充明确的通行设定：C站两个站台之间只有这条楼梯，P沿途则符合乘客的通行要求。这里增加的是通行信息，没有增加一条新连接。
把两条候选路线组成集合R＝{P，Q}。对其中一条路线r，设L(r)表示“沿途连接都可通行”，B(r)表示“会使用这条禁用楼梯”。约定除此之外没有别的限制，允许参加比较的完整条件就是：
r可行 ↔ L(r) ∧ ¬B(r)
可行路线组成集合F。当前L(P)、L(Q)都真，B(P)为假、B(Q)为真，所以F＝{P}。Q虽然更快，也已经不在待选名单里。
这里的双向箭头依赖“除此之外没有别的限制”的约定。如果还有尚未核对的关站信息，只通过楼梯检查就不能推出可行。明确写出条件，也暴露了计算前必须拿到哪些输入。
把Q加上“很大的惩罚”能替代排除吗？在当前数据下，两种做法可能碰巧都选P，但表达的规则不同。假如P也临时不通，大惩罚仍可能让程序返回Q；真正的限制要求报告“没有可行路线”。不能走与不太想走，必须从输入开始就分开。
第二章的逻辑在这里有了实际用途：结果被推荐，就必须属于F。可行只是被选中的必要条件；当多条路线都可行时，还要继续比较。
把时间与换乘负担分开记录
下面换成两条路线都可行的乘客，暂时移除刚才的楼梯限制。
“少换一次值得多坐两分钟”可以写成一个明确的比较办法。把一次换乘的额外主观负担折合为λ分钟，λ读作“lambda”，并约定λ≥0。用t(r)记录实际总时间，m(r)记录换乘次数，定义路线的比较代价：
Jλ(r)＝t(r)＋λ×m(r)
λ的单位是“分钟等价值／次”，乘以换乘次数后，得到按同一偏好标尺折算的代价。它不是列车实际多开了几分钟，也不是C站实际换乘用时。C站那1分钟已经计入t，不能漏掉，也不能再当作λ重复解释。
现在代入两条路线：
Jλ(P)＝8＋λ×0＝8
Jλ(Q)＝7＋λ×1＝7＋λ
Q的代价更低，当且仅当7＋λ＜8，也就是λ＜1。λ＝1时并列，λ＞1时P更低。选择改变的分界，恰好是“少换一次”与“少花一分钟”在这把标尺上打平的地方。
例如λ＝2时，程序比较的是8与9，因而选P。但Q的实际总时间仍是7分钟。推荐页面若把“代价9”写成“9分钟到达”，就在最后一步把偏好分数冒充了计时结果。
这条式子也是一项待确认的约定：它认为每次换乘的额外负担相同，而且能够逐次相加。实际偏好未必如此。这里不是要给感受找到唯一正确的数字，而是让这次选择依据什么变得可检查。分钟与公里同样不能直接相加；若要合成分数，必须先说明转换办法和所得分数的含义。
“又快又少换乘”不一定只有一个答案
若乘客还没给出λ，我们仍能说清两条路线的长处。
把P记成“8分钟，0次换乘”，Q记成“7分钟，1次换乘”。Q在时间上更好，P在换乘上更好。没有哪一条同时在这两个指标上都不差于另一条，因此仅凭“又快又少换乘”，不能选出无条件胜出的路线。
可以把二者一并展示，请乘客决定更看重哪一项；也可以采用已经确认的规则。例如“最多换乘0次，再选最快”，会先筛出P；“先选时间最短，时间相同时再比较换乘次数”，则选Q。这两个中文要求都明确，却定义了不同的问题。
改变λ与改变通行条件也不一样。前者是在同一个F里换一把比较尺；后者会改变F本身。把这两步混在一起，程序就可能把用户禁止的路线当成“很不划算但仍可推荐”。
让图上的计算与新的目标对齐
现在两条路线都可行，并采用Jλ比较。第五章的Dijkstra还能用吗？要先检查，它累加的边权是不是这个代价。
沿用第一章的状态表示，把C拆成C绿与C橙。Q在图上成为S→B→C绿→C橙→T；P仍是S→A→T。乘车边保留原来的行车时间，C绿与C橙之间的换乘边则记为1＋λ。
这时P的边权和为4＋4＝8，Q为2＋2＋(1＋λ)＋2＝7＋λ，恰好等于刚才定义的Jλ。物理站点仍有五个，图中有六个状态。拆开的两点让换乘只在真实跨越站台时计入，而不是一到C就不分情况加价。
我们实际跑两遍。用d(v)表示目前找到的到状态v的最小代价，初始d(S)＝0，其余为∞。每次从未定案状态中选择d最小的一个；若并列，本例约定先选A，再选C绿。
λ＝0时，S先定案，得到d(B)＝2、d(A)＝4。B定案后，d(C绿)＝4。接着A定案，给T一个暂定值8；C绿定案，给C橙暂定值5。下一步选C橙，经过它到T的候选为5＋2＝7，小于8，于是把d(T)改成7。最后T定案，沿保存的前驱恢复出Q。
λ＝2时，前面的S、B、A、C绿依次定案，T仍先得到8。但换乘边现在重3，C橙得到7；从它到T的候选为7＋2＝9，不能改善8。T定案后恢复出的就是P。
注意两遍里，T都曾先被发现为8。第一遍若一发现T便退出，就会错过后面的7。停止位置必须仍是“从未定案者中以最小暂定值选出T”，不能因为我们换了目标，就随意改掉算法的动作。
原来的不变量也仍在工作：每个已定案状态的数值，等于这张图上从S到它的最小代价。λ固定且非负，所以新边权仍固定且非负，原证明的条件没有被破坏。MIT的Dijkstra讲义正是在这些条件下，以定案次序建立归纳论证。
这个保证有清楚的边界：算法优化的是我们写入的代价。它不会自行判断λ是否适合乘客，也不会替我们发现那条楼梯其实不能走。
如果第一次运行已经把T以7定案，再把λ从0改成2，就不能沿用“这个7已经正确”的承诺。原来的7属于旧权重，新的最小代价应是8。本例重新初始化再计算，就能重新建立不变量。证明可以复用，是因为新输入也满足前提；上一次的中间数值却不能因此照搬。
哪一项变化，需要回头检查哪里
再把实际换乘时间恢复成变量τ。两条路线的比较代价变为8与6＋τ＋λ，于是Q更好的条件是：
τ＋λ＜2
这个条件式把两种来源不同的变化放在同一处比较。τ来自通行与等待的估计，λ来自偏好的约定；二者都能改变推荐，但需要的证据不同。
例如λ＝1时，如果τ＝0.8，Q的代价为7.8；若τ＝1.2，代价便是8.2，推荐翻转。要用于真实出行，就应核对估计对应的时段、方向和计时范围，而不是继续把小数算得更长。若“1分钟”只是平均值，也不能宣称每次都会花1分钟。
检查应发生在计算之前，也发生在结果使用时。计算前核对通行条件和权重；计算后检查返回路线确实属于F，边权和确实符合Jλ；出发前若通道关闭或数据更新，就用新输入重新求解。旧图中的不变量不能直接证明新图的答案。SIAM与COMAP的GAIMME指南强调的模型评估，也包括把结果放回原问题，检查假设并按需要修订。
这种分工可以迁移到资源规划或AI任务执行：先把权限、容量等不可违反的条件落实为可行性，再定义耗时与费用如何比较，最后检查求解程序是否满足规格。即使程序找到了代价最小的方案，也还需要验证计费、运行数据和目标是否适合实际任务。优化结果是一条带着条件的结论。
回到S站，我们现在可以给出完整答案：两路都可行、换乘固定1分钟、只求最快时，选7分钟的Q；每次换乘的额外负担折合2分钟时，选8分钟的P；若C站那条楼梯不能使用，先排除Q，P才是待选路线。
从一张图出发，走过规则、关系、状态和证明，再回到一次具体选择，地图上的线没有增加，我们能回答的问题却精确了许多。“哪条最好”终于有了可以核对的后半句：对谁，满足什么条件，按什么标准。
顺手试一下
题目1：同一张图，三个推荐
两路都可行，τ＝1。分别取λ＝0.5、1、2，求两条路线的比较代价与推荐结果。Q的实际到达时间会随λ改变吗？
**提示：**比较8与7＋λ，单独保留实际时间字段。
**参考答案：**三种情况下P的代价均为8；Q分别为7.5、8、9。因此依次为Q更优、两路并列、P更优。Q的实际总时间始终是7分钟。并列时若必须只返回一条，应另行约定平局规则。
题目2：惩罚能表达禁止吗
沿用楼梯限制：Q不可行，P符合要求。现在S—A暂时关闭。有人给Q加1000的惩罚，再让算法选代价最小的路线。它能保证满足乘客要求吗？应怎样修改图并报告结果？
**提示：**再大的有限代价，也没有把一条边从图中删除。
**参考答案：**不能。P因关闭不可行，Q仍因楼梯不可行，所以F为空。应在图中禁用S—A以及C绿—C橙之间的楼梯连接，再计算可达性；此时S无法到达T，应报告没有可行路线。保留楼梯边只加惩罚，仍可能返回违反要求的Q。
延伸阅读与来源
- MIT 6.006，2020年春，第13讲：Dijkstra's Algorithm。重点看讲义第1—3页的非负边权条件、逐次选取最小暂定值及正确性证明，不必在本章展开优先队列的实现。
- SIAM与COMAP，GAIMME第二版，2019年。正文印刷页12—13介绍模型形成与评估，18—20页的案例展示假设检查和目标遗漏。本文五站模型与两次运行均为独立设定、逐步计算的教学例子。
作者：Jiancheng Wang · 数学之美（独立原创）