c++ - 存储最短路径

Question

我指的是本教程：http ://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/

作者提到了这一点：

我们还可以通过将前驱信息存储在单独的二维矩阵中来修改解决方案以打印最短路径。

我对这个前身信息有点困惑。

那么，如何存储路径以供以后显示呢？

Answer 1

如果要重建从节点 x_1 到 x_n 的路径，可以通过转到节点 x_2 并重建从 x_2 到 x_n 的路径来实现。如果 x_1 改变，从 x_2 到 x_n 的路径不会改变。因此，您要存储的是从 x_1 到 x_n 时下一个节点的信息。这可以通过 |V| 来完成 x |V| 矩阵，其中条目 [i][j] 给出从 i 到 j 的路径上的下一个节点的索引。

在这部分代码中

if (dist[i][k] + dist[k][j] < dist[i][j])
    dist[i][j] = dist[i][k] + dist[k][j];

您应该将分配添加到下一个节点矩阵。