我试图通过计算所有对之间的最短路径来使用 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];
}
}
}
}
这个算法的问题是，当我在下图上运行这个算法时，这个算法找到的路径是一个无限循环。
这是first算法计算的矩阵：
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。
- 为什么该算法会以这种方式运行？
- 当我计算路径的长度时，是否有另一种方法来计算每条路径上的第一个（在源之后）顶点？
我已经阅读了维基百科的文章以及一些关于 SO 的问题，但它们并没有太大帮助。