CODEWITHSUNDEEP
c++graph-algorithmshortest-pathfloyd-warshall
2147483647
2147483647

Reputation: 1197

Floyd–Warshall algorithm with path reconstruction does not find a path

I am trying to find a shortest path between a source and a target using Floyd-Warshall's algorithm by computing the shortest paths between all pairs.

I need to find the shortest path not just the distance. This is what I'm trying to do:
I store the first vertex on the shortest path from i to j. Whenever the shortest path from i to j is updated and it now goes through k, I set the first vertex on the shortest path from i to j to that on the shortest path from i to 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];
            }
        }
    }
}

The problem with this algorithm is that when I run this algorithm on the following graph, the path found by this algorithm is an infinite cycle.

the graph

Here is the first matrix computed by the algorithm:

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

The first vertex on the shortest path from 0 to any other vertex, according to the algorithm is 4, but the first vertex on the shortest path from 4 to any other vertex is 0.

I have read the Wikipedia article and also some questions on SO but they weren't of much help.

Upvotes: 3

Views: 6051

Answers (1)

mic_e
mic_e

Reputation: 5830

Your dist matrix already seems to be calculated correctly, but your first matrix additions seem to have a problem with zero-cost edges.

See this slightly modified python version of your code, which uses 0.01 as cost for all self-edges and other 0-cost edges.

http://pastebin.com/fub60HA5

That code outputs the (hopefully) correct dist and first matrices

[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]

and

[   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]

Upvotes: 1

Related Questions