Why does floyd warshall just use one distance matrix?
I am reading pseudocode of floyd warshall algorithm
1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3 dist[v][v] ← 0
4 for each edge (u,v)
5 dist[u][v] ← w(u,v) // the weight of the edge (u,v)
6 for k from 1 to |V|
7 for i from 1 to |V|
8 for j from 1 to |V|
9 if dist[i][j] > dist[i][k] + dist[k][j]
10 dist[i][j] ← dist[i][k] + dist[k][j]
11 end if
But it just uses one dist matrix to save distances. I think there should be n dist matrices, where n is the number of vertices, Or at least we need two dist matrices. one stores the current shortest path at vertices k-1, the other stores the shortest path at vertices k, then the first stores the shortest path within k + 1, .... How can we simply store the new shortest path distances at vertices k in the original matrix for distances at the vertices k-1?
This image shows that we need D0, D1, D2 .... D (n)
source to share
You are partially right here.
Inference from Floyd Warshall's algorithm (i.e. NxN matrix) will NOT help to reconstruct the actual shortest path between any two given vertices.
These paths can be reconstructed if we store the parent matrix P such that it stores the last intermediate vertex used for each pair of vertices (x, y). Let's say this is the value of k.
The shortest path from x to y is the concatenation of the shortest path from x to k with the shortest path from k to y, which can be reconstructed given the matrix P.
Note, however, that for most pairing applications only the resulting distance matrix is required. These tasks are what the Floyds algorithm was designed for.
source to share
You are correct in the sense that the original formula requires that the calculations for the step k
use the calculations from the step k-1
:
This can be easily organized if, as you say, the first matrix is used to store values from step, the k-1
second is used to store values from k
, the first is used again to store values from k+1
, etc.
But, if we use the same matrix when updating values, in the above formula, we could accidentally use instead
if the value for the index
i,k
has already been updated in the current round k
, or we can get [TG33] instead if the value for the index has
k,j
been updated. Wouldn't this be a violation of the algorithm, since we are using the wrong recursive update formula?
Well, not quite. Remember that the Floyd-Warshall algorithm deals with the constraint "no negative cycles", which means that there is no cycle with edges that sum to a negative value. This means that for any, the k
shortest path from node k
to node k
is 0
(otherwise it would mean that there is a path from k
to k
with edges that add up to a negative value). So, by definition:
Now, let's just take the first formula and replace it j
with k
:
And then let’s replace "I" with "k" in the same formula:
So basically, will have the same meaning as and
, but
will have the same meaning as and
, so it doesn't really matter if those values are updated or not during the 'k' cycle and thus you can update the same matrix by reading it without breaking the algorithm.
source to share