Floyd-Warshall's algorithm--
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
dist[u][v] ← w(u, v) // The weight of the edge (u, v)
for each vertex v do
dist[v][v] ← 0
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end if
can someone explain why the order of the last three "for statements(for k from 1 to |V|, for i from 1 to |V|, for j from 1 to |V|" doesn't matter the result of the program??.
The order does matter. The Floyd-Warshall algorithm is actually only a "DP in disguise": Define $$$f(i, j, k)$$$ as the weight of the shortest path between vertex $$$i$$$ and $$$j$$$, such that only intermediate vertices $$$1, 2, \ldots k$$$ are used. This DP can be computed in increasing order of $$$k$$$, hence it's the outermost for loop. The $$$k$$$-dimension of the DP table can be optimised away to get the well known implementation.
In fact the order actually doesn't matter "too much". If you repeat the entire algorithm 3 times with incorrect loop order, you'll get the correct results anyways (see here).
Wow, I learned FW like, 12 years ago and just memorized it instead of understanding it. This was a really good explanation (once you explained it this way, it just clicked since this is actually a very common style of DP). Thanks!