doubt regarding floyd warshalls algorithm

Правка en3, от HEIR_OF_SLYTHERIN, 2020-06-22 18:58:16

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)