所以我试图理解 Floyd-Warshall 算法，虽然我可以实现它并清楚地看到它确实有效，但我不完全确定为什么它之所以有效是因为一件事:
因为对于每一对顶点，我们检查其他两对顶点是否允许我们在我们当前正在处理的对之间有更短的路径，并且在开始时我们只知道从顶点到它们自己的距离(这是所有 0) 和没有中间顶点的距离(这是我们的输入)，我们如何确定我们首先处理的顶点将被赋予“真正的”最短路径？我的意思是 - 在处理前几个顶点对时，我们所知道的只是输入和一些无穷大，所以为什么保证它足以找到最短路径并且在路上的某个地方我们不会找到更有利可图的东西在开始的顶点使用？
最佳答案
我相信这个想法是在每个阶段 i 算法找到每对顶点之间的最短路径，限制路径只能使用顶点 1..i
诀窍在于归纳步骤。
考虑最短路径 a->b 并限制它只使用顶点 1..i
有两种情况，路径要么经过 i，要么不经过。
如果不是，则最短路径与上一轮没有变化。
如果确实经过 i，那么路径必须是 a->i->b 的形式，总成本是距离 a->i 加上距离 i->b，其中每个距离都是从上一轮开始有效。
另一种看待这个问题的方法是注意，在算法过程中，随着找到更好的路径，特定节点对(例如 1 和 2)之间的距离将逐渐减小。最初距离将是直接距离 1->2，但如果有更好的路径，例如 1->10->2，这将在算法的第 10 阶段找到。
这感觉我们可能会出错，因为我们在多个点使用了距离 1->2 并且感觉我们可能使用了错误的值。然而，如果你还记得在每个阶段我们都找到了“什么是 1 和 2 之间的最短路径，我们只能使用顶点 1..i 的限制”这个问题的确切答案，也许会更清楚
关于algorithm - 对 Floyd-Warshall 的基本前提感到困惑，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23701752/