Q对于每个v都由相应的处理。对于每个v都计算过邻边。这个绿色循环每次都计算了整个图像。但是这还不够因为要包含负权重所以可能出现被计算过的distTo变小的情况因此还有一个v次的i外层循环。但这样就能保证万无一失吗证明是接下来就是后面的证明要讲的内容吗A是的。Bellman-Ford 确实就是外层循环 V 次内层每次遍历所有 E 条边执行松弛。为什么需要 V 次外层因为负权重可能让已经更新过的distTo再次变小所以必须反复扫描直到所有可能的路径长度都被传播到。证明在第 63 页已经给出了。它的核心是一个归纳命题第 i 轮结束后对于每个顶点 vdistTo[v]等于从 s 到 v 且最多经过 i 条边的最短路径长度。证明的物理展开基础情况i 0初始化时distTo[s] 0其他顶点为 ∞。这对应“从 s 到 s 经过 0 条边”的长度为 0到其他顶点经过 0 条边不可达∞。命题成立。归纳步骤假设第 i 轮结束后所有distTo[v]都是“至多 i 条边”的最短路径长度。也就是每次循环只获得一条边这是最差情况但这个假设前提是对的吗现在执行第 i1 轮遍历所有边。考虑任意一条边 e v→w。如果存在一条从 s 到 w 且最多经过 i1 条边的最短路径它的最后一条边是 v→w。那么在这条路径中从 s 到 v 的部分最多经过 i 条边。根据归纳假设第 i 轮结束时distTo[v]已经是“至多 i 条边”的最短路径长度。所以当第 i1 轮遍历到边 v→w 时执行松弛textif (distTo[w] distTo[v] e.weight()) distTo[w] distTo[v] e.weight();这个候选值distTo[v] e.weight()就是那条“至多 i1 条边”的最短路径的长度。因此distTo[w]会被更新为正确值。遍历完所有边后所有“至多 i1 条边”的最短路径都会被找到。归纳结论第 V-1 轮结束后所有distTo[v]都是“至多 V-1 条边”的最短路径长度。为什么 V-1 轮就足够因为在一个没有负环的图中任何从 s 到 v 的最短路径都可以取一条简单路径不重复经过任何顶点。简单路径最多包含 V-1 条边因为图只有 V 个顶点。所以“至多 V-1 条边”的最短路径就是真正的最短路径。因此第 V-1 轮结束后所有distTo[]已经收敛到最终的最短路径长度。第 V 轮的作用检测负环如果图中存在负环那么最短路径可以包含任意多条边绕负环无限次总权重越来越小。此时“至多 V-1 条边”的最短路径不再是最终答案因为你可以绕负环获得更短的路径。Bellman-Ford 执行第 V 轮额外一轮。如果这一轮中仍然有边能够松弛即distTo[w]还能被改小说明存在一条路径包含至少 V 条边且更短。这条路径必然包含一个环。而只有负环才能让绕环后的路径更短。所以第 V 轮的松弛检测可以用来判断负环是否存在。回答你的问题“这样就能保证万无一失吗”在无负环的前提下是的。证明就是上面的归纳。第 V-1 轮后所有最短路径都已经被找到。第 V 轮用来检测负环如果第 V 轮还能松弛说明存在负环最短路径问题无解因为可以无限绕环变小。“接下来就是后面的证明要讲的内容吗”证明已经在第 63 页给出了。第 64 页是 FIFO 队列改进优化实际运行速度第 66-67 页是负环检测的具体方法。证明本身不需要更多内容。Q假设第 i 轮结束后所有 distTo[v] 都是“至多 i 条边”的最短路径长度。 也就是每次循环只获得一条边这是最差情况。但这个假设前提是对的吗为什么第i轮候所有的distTo就是至多i条边的最短路径了这很奇怪。因为满足松弛条件不代表就是最优边还有可能又被下一轮更新掉呢A我们来把证明的逻辑结构彻底拆开。归纳假设到底在说什么证明的归纳假设是第 i 轮结束后distTo[v]至多是“从 s 到 v、最多经过 i 条边”的最短路径长度。注意关键词是“至多”。它不是说“distTo[v]就是最终最优值”。它说的是“如果你限制路径最多只能走 i 条边那么distTo[v]不会比这个限制下的最优值更差。”你的质疑“满足松弛条件不代表就是最优可能下一轮又被更新”完全正确。distTo[v]确实可能在下一轮被更新得更小。但归纳证明并不否认这一点。它只是说在第 i 轮结束时如果你只看那些最多 i 条边的路径distTo[v]已经不比它们差了。它没有说distTo[v]不能再变小。它可以变小。变小的原因是在后续轮次中发现了经过更多条边但总权重更小的路径。为什么这个“至多 i 条边”的保证是成立的用归纳法基础情况i0第 0 轮初始化后distTo[s]0其他为 ∞。这对应“最多经过 0 条边”的路径只有 s 自己长度 0。其他顶点不可达∞ 是一个上界。成立。归纳步骤假设第 i 轮结束后distTo[v]至多是“最多 i 条边”的最短路径长度保证了最差情况但不排除一条边直达的异常好情况。现在执行第 i1 轮遍历所有边。考虑任意一条“最多 i1 条边”的路径它的最后一条边是 u→v。从 s 到 u 的部分最多有 i 条边。根据归纳假设第 i 轮结束时distTo[u]至多是这段前缀的长度。所以当第 i1 轮遍历到边 u→v 时候选值distTo[u] weight(u→v)至多是这条路径的总长度。因此distTo[v]会被更新为至多这个值。结论第 i1 轮结束后distTo[v]至多是“最多 i1 条边”的最短路径长度。关键点归纳证明不关心“是否下一轮会更新”归纳证明只证明了一个上界。它说在第 i 轮结束时distTo[v]不会比“限制在 i 条边内”的最优值更差。第 i1 轮可能找到更短的路径经过 i1 条边所以distTo[v]可能变小。但这不违反归纳假设。归纳假设只保证“至多 i 条边的路径已经被覆盖”不保证“没有更长的路径能更短”。为什么 V-1 轮后就能收敛因为任何从 s 到 v 的最短路径都可以取一条简单路径不重复顶点。简单路径最多 V-1 条边。所以第 V-1 轮结束后distTo[v]至多是“最多 V-1 条边”的最短路径长度。但“最多 V-1 条边”的最短路径长度 真正的最短路径长度因为最短路径本身最多 V-1 条边。所以distTo[v]至多等于最短路径长度。同时distTo[v]不可能小于最短路径长度因为它是某条路径的长度而最短路径是所有路径中最小的。所以distTo[v]恰好等于最短路径长度。总结你的疑问你的质疑“满足松弛条件不代表就是最优可能下一轮又被更新”是对的。归纳证明没有否认这一点。它只是逐轮推进一个“至多 i 条边”的上界。第 i 轮结束时上界是“i 条边内的最优值”。下一轮可能把这个上界推进到“i1 条边内的最优值”。直到 V-1 轮上界推进到“V-1 条边内的最优值”而这恰好就是全局最优值。Q我感觉还是不太行我现在能够理解到的就是如果你进行i轮循环的话确实会有最多是i条边的最短路径存在也能够保证在这个前提下的上限。同时我还可以从另外一个角度来看那就是假使这些点的顺序正好是继续那么确实我每一次i的外层循环是可以使之多一条边的等到V-1轮循环完成以后也会有V-1条边也就是所有边都含括在其中的最短路径这是上限。那么我现在能够理解到的就是这个外层循环所保证的仅仅是所有的点所有的边都被涵括进来但是你知道就算所有的点所有的边都被涵括后再进行一轮也可能是会有新的更新的。比如说如果我们第一轮就直接把点一到七给所有都遍历了一遍我们再去做第二轮外层循环还是可能找到更优的路径。因此并不是所有的点和边都被包括进来就可以保证这个路径是最优的保证最优路径的另有其他那么到底是什么保证了这个最优路径呢A你现在的困惑可以精确地表述为“遍历了所有点和所有边”不等于“找到了最优路径”。那到底是什么保证了最优答案分两层。第一层Bellman-Ford 保证的到底是什么它保证的不是“遍历了所有点和所有边”。它保证的是一个逐轮推进的上界第 i 轮结束后对于每个顶点 vdistTo[v]至多是“从 s 到 v、最多经过 i 条边的最短路径”的长度。注意这里的“最多 i 条边”不是“遍历了 i 条边”而是“路径的长度限制在 i 条边以内”。这个上界是逐轮收紧的第 1 轮后至多是“最多 1 条边”的最优值。第 2 轮后至多是“最多 2 条边”的最优值。...第 V-1 轮后至多是“最多 V-1 条边”的最优值。第二层为什么 V-1 轮后这个上界就是全局最优这一步依赖一个图论事实在一个没有负环的图中任何最短路径都可以取一条简单路径不重复顶点。简单路径最多 V-1 条边。所以全局最优路径的长度 ≤ V-1 条边。第 V-1 轮后distTo[v]至多是“最多 V-1 条边的最短路径”长度。但“最多 V-1 条边的最短路径”长度 全局最短路径长度因为全局最短路径本身就在这个范围内。所以distTo[v]至多等于全局最短路径长度。同时distTo[v]不可能小于全局最短路径长度因为它是某条路径的长度而全局最短路径是所有路径中最小的。所以distTo[v]恰好等于全局最短路径长度。回到你的质疑“就算所有的点和边都被涵括后再进行一轮也可能会有新的更新。”在有负环的图中这是对的。如果存在负环你可以无限绕环每绕一次路径长度都变小所以永远会有新的更新。在没有负环的图中这是不对的。因为任何最短路径最多 V-1 条边。第 V-1 轮后所有“最多 V-1 条边”的路径都已经被考虑过了。再执行第 V 轮遍历所有边时没有任何一条边能提供比当前distTo更小的候选值。所以第 V 轮不会有任何更新。如果第 V 轮还有更新那就说明存在一条包含至少 V 条边的路径其长度小于当前distTo。这条路径必然包含一个环。而只有负环才能让绕环后的路径更短。所以第 V 轮的更新直接证明了负环存在。总结保证最优的不是“遍历了所有点和边”而是“逐轮推进的路径边数上界”加上“最短路径最多 V-1 条边”这个图论事实。第 i 轮保证覆盖“最多 i 条边”的路径。第 V-1 轮覆盖了所有可能的最短路径因为最短路径 ≤ V-1 条边。第 V 轮如果还有更新说明存在负环最短路径问题无解。在没有负环的情况下第 V-1 轮结束后distTo[]已经收敛不会再有任何更新。Q我明白了我不是不能推导出这件事我是不能理解这件事。通过数学归纳法我确定了它的正确性但是感官的认识上——为什么经过i轮可以计算出最长为i条边的最短路径这是如何被保证的A你问的是机制层面的“为什么”为什么恰好经过 i 轮就能算出至多 i 条边的最短路径我们不用归纳法而是用一条具体的路径来追踪它的物理传播过程。物理机制波前传播假设有一条从 s 到 v 的路径经过 k 条边s → a₁ → a₂ → ... → aₖ v第 1 轮遍历所有边时边 s→a₁ 被处理。因为distTo[s]0所以distTo[a₁]被更新为边 s→a₁ 的权重。此时从 s 出发经过 1 条边能到达的顶点其distTo变成了有限值。第 2 轮遍历所有边时边 a₁→a₂ 被处理。因为distTo[a₁]在第 1 轮结束时已经是有限值所以distTo[a₂]被更新为distTo[a₁] weight(a₁→a₂)。此时经过 2 条边能到达的顶点被激活。第 k 轮边 aₖ₋₁→aₖ 被处理。distTo[aₖ₋₁]已经在第 k-1 轮结束时被激活。所以distTo[aₖ]被更新。结论一条经过 k 条边的路径它的效果最多在第 k 轮结束时传播到路径的终点。为什么“最多”而不是“恰好”如果边的遍历顺序恰好是沿着路径从前向后那么这条路径可以在一轮内全部传播完因为每处理一条边下一个顶点就被激活紧接着处理下一条边。但如果边的遍历顺序是反的先处理 aₖ₋₁→aₖ再处理 aₖ₋₂→aₖ₋₁...那么第 1 轮只能激活 a₁因为只有 s→a₁ 的起点 s 已经有值第 2 轮激活 a₂...第 k 轮激活 aₖ。最坏情况下每轮只能向前推进一条边。所以 k 条边的路径最多需要 k 轮才能把它的效果完全传播到终点。为什么 V-1 轮后一定收敛因为任何最短路径都是简单路径不重复顶点简单路径最多 V-1 条边。所以任何最短路径的效果最多在第 V-1 轮结束时传播完毕。第 V-1 轮后所有顶点都已经被它们的最短路径激活过。distTo[]不再变化。回到你的感官困惑你无法“感知”这个机制是因为你在试图一次性想象所有路径同时传播。但实际物理过程是第 1 轮只激活距离 s 为 1 条边的顶点。第 2 轮激活距离 s 为 2 条边的顶点。...每轮只向前推进一条边。这个过程是串行的、有限步的。你可以在纸上画一条 5 个顶点的链手动追踪 4 轮亲眼看到每一轮激活一个新顶点。你不需要感知“无限”你只需要追踪 4 轮有限步骤。你之前的困惑来自“遍历了所有边”这个动作。但遍历不等于激活。一条边能否生效取决于它的起点是否已经被激活。起点的激活又依赖上一轮的传播。所以轮次决定了传播深度而不是遍历次数。Q或许你的意思是我们第一次只保证s1下的最短路径第二次保证一个s1-s2下的最短路径我们要保证的是作为路经前缀的那一段是最优的A你的方向是对的但需要把“路径前缀最优”这个说法精确化。Bellman-Ford 每轮保证的不是“某一条特定路径的前缀最优”而是第 i 轮结束后对于每个顶点 vdistTo[v]不会大于任何一条从 s 到 v、边数不超过 i 的路径的长度。换句话说它保证的是所有长度 ≤ i 的路径这个集合中的最短距离的上界。它同时覆盖所有可能的前缀而不是单独保证某一条路径的前缀。用你的话来说第 1 轮保证distTo[a]不会大于任何“从 s 到 a、只走 1 条边”的路径长度。第 2 轮保证distTo[b]不会大于任何“从 s 到 b、最多走 2 条边”的路径长度。...第 i 轮保证所有顶点都覆盖了“最多 i 条边”的路径。所以不是“先保证 s1 的最短路径再保证 s1→s2 的最短路径”而是每一轮把路径长度限制放宽一条边同时更新所有顶点。最终当 i 达到 V-1 时限制放宽到“最多 V-1 条边”而所有简单路径都不超过 V-1 条边因此所有可能的最短路径都被覆盖distTo收敛到全局最优。你不需要感知“无限”只需要理解每轮把路径边数上限加一直到覆盖所有简单路径。一个很抽象的小东西……
