在 Floyd-Warshall 算法中，计算任意一对顶点的最短路径成本。额外的簿记使我们能够将实际路径（顶点列表）保持在最短路径上。
如何扩展 Floyd-Warshall 以便为任何一对顶点找到前 K 个最短路径？例如，对于 K=3，结果会是计算和维护 3 条最短路径吗？
我一直在使用 Sedgewick 的Java 实现。
问问题
1059 次
2 回答
2
听起来更像 Dijkstra 会更容易修改以返回 N 最短路径。允许搜索进入顶点，直到 K 最短的备选方案进入顶点。
有关更多信息，您可以查看维基百科文章
于 2014-08-23T23:58:34.640 回答
0
您可以使用可能喜欢的额外条件多次调用循环
for (int i = 0; i < V; i++) {
// compute shortest paths using only 0, 1, ..., i as intermediate vertices
for (int v = 0; v < V; v++) {
if (edgeTo[v][i] == null) continue; // optimization
for (int w = 0; w < V; w++) {
if (distTo[v][w] > distTo[v][i] + distTo[i][w] && distTo[v][i]+distTo[i][w]>min[k]) { //min[k] is the minimum distance calculated in kth iteration of minimum distance calculation
distTo[v][w] = distTo[v][i] + distTo[i][w];
edgeTo[v][w] = edgeTo[i][w];
}
}
// check for negative cycle
if (distTo[v][v] < 0.0) {
hasNegativeCycle = true;
return;
}
}
}
此代码将计算不同的 K 个最小距离。希望它会帮助你。
于 2014-09-06T22:00:33.677 回答