Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

HEIR_OF_SLYTHERIN's blog

By HEIR_OF_SLYTHERIN, history, 5 years ago, In English

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??.

  • Vote: I like it
  • +12
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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,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).

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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!