파이썬과 함께하는 자료구조 8장 그래프(알고리즘) 3번째, 플로이드 마샬

원래는 다익스트라 먼저 나와야 하는데

그 부분이 아직 정리가 덜 됬다.

플로이드 마샬의 경우 기존에 우리가 해왔던 임의의 정점, 또는 한 정점으로 부터가 아닌

모든 정점에 대한 계산을 실시한다.

바꿔 말하자면 X에서 Y로의 경로에 N 노드를 거치는게 빠르냐 아니냐를 따지는 것이다.

그렇기에 

1. X->Y의 비용

2. X->N + N -> Y의 비용

이 두개의 비용을 비교하여 최소 비용으로 업데이트 한다.

(아래 내용은 동빈나님의 블로그를 필기한 것이다, https://blog.naver.com/ndb796/221234427842)

위를 코드로 구성하자면

D = 인접 리스트

for i in range(len(D):

for k in range(len(D)):

for j in range(len(D)):

D[i][k] = min(D[i][k], D[i][j] + D[j][k])

매우 간단한데 이해가 바로 오지는 않는다.

위에 예시에 D[2,3] 이 누구랑 비교 되는지 확인하면서 생각해야한다.