[Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘 이란?

서론

이번 글에서는 모든 정점 사이의 최단 경로를 구하는 알고리즘인 플로이드-워셜(Floyd-Warshall) 알고리즘의 개념을 살펴보고 예제를 알고리즘의 동작 원리를 알아보고자 한다. 또한, 파이썬을 통해 해당 알고리즘을 구현하는 방법을 살펴볼 것이다.

Floyd-Warshall Algorithm

플로이드 워셜 알고리즘은 그래프(Graph) 상에서 가능한 모든 노드 쌍에 대한 최단 거리를 구하는 알고리즘으로, 최단 경로 알고리즘 (Shortest Path Algorithm) 이라고도 불린다.

 

특정 정점에서 모든 정점까지의 최단 거리를 구하는 다익스트라(dijkstra) 알고리즘과 다른 점은 다음과 같다.

 

• 모든 노드 쌍에 대한 최단 거리를 구할 수 있다.
• 간선의 가중치가 음의 값을 가질 수 있다.

플로이드 워셜 알고리즘의 시간 복잡도는 O(V^3) 을 가진다.

구현 방법

위와 같은 그래프가 있을 때 인접 행렬로 초기 그래프를 나타내면 다음과 같이 나타낼 수 있다.

0	3	8	INF	-4
INF	0	INF	1	7
INF	4	0	INF	INF
2	INF	-5	0	INF
INF	INF	INF	6	0

• 시작, 도착 노드의 노드 번호가 같은 경우 가중치는 0이 된다. (1→1, 2→2, 3→3, 4→4, 5→5)
• INF는 시작 노드에서 도착 노드로 가는 길이 없음을 의미한다. (무한대 값)

플로이드 워셜 알고리즘은 1번 노드부터 시작해서 마지막 노드(n)까지 총 n번 알고리즘을 반복한다.

 

플로이드 워셜 알고리즘 로직은 다음과 같이 구현할 수 있다.

INF = float('inf')
graph = [[0, 3, 8, INF, -4], [INF, 0, INF, 1, 7], [INF, 4, 0, INF, INF],
         [2, INF, -5, 0, INF], [INF, INF, INF, 6, 0]]


# 점화식에 따라 플로이드 와샬 알고리즘 수행
for k in range(0, len(graph)): # 총 5번 알고리즘을 반복 (노드의 개수 = 5)
    for a in range(0, len(graph)):
        for b in range(0, len(graph)):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

 

플로이드 워셜 알고리즘 로직의 의미는 다음과 같다.

• 각 반복마다 시작 노드에서 새로운 중간 노드를 통해서 도착 노드로 갈 수 있는 경로를 선택하여 값을 업데이트 한다.
• 더 짧은 길이로 갈수 있는 경로가 존재한다면 해당 길이로 값을 업데이트 한다.

STEP 1

k=0 일 때 플로이드 워셜 알고리즘을 수행한 결과는 다음과 같다. (1번 노드가 중간 노드가 됨)

빨간 색으로 표시된 값은 경로의 가중치 값이 업데이트 되었음을 의미한다.

0	3	8	INF	-4
INF	0	INF	1	7
INF	4	0	INF	INF
2	5	-5	0	-2
INF	INF	INF	6	0

초기 그래프에서는 4번 노드에서 2번 노드로 갈 수 있는 경로가 없었는데, 1번 노드를 중간 노드로 설정하면 4→1→2 경로를 통해 2번 노드에 도착할 수 있다. 따라서 4번 노드에서 2번 노드로 가는 경로의 가중치 값이 (4→1) = 2 + (1→2) = 3 므로 5의 값으로 업데이트 된다.

 

4번 노드에서 5번 노드로 가는 경우도 1번 노드를 중간 노드로 설정하면 4→1→5 경로를 통해 5번 노드에 도착할 수 있다.

(4→1) 의 가중치는 2, (1→5)의 가중치는 -4 이므로 4번 노드에서 2번 노드로 가는 경로의 가중치 값이 -2로 업데이트 된다.

STEP 2

k=1 일 때 플로이드 워셜 알고리즘을 수행한 결과는 다음과 같다. (2번 노드가 중간 노드가 됨)

0	3	8	4	-4
INF	0	INF	1	7
INF	4	0	5	11
2	5	-5	0	-2
INF	INF	INF	6	0

• (1→4)로 가는 경로는 2번 노드를 중간 노드를 거쳐서 도착할 수 있다. 3+1 = 4
• (3→4)로 가는 경로 또한 2번 노드를 거쳐서 4번 노드에 도착할 수 있다. 4+1 = 5
• (3→5)의 경우에도 2번 노드를 거쳐서 5번 노드에 도착할 수 있다. 4+7 = 11

STEP 3

k=2 일 때 플로이드 워셜 알고리즘을 수행한 결과는 다음과 같다. (3번 노드가 중간 노드가 됨)

0	3	8	4	-4
INF	0	INF	1	7
INF	4	0	5	11
2	-1	-5	0	-2
INF	INF	INF	6	0

4번 노드에서 2번 노드로 가는 경우는 STEP 0에서 1번 노드를 거쳐갈 수 있었으므로 값이 5로 업데이트 되었다.

그러나, 플로이드 워셜 알고리즘은 최단 거리 알고리즘 이므로 다른 경로를 거쳐갈 때의 가중치 값이 더 작으면 해당 값으로 업데이트 한다.

 

4→1→2 의 경우는 가중치가 5였지만,

4→3→2의 경우에는 (4→3) = -5 + (3→2) = 4 이므로 가중치의 값이 -1이다. 따라서 더 작은 가중치 값인 -1로 업데이트 되는 것이다.

 

중간 노드가 4, 5번 노드가 되는 경우도 지금까지 반복한 알고리즘 로직과 동일하므로 설명은 생략한다.

STEP 4

k=3 일 때 플로이드 워셜 알고리즘을 수행한 결과는 다음과 같다. (4번 노드가 중간 노드가 됨)

0	3	-1	4	-4
3	0	-4	1	-1
7	4	0	5	11
2	-1	-5	0	-2
8	5	1	6	0

4번 노드가 중간 노드가 되는 경우는 다음과 같은 결과를 얻을 수 있다.

STEP 5

k=4 일 때 플로이드 워셜 알고리즘을 수행한 결과는 다음과 같다. (5번 노드가 중간 노드가 됨)

0	1	-3	2	-4
3	0	-4	1	-1
7	4	0	5	3
2	-1	-5	0	-2
8	5	1	6	0

모든 단계를 수행한 뒤의 그래프 값은 다음과 같다.

 

플로이드 워셜 알고리즘 관련 문제

• https://www.acmicpc.net/problem/11404

11404번: 플로이드