Editing Floyd–Warshall algorithm (section)

==Path reconstruction==

The Floyd–Warshall algorithm typically only provides the lengths of the paths between all pairs of vertices. With simple modifications, it is possible to create a method to reconstruct the actual path between any two endpoint vertices. While one may be inclined to store the actual path from each vertex to each other vertex, this is not necessary, and in fact, is very costly in terms of memory. Instead, we can use the [[shortest-path tree]], which can be calculated for each node in <math>\Theta(|E|)</math> time using <math>\Theta(|V|)</math> memory, and allows us to efficiently reconstruct a directed path between any two connected vertices.

=== Pseudocode ===

The array {{code|prev[u][v]}} holds the penultimate vertex on the path from {{code|u}} to {{code|v}} (except in the case of {{code|prev[v][v]}}, where it always contains {{code|v}} even if there is no self-loop on {{code|v}}):<ref>{{Cite web|url=https://books.goalkicker.com/AlgorithmsBook/|title = Free Algorithms Book}}</ref>

 '''let''' dist be a <math>|V| \times |V|</math> array of minimum distances initialized to <math>\infty</math> (infinity)
 '''let''' prev be a <math>|V| \times |V|</math> array of vertex indices initialized to '''null'''
 
 '''procedure''' ''FloydWarshallWithPathReconstruction''() '''is'''
     '''for each''' edge (u, v) '''do'''
         dist[u][v] = w(u, v)  ''// The weight of the edge (u, v)''
         prev[u][v] = u
     '''for each''' vertex v '''do'''
         dist[v][v] = 0
         prev[v][v] = v
     '''for''' k '''from''' 1 '''to''' |V| '''do''' ''// standard Floyd-Warshall implementation''
         '''for''' i '''from''' 1 '''to''' |V|
             '''for''' j '''from''' 1 '''to''' |V|
                 '''if''' dist[i][j] > dist[i][k] + dist[k][j] '''then'''
                     dist[i][j] = dist[i][k] + dist[k][j]
                     prev[i][j] = prev[k][j]

 '''procedure''' ''Path''(u, v) '''is'''
     '''if''' prev[u][v] = null '''then'''
         '''return''' []
     path = [v]
     '''while''' ''u'' ≠ ''v'' '''do'''
         v = prev[u][v]
         path.prepend(v)
     '''return''' path