In floyd warshell algorithm we keep any node y as intermediate node and update distance from one node to another(for all nodes) via intermediate node y. dp[x][y] = min( dp[x][y] , dp[x][z] + dp[z][y]) but the problem here is dp[x][z] may be updated later which means dp[x][z] may not be the minimum distance of reaching x to z, how can we use the dp[x][z] to calculate dp[x][y]?
The implementation of Floyd--Warshall obscures the mathematical structure of how it works.
The proof would still go through if you updated dp
in rounds, e.g., for all x
and y
, do dp'[x][y] = min(dp[x][y], min_z(dp[x][z] + dp[z][y]))
and then copy dp = dp'
. This is enough to ensure that dp[x][y]
is at most the length of the shortest path from x
to y
through the various z
that we've iterated over so far.
Conversely, we don't end up underestimating dp[x][y]
by doing in-place updates because every time we do an update, there's a path that achieves the new value (specifically, the path represented by the value of dp[x][z]
followed by the path represented by the value of dp[z][y]
).