Hey Tech
플로이드 워셜(Floyd-Warshall) 알고리즘 이해(+Python 구현) 본문
본 포스팅에서는 최단경로(길 찾기)알고리즘 중에서도 플로이드-워셜 알고리즘에 대해 알아봅니다.
📚 목차
1. 최단경로(길 찾기) 알고리즘이란?
2. 플로이드-워셜 알고리즘 개념
3. 플로이드-워셜 알고리즘 특징
4. 플로이드 워셜 알고리즘의 동작 과정
5. 플로이드 워셜 알고리즘 구현(Python)
1. 최단경로(길찾기) 알고리즘이란?
최단경로 알고리즘은 길찾기 알고리즘이라고도 불리며, 말 그대로 특정 지점까지 가장 빠르게 도달할 수 있는 경로를 찾는 알고리즘입니다. 이번 포스팅에서는 알고리즘 테스트에서 빈출 최단경로 알고리즘 유형 2가지 중 2번째, 플로이드-워셜 알고리즘에 대해 알아봅니다.
- 다익스트라 최단경로 알고리즘(Dijkstra Algorithm)
- 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
2. 플로이드-워셜 알고리즘 개념
플로이드 워셜 알고리즘은 모든 노드 간의 최단 경로를 계산할 때 사용하는 알고리즘입니다. 플로이드 워셜 알고리즘에서는 노드의 개수가 \(N\) 개일 때, 알고리즘의 각 동작 단계별로 노드 1개씩을 선택하기 때문에 동작 단계는 총 \(N\) 개입니다. 즉, 이 단계에서 \(O(N)\) 만큼의 연산이 필요합니다. 이제 각 단계별로 현재 선택된 노드를 거쳐서 다른 모든 노드로 가는 최단 경로를 계산합니다. 다시 말해, 현재 노드를 제외하고 \((N-1)\) 개의 노드 중에서 서로 다른 2개의 노드로 구성된 한 쌍을 선택하고 최단 경로를 계산하는 것입니다. 이는 \(_{N-1}P_{2}\) 개의 쌍을 각 단계별로 반복하여 확인하는 것과 같습니다. 이렇게 계산된 최단 경로는 '최단 거리 테이블'이라고 부르는 2차원 리스트에 저장합니다. 따라서 전체 시간 복잡도는 \(O(N^{3})\) 입니다.
3. 플로이드-워셜 알고리즘 특징
플로이드 워셜 알고리즘은 모든 노드별로 특정 노드를 거쳐 다른 모든 노드로 가는 최단 경로를 저장하기 위해 2차원 리스트(i.e., 최단 거리 테이블)를 활용합니다. 따라서 노드의 개수가 총 \(N\) 개일 때, 알고리즘의 전체 시간 복잡도는 \(O(N^3)\) 입니다. 알고리즘 대회(테스트) 문제 등에서 최단 경로를 구할 때 노드의 개수가 적다면 플로이드 워셜 알고리즘을 활용하는 것이 효과적입니다. 반면, 노드와 간선의 개수가 모두 많을 때는 다익스트라 최단 경로 알고리즘을 활용하는 것이 효과적입니다. 노드의 개수만큼 점화식에 따라 최단 거리 테이블을 갱신한다는 점에서 다이나믹 프로그래밍 유형 중 하나로 볼 수 있습니다. 플로이드 워셜 알고리즘의 점화식은 아래와 같습니다.
$$ D_{ab} = min(D_{ab}, D_{ak}+D_{bk}) $$
여기서 \(D_{ab}\) 는 노드 A에서 노드 B로 가는 최단 거리를 의미합니다. 위의 점화식은 노드 A에서 노드 B로 가는 거리를 A에서 B로 가는 최단 거리와 A에서 K를 거쳐 B로 가는 거리와 비교하여 더 작은 값으로 갱신하라는 의미입니다. 즉, 목적지 노드로 직행하는 거리보다 어느 한 노드를 경유해서 목적지 노드로 가는 거리가 짧다면, 경유해서 가는 거리로 출발-도착 노드 간의 거리를 갱신하는 것이죠.
4. 플로이드 워셜 알고리즘의 동작 과정
이제 플로이드 워셜 알고리즘의 구체적인 동작 과정을 살펴보겠습니다. 동작 순서는 아래와 같습니다.
1️⃣ 최단 거리 테이블 내 특정 노드에서 자기 자신 노드로 가는 비용은 항상 0이므로 대각 행렬의 값은 모두 0으로 초기화합니다.
2️⃣ 특정 노드에서 다른 모든 노드로 가는 비용(간선)에 따라 최단 거리 테이블을 갱신합니다. 노드 간에 간선으로 연결되어 있지 않은 경우에는 '무한'으로 테이블을 초기화합니다.
3️⃣ 이제 1번 노드부터 차례대로 해당 노드를 중간에 거쳐서 가는 모든 노드 간의 최단 경로를 계산하고 최단 거리 테이블을 갱신합니다.
이제 본격적으로 아래 그림 1 과 같이 예시 그래프를 통해 플로이드 워셜 알고리즘의 동작 과정을 알아보겠습니다.
(1) 먼저 최단 거리 테이블 내 대각 행렬은 모두 0으로 초기화하고(과정 1️⃣), 노드 간의 간선 연결 상태에 따라 최단 거리 테이블을 초기화합니다(과정 2️⃣). 이때 노드 간에 간선이 연결되어 있지 않은 경우에는 '무한'으로 초기화합니다(표 1 참고).
| 출발\도착 | 노드 1 | 노드 2 | 노드 3 | 노드 4 |
| 노드 1 | 0 | 2 | 6 | 무한 |
| 노드 2 | 1 | 0 | 무한 | 3 |
| 노드 3 | 무한 | 4 | 0 | 4 |
| 노드 4 | 7 | 무한 | 5 | 0 |
표 1. 초기 최단 거리 테이블
(2) 가장 먼저, 1번 노드를 거쳐서 다른 모든 노드로 가는 최단 거리를 계산해 보겠습니다. 아래와 같이 정확히 \(_{3}P_{2}=6\) 개의 연산을 수행하면 됩니다.
\(D_{23} = min(D_{23}, D_{21}+D_{13})\)
\(D_{24} = min(D_{24}, D_{21}+D_{14})\)
\(D_{32} = min(D_{32}, D_{21}+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})\)
위 6가지 연산을 하나씩 수행하며 최단 거리 테이블 내 값과 비교하여 테이블을 갱신하면 됩니다. 예를 들어, \(D_{23} = min(D_{23}, D_{21}+D_{13})\) 을 계산해 보면 다음과 같습니다. 현재 \(D_{23}\) 은 '무한'이고 \(D_{21}+D_{13}\) 은 \(1+6 = 7\) 이므로 \(D_{23}\)은 7로 갱신됩니다. 마찬가지 방식으로 나머지 5개의 연산도 수행하면 결과는 표 2 와 같습니다. 편의상 표에서 갱신된 노드 간 거리는 파란색으로, 갱신되지 않은 노드 간 거리는 빨간색으로 표현하겠습니다.
| 연산 | \(D_{ab}\) | \(D_{ak}+D_{kb}\) | \(min(D_{ab}, D_{ak}+D_{kb})\) |
| \(D_{23} = min(D_{23}, D_{21}+D_{13})\) | 무한 | 1 + 6 = 7 | 7 |
| \(D_{24} = min(D_{24}, D_{21}+D_{14})\) | 3 | 1 + 무한 = 무한 | 3 (갱신 X) |
| \(D_{32} = min(D_{32}, D_{31}+D_{12})\) | 4 | 무한 + 2 = 무한 | 4 (갱신 X) |
| \(D_{34} = min(D_{34}, D_{31}+D_{14})\) | 4 | 무한 + 무한 = 무한 | 4 (갱신 X) |
| \(D_{42} = min(D_{42}, D_{41}+D_{12})\) | 무한 | 7 + 2 = 9 | 9 |
| \(D_{43} = min(D_{43}, D_{41}+D_{13})\) | 5 | 7 + 6 = 13 | 5 (갱신 X) |
표 2. 최단 거리 갱신 전/후 비교 테이블(노드 1 경유)
연산 결과를 바탕으로 최종적으로 최단 거리 테이블은 표 3 과 같이 갱신됩니다.
| 출발\도착 | 노드 1 | 노드 2 | 노드 3 | 노드 4 |
| 노드 1 | 0 | 2 | 6 | 무한 |
| 노드 2 | 1 | 0 | 7 (갱신 O) | 3 (갱신 X) |
| 노드 3 | 무한 | 4 (갱신 X) | 0 | 4 (갱신 X) |
| 노드 4 | 7 | 9 (갱신 O) | 5 (갱신 X) | 0 |
표 3. 갱신된 최단 거리 테이블(노드 1 경유)
(3) 다음으로 2번 노드를 거쳐서 다른 모든 노드로 가는 최단 경로를 계산하고 최단 거리 테이블을 갱신합니다(표 4 참고).
| 연산 | \(D_{ab}\) | \(D_{ak}+D_{kb}\) | \(min(D_{ab}, D_{ak}+D_{kb})\) |
| \(D_{13} = min(D_{13}, D_{12}+D_{23})\) | 6 | 2 + 7 = 9 | 6 |
| \(D_{14} = min(D_{14}, D_{12}+D_{24})\) | 무한 | 2 + 3 = 5 | 5 |
| \(D_{31} = min(D_{31}, D_{32}+D_{21})\) | 무한 | 4 + 1 = 5 | 5 |
| \(D_{34} = min(D_{34}, D_{32}+D_{24})\) | 4 | 4 + 3 = 7 | 4 |
| \(D_{41} = min(D_{41}, D_{42}+D_{21})\) | 7 | 9 + 1 = 10 | 7 |
| \(D_{43} = min(D_{43}, D_{42}+D_{23})\) | 5 | 9 + 7 = 16 | 5 |
표 4. 최단 거리 갱신 전/후 비교 테이블(노드 2 경유)
연산 결과를 바탕으로 최종적으로 최단 거리 테이블은 표 5와 같이 갱신됩니다.
| 출발\도착 | 노드 1 | 노드 2 | 노드 3 | 노드 4 |
| 노드 1 | 0 | 2 | 6 | 5 |
| 노드 2 | 1 | 0 | 7 | 3 |
| 노드 3 | 5 | 4 | 0 | 4 |
| 노드 4 | 7 | 9 | 5 | 0 |
표 5. 갱신된 최단 거리 테이블(노드 2 경유)
(4) 이제 3번 노드를 거쳐서 다른 모든 노드로 가는 최단 경로를 계산해 보면 갱신할 값이 없음을 알 수 있습니다(표 6 참고).
| 연산 | \(D_{ab}\) | \(D_{ak}+D_{kb}\) | \(min(D_{ab}, D_{ak}+D_{kb})\) |
| \(D_{12} = min(D_{12}, D_{13}+D_{32})\) | 2 | 6 + 4 = 10 | 2 |
| \(D_{14} = min(D_{14}, D_{13}+D_{34})\) | 5 | 6 + 4 = 10 | 5 |
| \(D_{21} = min(D_{21}, D_{23}+D_{31})\) | 1 | 7 + 5 = 12 | 1 |
| \(D_{24} = min(D_{24}, D_{23}+D_{34})\) | 3 | 7 + 4 = 11 | 3 |
| \(D_{41} = min(D_{41}, D_{43}+D_{31})\) | 7 | 5 + 5 = 10 | 7 |
| \(D_{42} = min(D_{42}, D_{43}+D_{32})\) | 9 | 5 + 4 = 9 | 9 |
표 6. 최단 거리 갱신 전/후 비교 테이블(노드 3 경유)
최단 거리 테이블은 표 7 과 같이 변화된 값이 없습니다.
| 출발\도착 | 노드 1 | 노드 2 | 노드 3 | 노드 4 |
| 노드 1 | 0 | 2 | 6 | 5 |
| 노드 2 | 1 | 0 | 7 | 3 |
| 노드 3 | 5 | 4 | 0 | 4 |
| 노드 4 | 7 | 9 | 5 | 0 |
표 7. 최단 거리 테이블(노드 3 경유)
(5) 마지막으로 4번 노드를 거쳐서 다른 모든 노드로 가는 최단 경로를 계산해 보면 갱신할 값이 없음을 알 수 있습니다(표 8 참고).
| 연산 | \(D_{ab}\) | \(D_{ak}+D_{kb}\) | \(min(D_{ab}, D_{ak}+D_{kb})\) |
| \(D_{12} = min(D_{12}, D_{14}+D_{42})\) | 2 | 5 + 9 = 14 | 2 |
| \(D_{13} = min(D_{13}, D_{14}+D_{43})\) | 6 | 5 + 5 = 10 | 6 |
| \(D_{21} = min(D_{21}, D_{24}+D_{41})\) | 1 | 3 + 7 = 10 | 1 |
| \(D_{23} = min(D_{23}, D_{24}+D_{43})\) | 7 | 3 + 5 = 8 | 7 |
| \(D_{31} = min(D_{31}, D_{34}+D_{41})\) | 5 | 4 + 7 = 11 | 5 |
| \(D_{32} = min(D_{32}, D_{34}+D_{42})\) | 4 | 4 + 9 = 13 | 4 |
표 8. 최단 거리 갱신 전/후 비교 테이블(노드 4 경유)
최종적으로 4개의 노드 중 1개씩 노드를 경유해 계산한 모든 노드 간의 최단 거리 테이블은 표 9 와 같습니다.
| 출발\도착 | 노드 1 | 노드 2 | 노드 3 | 노드 4 |
| 노드 1 | 0 | 2 | 6 | 5 |
| 노드 2 | 1 | 0 | 7 | 3 |
| 노드 3 | 5 | 4 | 0 | 4 |
| 노드 4 | 7 | 9 | 5 | 0 |
표 9. 최종 최단 거리 테이블
표 9 를 통해 다음과 같은 정보를 얻을 수 있습니다. 예를 들어, \(D_{13}\) 은 1행 3열의 값으로서 6입니다. 이는 노드 1에서 노드 3으로 가는 최단 거리가 6이라는 것을 의미합니다.
5. 플로이드 워셜 알고리즘 구현(Python)
이제 파이썬을 기반으로 플로이드 워셜 알고리즘을 구현해 보겠습니다.
소스코드
# '무한'을 의미하는 값을 10억으로 초기화
INF = int(1e9)
# 노드와 간선의 개수를 입력 받기
num_node = int(input("노드의 개수를 입력하세요: "))
num_edge = int(input("간선의 개수를 입력하세요: "))
# 최단 거리 테이블 역할의 2차원 리스트를 생성하고 모든 값을 '무한'으로 초기화
# 2차원 리스트의 인덱스와 노드 번호를 일치시키기 위해 행, 열의 개수를 1개씩 추가
min_dist_table = [[INF]*(num_node+1) for _ in range(num_node+1)]
# 자기 자신으로 가는 거리는 0이므로 대각행렬 0으로 초기화
for a in range(1, num_node + 1):
for b in range(1, num_node + 1):
if a == b:
min_dist_table[a][b] = 0
# 간선의 정보를 입력받아 최단 거리 테이블 초기화
for _ in range(num_edge):
a, b, cost = map(int, input("간선 정보 입력! 출발 노드, 도착 노드, 비용 순서대로 입력하세요: ").split())
min_dist_table[a][b] = cost
# 점화식을 기반으로 플로이드 워셜 알고리즘 수행
for k in range(1, num_node + 1):
for a in range(1, num_node + 1):
for b in range(1, num_node + 1):
min_dist_table[a][b] = min( min_dist_table[a][b], min_dist_table[a][k] + min_dist_table[k][b])
# 결과 출력
for a in range(1, num_node + 1):
for b in range(1, num_node +1):
# 노드를 방문할 수 없는 경우, '무한' 값 출력
if min_dist_table[a][b] == INF:
print("INF")
else:
# 노드를 방문할 수 있을 경우 최단 거리 출력
print(min_dist_table[a][b], end = ' ')
# 개행
print()입력값
노드의 개수를 입력하세요: 4
간선의 개수를 입력하세요: 8
간선 정보 입력! 출발 노드, 도착 노드, 비용 순서대로 입력하세요: 1 2 2
간선 정보 입력! 출발 노드, 도착 노드, 비용 순서대로 입력하세요: 1 3 6
간선 정보 입력! 출발 노드, 도착 노드, 비용 순서대로 입력하세요: 2 1 1
간선 정보 입력! 출발 노드, 도착 노드, 비용 순서대로 입력하세요: 2 4 3
간선 정보 입력! 출발 노드, 도착 노드, 비용 순서대로 입력하세요: 3 2 4
간선 정보 입력! 출발 노드, 도착 노드, 비용 순서대로 입력하세요: 3 4 4
간선 정보 입력! 출발 노드, 도착 노드, 비용 순서대로 입력하세요: 4 1 7
간선 정보 입력! 출발 노드, 도착 노드, 비용 순서대로 입력하세요: 4 3 5출력값
0 2 6 5
1 0 7 3
5 4 0 4
7 9 5 0마치며
오늘은 길 찾기 알고리즘이라고도 불리는 최단 경로 알고리즘 중에서도 알고리즘 대회(테스트) 문제로 자주 등장하는 플로이드 워셜 알고리즘에 대해 알아보았습니다. 플로이드 워셜 알고리즘은 다익스트라 최단 경로 알고리즘과 다르게, 모든 노드에서 다른 모든 노드로 가는 최단 거리를 계산한다는 점에서 차이가 있습니다. 또한, 다익스트라 최단 경로 알고리즘은 1차원 리스트 기반의 최단 거리 테이블을 사용하지만, 플로이드 워셜 알고리즘은 2차원 리스트를 활용한다는 차이가 있습니다. 플로이드 워셜 알고리즘은 \(O(N^{3})\) 만큼의 시간 복잡도가 필요하다는 특징도 있었습니다. 다음 포스팅에서는 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘의 차이점에 대해 비교해 보도록 하겠습니다.
📚 참고할 만한 포스팅
1. [자료구조] 그래프 자료구조에 대해 알아보자!(노드, 간선)
2. [알고리즘] 다이나믹(동적) 프로그래밍에 대해 알아보자! (+Python 구현)
3. 최단경로(길찾기) 알고리즘#1: 다익스트라 최단 경로 알고리즘에 대해 알아보자! (+Python 구현)
4. 최단경로(길찾기) 알고리즘#2: 플로이드 워셜(Floyd-Warshall) 알고리즘에 대해 알아보자!(+Python 구현)
포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐거운 하루 보내시길 바랍니다 :D
고맙습니다.
'알고리즘 > 이론' 카테고리의 다른 글
| [알고리즘] 파라메트릭 서치(Parametric Search)에 대해 알아보자! (3) | 2021.04.26 |
|---|---|
| [자료구조] 그래프 자료구조와 트리 자료구조의 차이에 대해 알아보자! (0) | 2021.04.15 |
| 다익스트라 최단 경로 알고리즘 이해 (+Python 구현) (3) | 2021.04.12 |
| [자료구조] 힙(Heap) 자료구조에 대해 알아보자!(+Python 구현) (2) | 2021.04.11 |
| [자료구조] 우선순위 큐(Priority Queue)에 대해 알아보자!(+Python 구현) (0) | 2021.04.02 |
