This code uses only one array `dist`, but works correctly. Why? (Floyd–Warshall Algorithm)

30 views Asked by At

The following code is a python code for Floyd–Warshall Algorithm.
After this code terminates, dist[x][y] is the shortest distance from the node x to the node y.

for i in range(N):
  dist[i][i] = 0

for k in range(N):
  for x in range(N):
    for y in range(N):
      dist[x][y] = min(dist[x][y], dist[x][k] + dist[k][y])

The above code uses only one array dist, but works correctly.
We don't need to modify the above code as follows:

for i in range(N):
  dist[i][i] = 0

for k in range(N):
  for x in range(N):
    for y in range(N):
      next_dist[x][y] = min(dist[x][y], dist[x][k] + dist[k][y])
  for x in range(N):
    for y in range(N):
      dist[x][y] = next_dist[x][y]

Why?

0

There are 0 answers