플로이드-워셜 알고리즘
옛날 도로 지도책 맨 뒤에는 모든 도시 쌍 사이의 거리를 적은 표가 있었습니다. 플로이드-워셜 알고리즘은 이런 표를 계산하는 방법이며, 지금까지 쓰인 알고리즘 중 가장 짧은 것 가운데 하나입니다. 반복문 셋과 비교 하나면 모든 최단 거리가 제자리를 찾습니다.
아이디어
다익스트라 알고리즘과 벨만-포드 알고리즘은 한 시작점에서의 최단 거리를 찾습니다. 플로이드-워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 거리를 한 번에 찾아, 노드마다 행과 열이 하나씩 있는 표에 담습니다. 간선이 직접 알려 주는 것에서 시작해, 경유지로 허용하는 노드를 점점 늘려 가며 표 전체를 개선합니다.
단계별로
표를 채웁니다. 각 노드에서 자기 자신까지는 0, 이웃한 노드 사이는 간선의 길이, 나머지는 무한대입니다. 그런 다음 각 노드 k와 모든 쌍 i, j에 대해, i에서 k까지 거리와 k에서 j까지 거리의 합이 i에서 j까지 거리보다 작으면 더 작은 수를 적습니다. 알고리즘은 이게 전부입니다. 코드로는 반복문 세 개이며, k가 가장 바깥에 있습니다.
예제
노드 네 개와 간선 A–B 길이 3, B–C 1, A–C 5, C–D 2를 생각해 봅시다. 표는 이 간선들과, A–D와 B–D의 무한대로 시작합니다. A 라운드에서는 아무것도 바뀌지 않습니다. A를 거치는 길은 모두 더 길기 때문입니다. B 라운드에서는 B를 거쳐 A에서 C까지: 3 + 1 = 4를 찾는데, 5보다 짧습니다. C 라운드에서는 C를 거쳐 A에서 D까지: 4 + 2 = 6과 B에서 D까지: 1 + 2 = 3을 찾는데, 둘 다 처음 찾은 길입니다. D 라운드에서는 아무것도 바뀌지 않습니다. 최종 표: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.
반복문 순서가 중요한 이유
경유지 k는 가장 바깥 반복문이어야 합니다. k 라운드가 끝나면 모든 칸은 처음 k개 노드만 경유지로 쓴 최단 거리이고, 다음 라운드는 그 위에 쌓입니다. 새 경유지를 거치는 가장 좋은 경로는 그 노드까지의 가장 좋은 경로에 그 노드에서의 가장 좋은 경로를 더한 것이고, 둘 다 이미 맞기 때문입니다. k를 안쪽 반복문에 두면 이 보장이 깨져 틀린 거리가 남을 수 있습니다. 라운드 중에 표를 그 자리에서 고쳐도 안전합니다. 그 라운드에서 k 자신의 행과 열은 바뀌지 않기 때문입니다.
역사와 활용
Bernard Roy가 1959년에 이 방법을 설명했습니다. 1962년에 Stephen Warshall은 한 노드가 다른 노드에 도달할 수 있는지만 묻는 추이적 폐쇄를 위해, Robert Floyd는 최단 경로를 위해 이 방법을 발표했습니다. 거리 표와 라우팅 표를 계산하고, 네트워크의 지름을 구하고, 어떤 노드가 어떤 노드에 도달할 수 있는지 알려 주며, 대각선에 음수가 나오면 음수 사이클을 드러냅니다.
직접 살펴보기
앱을 열고 단계를 누르세요. 한쪽에는 그래프, 다른 쪽에는 표가 있습니다. 라운드마다 현재 경유지의 행과 열이 강조되고, 단계마다 한 쌍의 더 짧은 거리가 적히며 더한 두 칸에 테두리가 그려집니다. 이번 라운드에서 바뀐 칸에는 색이 칠해집니다. 시작과 목표를 고르면 표가 완성되었을 때 둘 사이의 최단 경로를 볼 수 있습니다.
자주 묻는 질문
플로이드-워셜 알고리즘의 시간 복잡도는?
노드가 n개일 때 간선 수와 관계없이 O(n³)이며, 표에는 O(n²) 메모리가 듭니다. 작거나 밀집된 그래프에서는 단순한 반복문이 아주 빠르게 돌아가므로 가장 먼저 고려할 방법입니다.
플로이드-워셜 알고리즘과 모든 노드에서의 다익스트라, 어느 쪽이 좋나요?
밀집 그래프이거나 간선이 음수일 수 있으면 플로이드-워셜 알고리즘이 더 단순하고 속도도 비슷합니다. 간선이 음수가 아닌 큰 희소 그래프에서는 각 노드에서 다익스트라 알고리즘을 실행하는 편이 더 빠릅니다.
플로이드-워셜 알고리즘은 동적 계획법인가요?
네. 처음 k − 1개 노드에 대한 답을 이용해, 경유지가 처음 k개 노드 안에 있는 경로의 문제를 풉니다. 표는 하나만 두고 진행하면서 덮어씁니다.
추이적 폐쇄란?
거리는 무시하고 어떤 노드가 어떤 노드에 도달할 수 있는지를 나타낸 표입니다. 워셜 버전의 알고리즘은 "min"과 "+" 대신 "or"와 "and"로 이를 계산합니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
플로이드-워셜 알고리즘 해 보기