弗洛伊德·沃肖尔:计算每个顶点对的top-k最短路径

Question

在弗洛伊德-沃肖尔算法中，为任何一对顶点计算最短路径成本。额外的记账使我们能够将实际路径(顶点列表)保持在最短路径上。

我如何扩展Floyd-Warshall，以便对任何一对顶点，都能找到top-K最短路径？例如，对于K=3，结果将是计算并维护3条最短路径？

我一直在使用来自Sedgewick的Java implementation。

Answer 1

听起来Dijkstra更容易修改以返回N个最短路径。允许搜索进入顶点，直到K个最短备选方案进入顶点。

有关更多信息，请查看wikipedia article

Answer 2

您可以使用如下所示的额外条件多次调用循环

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个不同的最小距离。希望能对你有所帮助。