플로이드-워셜(Floyd-Warshall)

 

플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드 워셜 알고리즘은 그래프의 모든 노드에서 다른 모든 노드로 가는 최소 비용을 구하는 알고리즘입니다.

 

원리

 

1에서 3으로 가는 최단 거리를 구한다고 생각해봅시다.

1에서 3으로 바로 가는 거리는 13입니다.

하지만, 1에서 2로 갔다가, 2에서 3으로 가는 거리는 2 + 3으로 5입니다.

즉, 2를 거쳐가는 1 -> 2 -> 3이 최단 거리가 됩니다.

 

위와 같이 플로이드 워셜 알고리즘은 현재 내가 알고 있는 최단 거리와 다른 노드를 거쳐갈 때의 최단 거리를 비교하여 갱신합니다.

이를 점화식으로 나타내면 다음과 같습니다

 

# A에서 B로 가는 최단 거리 D[A][B]
# 경유 노드 K

D[A][B] = min(D[A][B], D[A][K] + D[K][B])

 

코드화

플로이드 워셜 알고리즘은 3중 for문을 통해 코드로 작성할 수 있습니다.

 

for k in range(n): # 경유지 선정 k
    for a in range(n):
        for b in range(n):
            current_val = D[a][b]
            compare_val = D[a][k] + D[k][b]

            D[a][b] = min(current_val, compare_val) # 현재 최솟값과 경유 최솟값 비교

 

3중 for문의 가장 밖의 for문을 통해 경유지를 설정한다는 점에 유의하세요.

이를 통해 모든 노드에서 여러 개의 경유지를 통해 도달할 수 있는 최소 거리를 구할 수 있습니다.

 

시간 복잡도

플로이드 워셜 알고리즘은 삼중 for 문을 통해 구현되므로, 시간 복잡도는 O(N^3)입니다.