Print shortest b / w path for given nodes using modified floyd warshall

Question

I read the approach suggested by Wikipedia to print the shortes b / w path with two given points in a graph, modifying the Floyd Warsall algorithm. I encoded this, but this does not give the expected result:

• Initialize all elements in minimumDistanceMatrix[i][j] to the corresponding weights in the graph and all elements in the matrix shortestPathCalculatorMatrix [i][j] to -1.

• Then:

   // Find shortest path using Floyd–Warshall algorithm for ( unsigned int k = 0 ; k < getTotalNumberOfCities() ; ++ k) for ( unsigned int i = 0 ; i < getTotalNumberOfCities() ; ++ i) for ( unsigned int j = 0 ; j < getTotalNumberOfCities() ; ++ j) if ( minimumDistanceMatrix[i][k] + minimumDistanceMatrix[k][j] < minimumDistanceMatrix[i][j] ) { minimumDistanceMatrix[i][j] = minimumDistanceMatrix[i][k] + minimumDistanceMatrix[k][j]; shortestPathCalculatorMatrix [i][j] = k; } 

• Then:

   void CitiesMap::findShortestPathListBetween(int source , int destination) { if( source == destination || source < 0 || destination < 0) return; if( INFINITY == getShortestPathBetween(source,destination) ) return ; int intermediate = shortestPathCalculatorMatrix[source][destination]; if( -1 == intermediate ) { pathCityList.push_back( destination ); return ; } else { findShortestPathListBetween( source, intermediate ) ; pathCityList.push_back(intermediate); findShortestPathListBetween( intermediate, destination ) ; return ; } } 

PS: pathCityList is a vector that is considered empty before calling findShortestPathListBetween . At the end of this call, this vector has all the intermediate nodes in it.

Can someone please indicate where I could be wrong?

Answer 1

The Wikipedia article is terrible. In addition to the incorrect representation (in my opinion) of the canonical form of the Floyd-Warsall algorithm, it is an erroneous pseudocode.

Its much simpler (and more directly) not to iterate over indexes, but over vertices. In addition, each predecessor (usually denoted by π , not next ) should point to it, well, the predecessor, and not to a temporary temporary vertex.

With that in mind, we can fix their broken pseudo-code.

 for each vertex v dist[v][v] ← 0 for each edge (u,v) dist[u][v] ← w(u,v) // the weight of the edge (u,v) for each vertex k for each vertex i for each vertex j if dist[i][k] + dist[k][j] < dist[i][j] then dist[i][j] ← dist[i][k] + dist[k][j] next[i][j] ← next[k][j] 

Note that Ive changed the three nested loops to iterate over the vertices, not the indexes, and Ive fixed the last row to refer to the previous node, and not to any intermediate node.

An explanation of why this is correct and how the predecessor matrix works can be found on Algoritmy.net .

The above requires some initialization. Fortunately, this is easy, since we already know the first predecessor of each node: if theres a direct path from i to j , then i is the predecessor of j . If there is no direct path, then there is no predecessor.

 for each vertex i for each vertex j if w(u,v) = ∞ then next[i][j] ← NIL else next[i][j] ← i 

NIL is just a placeholder for any value other than vertices. In object oriented code, this will usually be a null reference / pointer. When implementing a graph as an adjacency matrix, it can be any index that does not correspond to a vertex, for example. -1 or | V | +1

They also provide corrected reconstruction of the path:

 function path(P, i, j) if i = j then write i else if next[i][j] = NIL then write "no path exists" else path(P, i, P[i][j]) write j