c++ - 具有路径重建的 Floyd–Warshall 算法找不到路径

Question

我试图通过计算所有对之间的最短路径，使用 Floyd-Warshall 算法找到源和目标之间的最短路径。

我需要找到最短的路径，而不仅仅是距离。这就是我想要做的:
我将第一个顶点存储在从i到j的最短路径上。每当从 i 到 j 的最短路径更新并且它现在经过 k 时，我将从 i 到 j 的最短路径上的第一个顶点设置为从 i 到 k 的最短路径上的第一个顶点。

/*first[i][j] is the first vertex after i on the shortest path from i to j.
first[i][j] is initially j if there is an edge from i to j and the dist[i][j] is the weight of the edge. Otherwise f[i][j] is -1 and the cost is infinity.
*/
for(k = 0; k < N; ++k){
    for(i = 0; i  < N; ++i){
        for(j = 0; j < N; ++j){
            if(dist[i][j] >= dist[i][k]+dist[k][j]){
               dist[i][j] = dist[i][k]+dist[k][j];
               //When the distance is updated, update first[i][j]
               first[i][j] = first[i][k];
            }
        }
    }
}

这个算法的问题是，当我在下图运行这个算法时，这个算法找到的路径是一个无限循环。

这是算法计算的第一个矩阵:

4 4 4 4 4 4 
2 2 2 2 2 2 
5 5 5 5 5 5 
1 1 1 1 1 1 
0 0 0 0 0 0 
2 2 2 2 2 2 

根据算法，从 0 到任何其他顶点的最短路径上的第一个顶点为 4，但从 4 到任何其他顶点的最短路径上的第一个顶点为 0。

• 为什么该算法会以这种方式运行？
• 是否有另一种方法来计算每条路径上的第一个(在源之后)顶点同时我正在计算路径的长度？

我已阅读 Wikipedia文章和一些关于 SO 的问题，但它们没有太大帮助。

Answer 1

您的 dist 矩阵似乎已正确计算，但您的 first 矩阵添加似乎存在零成本边问题。

查看代码的这个略微修改的 Python 版本，它使用 0.01 作为所有自边和其他 0 成本边的成本。

http://pastebin.com/fub60HA5

该代码输出(希望)正确的 dist 和 first 矩阵

[0.01,  inf,  inf, 0.01, 0.01,  inf]
[0.02, 0.01, 0.01, 0.01, 0.03, 0.02]
[0.01,  inf, 0.01, 0.02, 0.02, 0.01]
[ inf,  inf,  inf, 0.01,  inf,  inf]
[0.01,  inf,  inf, 0.02, 0.01,  inf]
[0.02,  inf, 0.01, 0.01, 0.03, 0.01]

和

[   0, None, None,    3,    4, None]
[   2,    1,    2,    3,    2,    2]
[   0, None,    2,    5,    0,    5]
[None, None, None,    3, None, None]
[   0, None, None,    0,    4, None]
[   2, None,    2,    3,    2,    5]