[알고리즘] 플로이드 워셜

플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다.

플로이드 워셜 알고리즘은 다익스트라 알고리즘처럼 단계마다 최단 거리를 가지는 노드에 대해 최단 거리 테이블을 갱신하는 방식으로 동작한다. 하지만 매 단계마다 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다. 또한, 다익스트라 알고리즘은 1차원 리스트에 최단 거리 테이블을 저장했다면 플로이드 워셜 알고리즘은 2차원 리스트에 최단 거리 정보를 저장한다.

동작 방법

노드의 개수가 N개라고 하면, N번만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문에 다이나믹 프로그램이라고 할 수 있다.  $0<=i<=N$이고 a번 노드에서 b번 노드까지의 최단 거리를 구한다고 가정하자.

예시

아래 그래프에 대한 플로이드 워셜 알고리즘 동작을 알아보자. 우선 2차원 최단 거리 테이블을 설정한다.

처음 최단 거리 테이블

1번 노드를 거쳐간 후 최단 거리 테이블

첫 번째로 1번 노드를 거쳐갈 때의 경우를 살펴보자. 이미 최단 거리 테이블에 존재하는 값과 1번 노드를 거쳐갔을 때의 거리를 비교해서 더 작은 값으로 최단 거리 테이블을 갱신해준다.

$D_{23} = min(D_{23}, D_{21}+D_{13})$

$D_{24} = min(D_{24}, D_{21}+D_{14})$ 

$D_{32} = min(D_{32}, D_{31}+D_{12})$

$D_{34} = min(D_{34}, D_{31}+D_{14})$

$D_{42} = min(D_{42}, D_{41}+D_{12})$

$D_{43} = min(D_{43}, D_{41}+D_{13})$

$D_{24}$의 경우 무한의 값을 가졌는데, $D_{21}+D_{14}=8$이므로 8로 갱신했다.

 

2번 노드를 거쳐간 후 최단 거리 테이블

이번에는 2번 노드를 거쳐갔을 때의 거리와 최단 거리 테이블에 존재하는 값과 비교하여 더 작은 값으로 최단 거리 테이블을 갱신한다. 2번 노드를 거쳐 가는 경우의 수는 2번 노드를 제외한 노드 중에서 2개를 뽑는 경우의 수이므로 6가지이다.

$D_{31}$의 경우 최단 거리 테이블에는 무한대가 저장되어 있다. $D_{32}+D_{21} = 12$이므로 최단 거리 테이블을 갱신한다.

$D_{34}$의 경우 최단 거리 테이블에는 무한대가 저장되어 있다. $D_{32}+D_{24} = 25$이므로 최단 거리 테이블을 갱신한다.

 

3번 노드를 거쳐간 후 최단 거리 테이블

위와 마찬가지로 3번 노드를 거쳐갔을 때의 거리와 최단 거리 테이블에 존재하는 값과 비교하여 더 작은 값으로 최단 거리 테이블을 갱신한다. 3번 노드를 제외한 노드 중에서 2개를 뽑는 경우의 수는 6가지이다.

$D_{12}$의 경우 최단 거리 테이블에는 무한대가 저장되어 있었다. $D_{13}+D_{32}=11$이므로 최단 거리 테이블을 갱신한다.

 

4번 노드를 거쳐간 후 최단 거리 테이블

위와 마찬가지로 4번 노드를 거쳐갔을 때의 거리와 최단 거리 테이블에 존재하는 값과 비교하여 더 작은 값으로 최단 거리 테이블을 갱신한다. 4번 노드를 제외한 노드 중에서 2개를 뽑는 경우의 수는 6가지이다.

$D_{12}$의 경우 최단 거리 테이블에는 11이 저장되어 있었다. $D_{14}+D_{42}=9$이므로 최단 거리 테이블을 갱신한다.

코드

# 플로이드 워셜 알고리즘
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

k는 중간에 경우하는 노드를, a와 b는 각각 출발 노드, 도착 노드를 나타낸다.

시간 복잡도

플로이드 워셜 알고리즘은 매 단계마다 '거쳐 가는 노드'를 기준으로 최단 거리 테이블을 갱신한다. 노드의 개수가 N개일 때 N번의 단계를 수행하며($O(N)$), 2차원 리스트 최단 거리 테이블을 탐색($O(N^2)$)하므로 플로이드 워셜 알고리즘의 시간 복잡도는 $O(N^3)$이다.

정리

1. 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있다.

2. 2차원 리스트 형태의 최단 거리 테이블을 사용한다.

3. 플로이드 워셜 알고리즘은 $O(N^3)$의 시간 복잡도를 가진다.

4. 다이나믹 프로그래밍으로 풀 수 있다.