CSCI3160 Special 10：Dijkstra 与 Bellman–Ford 完整演算

原件：Sp10 题目（本地课件） p.1–2，两幅有向图已渲染核对箭头。 每题先题解后解析；数字为原图，算法实现约定明确列出。

Problem 1：Dijkstra 确定顶点的次序（p.1）

题解

从a开始，依次确定a、e、g、c、b、d、f；最终距离按a,b,c,d,e,f,g排列为0、7、5、8、3、10、4。

具体解析

原图边为a→c(6)、a→e(3)、c→b(2)、b→d(1)、c→d(5)、c→e(2)、c→f(6)、g→c(1)、d→e(1)、d→f(2)、e→g(1)。尤其g与c的边是g→c，不是c→g；曲线是d→e。

每次取当前候选最小者，而非按顶点字母序或图上位置。到f的最短路径为a,e,g,c,b,d,f，权重3+1+1+2+1+2=10。正权保证已确定距离不会再被未来路线降低。

Problem 2：按最后一条边分解最短距离（p.1）

题解

对每个入邻居v，将s到v的最短路线接上v→t，给出候选上界；反过来取s到t最短路径的倒数第二点，就达到其中一个候选。因此

具体解析

第一方向：每条候选路线长度不小于真正最短距离，故左侧≤右侧。第二方向：选择最短简单路径，最后一边v→t；其前缀必须也是到v的最短路线，否则换成更短前缀就能改进整体，所以左侧等于该候选，≥全部候选的最小值。

若t不可达，所有有限候选都不存在，两边均为∞；若入邻居集合为空，约定min空集=∞。s与t不同排除了长度零而没有最后一条边的情况。可以有零权边，结论不要求严格正权。

Problem 3：Dijkstra 的负边反例（p.1）

题解

s→a=2、s→b=5、b→a=−4。算法先把a确定为2，真实最短距离却为1，故失败。

具体解析

初始化松弛源点后a候选2小于b候选5，于是a先出队。未来b才暴露负边，使s,b,a总长1；标准Dijkstra不再重新处理已确定顶点，因此正确性被破坏。图是DAG，无负环，说明只排除负环还不够。

若某实现允许对已出队顶点重复入队，它已不再是这里分析的标准Dijkstra及其一次确定的时间界，不能拿那个变体否定反例。

Problem 4：Bellman–Ford 的每轮距离（p.1）

题解

本题未固定每轮边顺序；采用与课堂演示一致的端点字母序、原地松弛。顺序为ac、ae、bd、cb、cd、de、ec。第1至第4轮后都为a=0、b=−5、c=−7、d=−2、e=−5。

具体解析

原图边：a→c=−7、a→e=3、b→d=4、c→b=2、c→d=5、d→e=−3、e→c=−2。第一轮逐边：ac使c=−7；ae使e=3；bd此时b=∞不变；cb使b=−5；cd使d=−2；de使e=−5；ec给候选−7，与现值相等，不更新。第一轮已经把最短路径a,c,d,e传播完，后续不再变化。

若每轮使用上一轮数组、同步写新数组，中间表会不同：第1轮为(0,∞,−7,∞,3)，第2轮为(0,−5,−7,−2,3)，第3、4轮为(0,−5,−7,−2,−5)。同步版第r轮对应最多r条边；原地版一轮可能传播多条边。二者最终相同，但不能混合表格后声称哪个中间结果唯一正确。

这张图含权重为0的环c→d→e→c（5−3−2=0），不含负环；距离可以稳定。由于题目要求四轮，表中仍列出全部四轮，而不是稳定后省略。

Problem 5：输出最短路径树（p.1）

题解

在Bellman–Ford严格改善d(v)时保存前驱u，是常用恢复方法。更稳妥且便于处理零权环的构造是：先得到最终距离，保留所有有限距离端点间满足d(v)=d(u)+w(u,v)的紧边，再从s在紧边图上DFS/BFS，首次发现一个顶点时保留那条发现边。所得发现树就是最短路径树，额外O(n+m)。

具体解析

每个可达顶点都有一条最短简单路径，这条路径上的每条边都满足紧等式，所以在紧边图中它仍可由s到达。搜索树按首次发现连接新顶点，天然无环；沿根到v的树路径把紧等式相加，内部距离抵消，总权重d(v)−d(s)=d(v)，因此每条树路径最短。

不能把所有紧边直接叫作树：Q4零权环的三条边全部可能紧，但一起保留仍有环。也不要在等距时任意改前驱导致引入循环。发现树方法明确给出无环选择规则。

只包含从s可达的顶点；不可达顶点没有源点路径，不能强行挂接。若有可达负环，则部分最短距离无有限值，必须先报告不存在所要求的最短路径树。总时间O(nm+n+m)，通常非退化连通规模写O(nm)。

在 Q4 原图上实际构造一次紧边树。 最终距离为 $(0,-5,-7,-2,-5)$。紧边是 ac、cb、cd、de、ec；ae 给候选 3 而非 −5，bd 给候选 −1 而非 −2，故不紧。从 a 搜索紧边图，首次发现可以依次保留 ac、cb、cd、de。到 e 时 ec 虽紧，但 c 已发现，跳过它：结果是四条树边，且 a 到 e 的树路径权重 $-7+5-3=-5$，符合距离。全部五条紧边则含 c→d→e→c 的零环。

Problem 6：所有边权为1的SSSP（p.2）

题解

从s做BFS，首次发现邻居时设d(v)=d(u)+1并记录前驱。队列按层扩展，时间O(n+m)、空间O(n)。

具体解析

队列先处理距离0的源点，再处理全部距离1的点，再距离2，依次递增。一个顶点第一次被发现时，不可能还有更短路线尚未探索：更短路线的前驱应位于更早层，早已处理过。因此首次发现距离最优。

标记应在入队时做，避免同一点被多个前驱反复入队。自取s→a、s→b、a→c、b→c，a、b距离1，c只需入队一次、距离2。DFS可能先走很长一支才找到目标，不能保证首次发现最短。

来源与证据

Sp10 p.1–2；松弛顺序参照L14 p.11–12的原地算法约定。两种Bellman–Ford表和Dijkstra结果已独立计算。