I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page:
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
Our professor told us that the loop for k MUST be outside the i and j loops. I am unable to understand why this must be the case. He said that if k is inside we will only compute the best 2 edged or 1 edge path from i to j. I just don't see it. Can someone help?