我试图通过计算所有对之间的最短路径,使用 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 的问题,但它们没有太大帮助。
最佳答案
您的 dist
矩阵似乎已正确计算,但您的 first
矩阵添加似乎存在零成本边问题。
查看代码的这个略微修改的 Python 版本,它使用 0.01
作为所有自边和其他 0 成本边的成本。
该代码输出(希望)正确的 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]
关于c++ - 具有路径重建的 Floyd–Warshall 算法找不到路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22789126/