플로이드 와샬 알고리즘 (Python)

삼중 for문으로 모든 정점을 순회하면서
"나 거쳐서 갈 수 있는 놈들 있어? 싹 다 갱신해봐"

가 플로이드 와샬 알고리즘이다.

 

이행적 폐쇄 (Transitive Closure)

비용 상관없이 갈 수 있느냐 없느냐만 따져보면

for k in range(n):  # 나 A를 거쳐서
    for i in range(n):  # B 너가
        for j in range(n):  # C로 갈 수 있니?
            if closure[i][k] and closure[k][j]:
                closure[i][j] = True

 

첫번째 for문 요소 : "나 A를 거쳐서"
두번째 for문 요소 : "B 너가"
세번째 for문 요소 : "C로 갈 수 있니?"

"나 A를 거쳐서, B 너가, C로 갈 수 있니?"

 

최소 비용 (Floyd-Warshall Algorithm)

최소 비용 버전으로 보면

for k in range(n):  # 나 A를 거쳐서 가는게
    for i in range(n):  # B 너가
        for j in range(n):  # C로 갈 때 더 빨리 가니?
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

 

첫번째 for문 요소 : "나 A를 거쳐서 가는게"
두번째 for문 요소 : "B 너가"
세번째 for문 요소 : "C로 갈 때 더 빨리 가니?"

"나 A를 거쳐서 가는게, B 너가, C로 갈 때 더 빨리 가니?"