들어가며
본 포스팅은 플로이드 워셜 알고리즘에 대해 소개합니다.
📌 플로이드 워셜 알고리즘
플로이드 워셜(Floyd-Warshall) 알고리즘이란, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘입니다.
기존에 소개된 다익스트라 알고리즘에서의 최단 거리 테이블에서 거리가 가장 짧은 노드를 탐색해야 했던 과정을 생략할 수 있다는 점이 차이점입니다.
모든 노드가 다른 노드로 가는 최단 거리의 정보를 2차원 리스트에 담아 저장합니다. 노드의 개수 N만큼 점화식에 맞게 2차원 리스트를 갱신하므로 다이나믹 프로그래밍으로 볼 수 있습니다.
☑️ 시간 복잡도
모든 최단 경로를 2차원 리스트에 담아 처리하므로 매번 $O(N^2)$의 시간이 소요되며, 노드의 개수 N만큼 $O(N^2)$의 연산을 통해, 해당 노드를 거치는 모든 경로를 고려합니다.
현재 노드를 거쳐 지나가는 모든 경우를 찾기 위해, N - 1개의 노드 중 2개의 쌍을 선택하고 거리를 계산합니다. 더 짧은 거리로 계산된다면, 갱신합니다. 즉, $_{N - 1}P_{2}$ 개의 쌍을 반복하여 확인하므로 $O(_{N-1}P_{2}) = O(N^2)$. 즉, 전체 시간 복잡도는 $O(N^3)$입니다.
$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$
이 점화식은 a와 b의 거리와, a에서 k를 거쳐 b로 이동하는 거리를 비교하여 최단 거리를 구하는 것을 의미합니다.
1️⃣ 그래프의 간선을 2차원 리스트로 표현합니다.
2️⃣ 현재 노드를 제외하고 $_{N - 1}P_{2}$ 개의 경우에 대해 점화식을 계산합니다.
3️⃣ 더 작은 거리로 2차원 리스트를 갱신합니다.
4️⃣ 위의 과정을 반복합니다.
1. 그래프의 간선을 2차원 리스트로 표현합니다. 간선이 없는 경우, 무한으로 표기됩니다.
| 출발 / 도착 | 1 | 2 | 3 | 4 |
| 1 | 0 | 4 | 무한 | 6 |
| 2 | 3 | 0 | 7 | 무한 |
| 3 | 5 | 무한 | 0 | 4 |
| 4 | 무한 | 무한 | 2 | 0 |
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_{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})$
| 출발 / 도착 | 1 | 2 | 3 | 4 |
| 1 | 0 | 4 | 무한 | 6 |
| 2 | 3 | 0 | 7 | |
| 3 | 5 | 0 | 4 | |
| 4 | 무한 | 무한 | 2 | 0 |
3. 현재 노드인 2를 거쳐가는 경우를 모두 구하여 최단 거리를 계산합니다.
| 출발 / 도착 | 1 | 2 | 3 | 4 |
| 1 | 0 | 4 | 6 | |
| 2 | 3 | 0 | 7 | 9 |
| 3 | 5 | 9 | 0 | 4 |
| 4 | 무한 | 무한 | 2 | 0 |
4. 현재 노드인 3을 거쳐가는 경우를 모두 구하여 최단 거리를 계산합니다.
| 출발 / 도착 | 1 | 2 | 3 | 4 |
| 1 | 0 | 4 | 11 | 6 |
| 2 | 3 | 0 | 7 | 9 |
| 3 | 5 | 9 | 0 | 4 |
| 4 | 2 | 0 |
5. 현재 노드인 4를 거쳐가는 경우를 모두 구하여 최단 거리를 계산합니다.
| 출발 / 도착 | 1 | 2 | 3 | 4 |
| 1 | 0 | 4 | 6 | |
| 2 | 3 | 0 | 7 | 9 |
| 3 | 5 | 9 | 0 | 4 |
| 4 | 7 | 11 | 2 | 0 |
✅ [ CODE ]
'''
< 플로이드 워셜 알고리즘 >
'''
import sys
input = sys.stdin.readline
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for x in range(1, n + 1):
for y in range(1, n + 1):
if x == y:
graph[x][y] = 0
break
for _ in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c
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])
for a in range(1, n + 1):
for b in range(1, n + 1):
if graph[a][b] == INF:
print("INFINITY")
else:
print(graph[a][b], end = " ")
print()포스팅에 문제 및 오류가 있는 경우, 댓글로 남겨주시면 감사하겠습니다.
출처 ) 이것이 코딩 테스트다 with Python