doubt regarding floyd warshalls algorithm

Правка en1, от HEIR_OF_SLYTHERIN, 2020-06-22 18:51:26

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

Теги graphs, floyd-warshall

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский HEIR_OF_SLYTHERIN 2020-06-22 18:58:16 0 (published)
en2 Английский HEIR_OF_SLYTHERIN 2020-06-22 18:54:48 12 (saved to drafts)
en1 Английский HEIR_OF_SLYTHERIN 2020-06-22 18:51:26 692 Initial revision (published)