최단 경로 문제 (2) - 플로이드 워셜 알고리즘

플로이드 워셜 (Floyd Warshall) 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 알고리즘으로 다익스트라 알고리즘처럼 단계 별로 거쳐가는 노드를 기준으로 수행합니다.

하지만, 다익스트라 알고리즘처럼 방문하지 않은 노드 중 최단 거리를 찾는 과정을 거치지 않고 다이나믹 프로그래밍 방법처럼 2차원 테이블에 대해 각 노드별 최단 거리를 업데이트하는 방법으로 수행하여 음수 간선을 가지는 그래프에 대해서도 동작합니다.

다이나믹 프로그래밍의 상향식 테뷸리이션 방법으로 2차원 최단 거리 테이블을 업데이트하는 방식으로 이루어지는데요. a노드와 b노드의 최단거리 테이블을 업데이트하기 위한 점화식은 다음과 같습니다.

$D_{ab} = min(D_{ab}, D_{ak}+D_{bk})$

각 단계마다 k노드를 거쳐 a노드에서 b노드로 가는 거리를 계산하고 그 중 최소값을 테이블에 업데이트합니다. 예를 들어 살펴보겠습니다.

EXAMPLE

플로이드 워셜 알고리즘에서는 모든 노드에서 다른 모든 노드까지의 최단 경로를 계산하므로 출발 노드가 따로 존재하지 않습니다. 

2차원 최단 경로 테이블은 다음과 같이 초기화할 수 있습니다. 자기 자신은 0이고 인접한 노드를 그대로 업데이트합니다. 그 외의 칸은 무한으로 설정합니다.

출발 / 도착	1	2	3	4
1	0	4	무한	6
2	3	0	7	무한
3	5	무한	0	4
4	무한	무한	2	0

 

1. Step 1

1번 노드를 거쳐 가는 경우를 고려하고 위의 점화식에 맞추어 2차원 테이블을 갱신합니다. 예를 들어 $D_{23}$은 $min(D_{23}, D_{21}+D{13}$으로 업데이트 되겠죠.

출발 / 도착	1	2	3	4
1	0	4	무한	6
2	3	0	7	3+6=9
3	5	5+4	0	4
4	무한	무한	2	0

 

2. Step 2

2번 노드를 거쳐 가는 경우를 고려하고 위의 점화식에 맞추어 2차원 테이블을 갱신합니다. 예를 들어 $D_{13}$은 $min(D_{13}, D_{12}+D{23}$으로 업데이트 되겠죠.

출발 / 도착	1	2	3	4
1	0	4	4+7=11	6
2	3	0	7	3+6=9
3	5	5+4	0	4
4	무한	무한	2	0

 

3. Step 3

위의 과정을 3번 노드, 4번 노드에 대해서 반복해서 전체 테이블을 완성합니다.

 

파이썬 코드

코드는 직관적으로 단순합니다. 점화식에 따라 3중 반복문을 수행하면 됩니다. 코드는 다음과 같습니다.

def floyd_warshall(n, 간선 정보): # n은 노드 개수    

    ## 2차원 최단 거리 테이블을 배열로 초기화 
    graph = [[float('inf')] * n for _ in range(노드 개수)]
    
    ## 자기 자신은 0으로 초기화
    for i in range(len(graph)):
        graph[i][i] = 0
        
    ## 간선 정보로 테이블 업데이트    
    
    ## 점화식에 따라 알고리즘 수행
    for k in range(n): # k 노드를 거치는 경우
        for a in range(n):
            for b in range(n): # ab의 거리와 ak+kb의 거리의 최소값으로 테이블 업데이트
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])              
                
    

시간 복잡도

노드의 개수가 $N$개일 때, $N$번의 라운드를 수행하게 되는데요. 각 라운드 별로 $O(N^2)$의 시간 복잡도가 소요되므로 총 시간 복잡도는 $O(N^3)$의 매우 큰 시간 복잡도가 소요됩니다. 따라서 노드의 개수가 적은 경우에 적합하겠죠.

 

홍머스 정리

• 점화식으로 2차원 최단거리 테이블 완성
• $O(N^3)$

참조

• www.youtube.com/watch?v=hw-SvAR3Zqg&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=31