Floyd Warshall Algorithm (플로이드-워셜)
모든 정점 사이의 최단 거리를 찾는 탐색 알고리즘
아이디어
두 정점 사이의 최단 경로는 다른 한 정점을 거치거나, 거치지 않는 경로 중 하나이다.
만약 경유지를 거친다면 최단 경로를 이루는 부분 경로 역시 최단 경로이다. 바꿔 말해 A - B의 최단 경로가 A-K-B라면 A-K와 K-B도 각각 최단 경로이다. (Optimal Substructure)
알고리즘 설계 및 구현
한 정점에서 다른 정점으로 바로 갈 수 있으면 최소거리를, 갈 수 없으면 INF값을 담고 있는 2차원 행렬 D을 초기화한다.
각 정점이 경유지 K를 지날 때마다 최단 거리를 계산하여 행렬 D를 갱신한다.
Dynamic Programming으로 해결하며, 점화식은
D[i][j] = min(D[i][j], D[i][k] + D[k][j])이다.
시간 복잡도
모든 가능한 경유지에 대해서 모든 정점 모든 정점으로 가는 최단 거리를 확인하므로, 시간복잡도는 O(n^3) 이다.
예시
코드 - Python
import copy
# Floyd-Warshall Algorithm: 모든 정점에서 모든 정점까지의 최단 경로 알고리즘
def floyd_warshall(g: list[list[int]], n: int) -> list[list[int]:
dist = copy.deepcopy(g) # dist: 최단 경로의 길이를 담은 행렬
for k in range(0, n): # 거치는 점
for i in range(0, n): # 시작점
for j in range(0, n): # 끝점
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# print 2-D Matrix
def printMatrix(d: list[list[int]]) -> None:
n = len(d[0])
for i in range(0, n):
for j in range(0, n):
print(d[i][j], end=' ')
print()
# Testcase
INF = 1000
g = [ [0, 1, INF, 1, 5],
[9, 0, 3, 2, INF],
[INF, INF, 0, 4, INF],
[INF, INF, 2, 0, 3],
[3, INF, INF, INF, 0] ]
dist = floyd_warshall(g, 5)
printMatrix(dist)
Floyd's Algorithm을 통한 최단 경로 출력
Optimal Substructure을 활용하면 경유하는 정점들을 알 수 있다.
P[i][j] = 중간에 정점이 없으면 0, 있으면 그 중 가장 큰 인덱스
예시
path(5, 3) = 4
path(5, 4) = 1
path(5, 1) = 0
v1
path(1, 4) = 0
v4
path(4, 3) = 0
즉, v5에서 v3까지 최단 경로는 v5 -> v1 -> v4 -> v3 이다.
코드
# Floyd-Warshall 알고리즘을 통한 최단 경로를 구성하는 정점 기록
def floyd_warshall_2(g: list[list[int]], n: int):
dist = copy.deepcopy(g)
p = [[0] * n for _ in range(n)] # p: 중간에 정점이 없으면 0, 있으면 그 중 가장 큰 인덱스를 포함한 행렬
for k in range(0, n):
for i in range(0, n):
for j in range(0, n):
if dist[i][k] + dist[k][j] < dist[i][j]:
p[i][j] = k + 1 # 경로 중 가장 큰 인덱스 저장
dist[i][j] = dist[i][k] + dist[k][j]
return dist, p
# print 2-D Matrix
def printMatrix(d: list[list[int]]) -> None:
n = len(d[0])
for i in range(0, n):
for j in range(0, n):
print(d[i][j], end=' ')
print()
# 특정 두 정점 사이의 최단 경로 출력
def printPath(p: list[list[int]], q: int, r: int) -> None:
if p[q-1][r-1] != 0: # 최단 경로가 경유지를 지날 경우
printPath(p, q, p[q-1][r-1]) # 시작 정점에서 겅유하는 정점까지의 경로 검사
print(f'v{p[q-1][r-1]}', end=' ')
printPath(p, p[q-1][r-1], r) # 겅유하는 정점에서 끝 정점까지의 경로 검사
# Testcase
INF = 1000
g = [ [0, 1, INF, 1, 5],
[9, 0, 3, 2, INF],
[INF, INF, 0, 4, INF],
[INF, INF, 2, 0, 3],
[3, INF, INF, INF, 0] ]
d, p = floyd_warshall_2(g, 5)
print()
printMatrix(d)
print()
printMatrix(p)
print()
printPath(p, 5, 3)