我刚刚开始学习图形算法，更具体地说 - 弗洛伊德-沃歇尔算法。在维基百科中查看修改为允许重建路径的算法，我注意到它保留了中间节点，而不是更合乎逻辑（在我看来）的方式 - 保存下一跳。此外，在课程书中，方式由最后一个节点保存。为什么要以这种方式保存路径？
没有一个"下一跳"。问题在于以紧凑的方式存储足够的信息，以便为节点 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组合，在路径上存储一个节点就足以重建任何最短路径。