Floyd Warshall: computing top-k shortest paths per vertex pair

0
votes

In the Floyd-Warshall algorithm, the shortest path cost is computed for any pair of vertices. Additional book-keeping allows us to keep the actual path (list of vertices) on the shortest path.

How can I extend Floyd-Warshall so that for any pair of vertices, the top-K shortest paths are found? For example, for K=3, the result would be that the 3 shortest paths are computed and maintained?

I have been using the Java implementation from Sedgewick.

2
algorithmgraphshortest-pathfloyd-warshall
Do you mean K different paths of same minimal length or K paths of different length, however being shorter than any other path? - Codor
The second one is what I meant. - stackoverflowuser2010
I take back what I said earlier: Floyd--Warshall is not a suitable base on which to build this. The dynamic programming structure of F--W makes it more or less infeasible to detect duplicate paths efficiently. - David Eisenstat
@DavidEisenstat: Can you recommend a different algorithm as a base? I still want to solve all-pairs shortest path with top-k routes per pair of end points. - stackoverflowuser2010
en.wikipedia.org/wiki/K_shortest_path_routing ? - David Eisenstat

2 Answers

2
votes

Sounds more like Dijkstra would be simpler to modify for returning N shortest paths. The search is allowed to enter the vertex until K shortest alternatives has entered the vertex.

For more information you can check wikipedia article

0
votes

You may call the loop multiple times using an extra condition that could like

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; } } } This code will calculate the K minimum distances that are different. Hope it would help you.