algorithm - 为什么 Floyd-Warshall 以一种奇怪的方式记住这条路？

Question

我刚开始学习图算法，更具体地说是 Floyd-Warshall 算法。在维基百科中查看修改后的算法以允许重建路径，我注意到它保留了中间节点，而不是更合乎逻辑（在我看来）的方式 - 保存下一跳。此外，在课本中，方式是由一个到最后一个节点保存的。为什么要以这种方式保存路径？

Answer 1

没有一个“下一跳”。问题是以紧凑的方式存储足够的信息来重建从 i 到 j 的最短路径，对于节点 i 和 j 的任何组合。假设从 i 到 j1 的最短路径(k,j1)的最后一条边是 ，从 i 到 j2 的最短路径的最后一条边是(k,j2)。您将存储什么作为节点 k 的“下一跳”？

另一方面，假设 k 是从 i 到 j1 和从 i 到 j2 的路径上的最高索引顶点。给定算法存储的信息，可以递归地重建两条最短路径。一个是从 i 到 k 的最短路径，然后是从 k 到 j1 的最短路径。另一个是从 i 到 k 的最短路径，然后是从 k 到 j2 的最短路径。对于每个组合，在路径上存储一个节点就i,j足以重建任何最短路径。