[CS] 플로이드 워셜 이해 안되는 점

과연 시작되는 순서가 바뀐다고 해도 결과는 같을까? 

결과적으로 for문의 순서를 바꿔도 같고 iteration 숫자를 바꿔도 같다.

왜 그런지는 잘 모르겠다.

 

def floyd():
    # k는 경유하는 노드
    
      for i in range(1, NODE_CNT+1):
          for j in range(1, NODE_CNT+1):
            for k in range(1, NODE_CNT+1):
                # k노드를 경유하는 거리값이 더 작으면 갱신
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

if __name__ == "__main__":
    NODE_CNT = 4
    INF = 2147000000
    graph = [[INF] * (NODE_CNT + 1) for _ in range(NODE_CNT + 1)]
    for i in range(1, NODE_CNT + 1):
        graph[i][i] = 0
    graph[1][2] = 1
    graph[2][1] = 1
    graph[1][3] = 5
    graph[3][1] = 5
    graph[2][3] = 2
    graph[3][2] = 2
    graph[2][4] = 8
    graph[4][2] = 8
    graph[3][4] = 2
    graph[4][3] = 2
    
    floyd()
    
    for x in graph[1:]:
        print(x[1:])

 

Reference

---

https://c4u-rdav.tistory.com/51

[파이썬으로 배우는 알고리즘] 플로이드 워셜(Floyd Warshall) 알고리즘