Floyd-Warshall algorithm shortest path

Question

I implemented Floyd-Warshall algorithm. According to their matrices, I can get the correct result, about the shortest path between two places and their distance. My question is how to print the shortest distance from i to j. I made some researches and I found an algorithm like that. Can anyone explain me how should it be, or how does it works, or say any other suggestion?

PrintShortestPath(P,i,j){
    if(i==j) print i
    else if (P[i][j]==NULL)
        print "No path from i to j"
    else{
        PrintShortestPath(P,i,P[i][j])
        print j
    }
}

Answer 1

Floyd's algorithm considers all paths between two nodes and keeps the cheapest found this far. Your code goes about this recursively. Here is another implementation with a good explanation for this in C: http://www.fearme.com/misc/alg/node88.html

You may also consider Dijkstra's algorithm, which might be better performing for sparse graphs.

--L.

Answer 2

The matrix P in the algorithm that you posted is the predecessor matrix. It lists for every path i -> j the predecessor.

This must be computed together with the distance matrix:

• P[i,j] is initalized to NULL forall i,j
• In the innermost loop of FW update P[i,j] if you find a shorter path passing from node k (use P[k,j]).

I can be more precise if you post your solution for the distance.