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]?
1 Answers
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]).
Related