소개
플로이드-워셜 알고리즘은 그래프의 모든 정점 간의 최단 거리를 찾는 알고리즘이다. 주로 그래프를 인접행렬로 표현한 상태에서 많이 쓰이는 방법이다. 양방향 그래프와 방향 그래프 모두 적용할 수 있으며 음수 가중치를 허용한다. 플로이드-워셜 알고리즘은 어떠한 두 정점 간의 최단 경로를 그 경로의 속한 두 최단 경로의 합으로 생각하는 데서 출발한다.
원리
어떠한 두 정점
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
위 그림에서 정점
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
0 | 2 | ∞ | 3 | |
2 | 0 | 3 | 7 | |
∞ | 3 | 0 | ∞ | |
3 | 7 | ∞ | 0 |
연결되어 있지 않은 정점들 간의 거리는 무한으로 초기화한다. 우선 정점
따라서
0 | 2 | ∞ | 3 | |
2 | 0 | 3 | 5 | |
∞ | 3 | 0 | ∞ | |
3 | 5 | ∞ | 0 |
0 | 2 | 5 | 3 | |
2 | 0 | 3 | 5 | |
5 | 3 | 0 | 8 | |
3 | 5 | 8 | 0 |
위의 논리를 계속해서 반복해
구현
플로이드-워셜의 구현은 굉장히 아름답다. 단순한 3중 반복문이면 되기 때문이다.
from copy import deepcopy
# weight는 간선의 가중치를 나타내는 2차원 배열이다. 즉, 인접행렬이다.
# weight[A][B]는 정점 a에서 b로 가는 간선의 가중치이다.
# 정점 a에서 b로 가는 간선이 없다면 weight[A][B]는 INF이다.
# a == b라면 weight[A][B]는 0이다.
def floyd_warshall(weight: list[list[int]]) -> list[list[int]]:
result = deepcopy(weight)
for m in range(len(weight)):
for s in range(len(weight)):
for e in range(len(weight)):
result[s][e] = min(result[s][e], result[s][m] + result[m][e])
return result
플로이드-워셜 알고리즘은 단순 3중 반복문이므로 시간복잡도는