algorithm - Floyd-Warshall 算法可视化 : length is known but predecessors aren't

Question

我正在尝试可视化 Floyd-Warshall 算法。问题是当它找到路径长度时，不需要有前辈在找到的时候准备好构建这条路径，所以我不能实际显示路径，虽然距离已经知道了。让我解释一下维基百科的例子:

这是原始图的邻接矩阵:

如果我们看第 3 行，我们会看到彼此相邻的两个无穷大。让我们跳到第 3 次迭代的开始(或 k)。

到目前为止一切正常。但这是距离矩阵在 k=3, i=3, j=1 上的样子(我使用 INT_MAX 作为无穷大):

这里我们看到，虽然第 3 行第 1 列元素的最短路径是已知的，但我无法真正构建到它的路径并显示它，因为它旁边的元素是未知的。因此构建路径失败，直到下一个节点自行解析我才能显示它。

我如何找到这些丢失的路径并在所有元素已知后显示它们？我想我需要一些循环，如果已知路径长度 j 小于当前路径长度，它会触发并显示所有路径，直到 j-1(谢天谢地 i 是已知的，而且我认为不应该改变)。我说得对吗？

附言我用 C++ 编写它，如果您愿意，可以提供我的实现。我认为在写作时没有必要，因为它是一般算法问题，并不专门属于 C++(以及我的实现味道)。谢谢。

Answer 1

我不确定我是否理解您的问题，但我会尝试在这里解决它。相信你在floyd-warshall算法的过程中随时都想知道如何构造路径。只有在完成给定 k 的矩阵计算后，调用此类路径查找算法才有意义。然后 Path(u, v) 将是 u 和 v 之间的最小路径，仅使用小于或等于 的中间顶点>k。如果您尝试在给定的 k 循环尚未完成运行时调用它，该算法将返回一个路径，该路径不考虑使用顶点 k 的所有改进作为中间顶点。很难想象它会返回哪条路径，但它只会将 k 视为 i 和 j< 对之间路径的中间顶点 你已经在这个循环中计算过了。

更多信息在这里:https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Path_reconstruction