플로이드-워셜 알고리즘

컴퓨터 과학에서 플로이드-워셜 알고리즘()은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 알고리즘을 한 번 수행하면 "모든" 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다.
이 알고리즘의 일부 버전은 관계 formula_1의 추이적 폐포를 찾거나, 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 (슐츠 선거 제도와 결합해서) 찾는 것이 가능하다.
역사와 이름.
플로이드-워셜 알고리즘은 동적 계획법의 한 예로, 로버트 플로이드가 1962년에 현재 알려진 형태로 발표했다. 하지만, 이 알고리즘은 본질적으로 버나드 로이가 1959년에 발표한 알고리즘과, 스티븐 워셜이 1962년에 발표한 알고리즘과 그래프의 추이적 폐포를 찾는다는 점, 그리고 결정적 유한 오토마타를 정규 표현식으로 변환할 때, 클레이니 알고리즘(1956년에 발표됨)과 밀접한 관련이 있다는 점에서 동일하다. 이 알고리즘의 삼중 for 반복문의 공식은 1962년에 Peter Ingerman이 설명하였다.
이 알고리즘은 플로이드 알고리즘, 로이-워셜 알고리즘, 로이-플로이드 알고리즘, 또는 WFI 알고리즘으로 알려져 있다.
알고리즘.
플로이드-워셜 알고리즘은 각각의 꼭짓점 쌍을 지나는 그래프의 모든 경로를 비교한다. 이 방법은 그래프에서 formula_2의 비교로 진행할 수 있다. 그 이유는 그래프에서는 최대 formula_3의 변이 있을 수 있고, 모든 변의 조합을 확인하기 때문이다. 이 알고리즘은 두 꼭짓점 간의 추정 최단 경로를 최적이 될 때까지 점진적으로 개선시켜서 최단경로를 찾는다.
1에서 formula_4까지 번호가 매겨진 formula_5를 꼭짓점으로 갖는 그래프 formula_6를 생각한다. 그 후 formula_7에서 formula_8로 집합 formula_9의 꼭짓점들 만을 경유지로 거쳐 가는 최단 경로를 반환하는 함수 formula_10를 생각한다. 함수가 주어졌을 때, 목표는 formula_11에 있는 꼭짓점만을 이용해서 모든 꼭지점 formula_7에서 모든 꼭짓점 formula_8로 가는 최단 경로를 찾는 것이다.
각각의 꼭짓점 쌍에 대해서, formula_10는 다음 중 한 가지에 속한다:
formula_7에서 formula_8까지 formula_25에서 formula_26의 꼭짓점 만을 거쳐가는 경로 중 최선의 경로는 formula_27에 의해 정의된다는 것은 알고 있으며, 만약 formula_7에서 formula_15를 거쳐 formula_8로 가는 더 나은 경로가 있다면, 그 경로는 formula_7에서 formula_15까지 (formula_16만을 거쳐서) 가는 경로와 formula_15에서 formula_8까지 (formula_16만을 거쳐서) 가는 경로를 합친 것이라는 것은 자명하다.
formula_37이 꼭짓점 formula_7와 formula_8 간의 변의 가중치라면, formula_10를 다음의 재귀적 공식으로 정의할 수 있다: 기본적인 경우는
이고 재귀적인 경우는 다음과 같다
이 공식은 플로이드-워셜 알고리즘의 핵심이다. 이 알고리즘은 처음에 모든 formula_45쌍에 대해서 formula_46일 때 formula_10를 계산하고, 다음으로 formula_48일 때를 계산하는 식으로 formula_49이 될 때까지 계속하면, 모든 formula_45쌍에 대해서 최단 경로를 찾게 된다. 기본적인 알고리즘의 의사코드는 다음과 같다:
 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
 2 for each edge ("u","v")
 3 dist["u"]["v"] ← w("u","v") "// 변 ("u","v")의 가중치
 4 for each vertex "v"
 5 dist["v"]["v"] ← 0
 6 for "k" from 1 to |V|
 7 for "i" from 1 to |V|
 8 for "j" from 1 to |V|
 9 if dist["i"]["j"] &gt; dist["i"]["k"] + dist["k"]["j"]
 10 dist["i"]["j"] ← dist["i"]["k"] + dist["k"]["j"]
 11 end if
예시.
위의 알고리즘은 좌측 하단의 그래프에서 수행된다:
위에서 첫 번째 외부 반복문의 반복 이전은 으로 표시했으며, 이것을 통해 알게 된 경로는 그래프의 한 변에 대응한다. 일 때, 꼭짓점 1을 통과하는 경로를 찾을 수 있다: 특히, 경로 [2,1,3]을 찾았기 때문에, 변이 더 적지만 더 (가중치의 관점에서)긴 경로인 [2,3]을 대체한다. 일 때, 꼭짓점 {1,2}를 통과하는 경로를 찾았다. 빨간 색과 파란 색의 네모는 경로 [4,2,1,3]이 경로 [4,2]와 이전 반복에서 찾은 [2,1,3]이 2를 교차점으로 결합해서 이루어져 있다는 것을 나타낸다. 경로 [4,2,3]은 2에서 3까지 가는 경로가 [2,1,3]보다 길기 때문에 고려하지 않는다. 일 때, {1,2,3}을 지나는 경로를 찾는다. 마지막으로, 일 때, 모든 최단경로를 찾게 된다.
각각의 의 반복에 대한 거리 행렬, 업데이트된 거리는 굵은 글씨로 표시했다:
음수 사이클에서 행동.
음수 사이클은 변의 가중치의 합이 음수를 갖는 사이클이다. 음수 사이클을 구성하는 어떤 꼭짓점 쌍formula_7, formula_8에 대해서든지 formula_7에서 formula_8로 가는 경로의 길이는 음의 무한으로 내려갈 수 있기 때문에 최단 경로가 존재하지 않는다. 수치적으로 의미있는 결과를 얻기 위해서, 플로이드-워셜 알고리즘은 입력에 음수 사이클이 없다고 가정한다. 반면, 음수 사이클이 존재할 경우에는 플로이드-워셜 알고리즘으로 감지할 수 있다. 그 과정은 다음과 같다:
따라서, 플로이드-워셜 알고리즘을 이용해서 음수 사이클을 감지하기 위해서는, 경로 행렬의 대각 성분을 확인해서 음수가 나타나는지를 확인한다. 음수가 발견되면 적어도 하나 이상의 음수 사이클이 존재한다는 것을 나타낸다. 수치적 문제를 피하기 위해서는 알고리즘의 안쪽 반복문에서 경로 행렬의 대각 성분에서 음수가 나타나는지를 확인해야 한다. 무향 그래프에서 음의 가중치가 있으면 그 인접한 꼭짓점 사이에서 음수 사이클이 생기는 것은 명백하다 (예: 닫힌 보행). 위의 예시의 모든 변을 방향이 없다고 생각하면, 꼭짓점 수열 4 - 2 - 4는 가중치의 합이 -2인 사이클이다.
경로 복원.
플로이드-워셜 알고리즘은 모든 꼭짓점 간의 경로의 길이 만을 제공한다. 간단한 수정으로 두 끝점 사이의 실제 경로를 재현하는 방법을 만들 수 있다. 그중 한 방법으로 각각의 꼭짓점에서 다른 꼭짓점 까지의 실제 경로를 저장할 지도 모르지만, 그럴 필요가 없을 뿐 더러 메모리의 엄청난 낭비가 생긴다. 대신, 각각의 꼭짓점에 대해서 최단 경로 트리를 formula_62시간복잡도에 각 트리를 저장하는데 formula_63공간복잡도를 사용해서 계산 할 수 있으며, 이 트리를 이용해서 두 연결된 꼭짓점간의 경로를 효율적으로 재현할 수 있다.
 let dist be a formula_64 array of minimum distances initialized to formula_65 (infinity)
 let next be a formula_64 array of vertex indices initialized to null
 procedure "FloydWarshallWithPathReconstruction" ()
 for each edge (u,v)
 dist[u][v] ← w(u,v) "// 변 (u,v)의 가중치
 next[u][v] ← v
 for k from 1 to |V| "// 일반적인 플로이드-워셜의 수행
 for i from 1 to |V|
 for j from 1 to |V|
 if dist[i][j] &gt; dist[i][k] + dist[k][j] then
 dist[i][j] ← dist[i][k] + dist[k][j]
 next[i][j] ← next[i][k]
 procedure Path(u, v)
 if next[u][v] = null then
 return []
 path = [u]
 while u ≠ v
 u ← next[u][v]
 path.append(u)
 return path
해석.
formula_67을 꼭짓점의 개수 formula_68로 두자. formula_69개의
formula_10 (모든 formula_7와 formula_8에 대해서)를
formula_27에서 찾기 위해서는 formula_74개의 연산이 필요하다. 처음에는
formula_75에서 시작했고 and compute the sequence of formula_67개의 행렬 formula_77, formula_78, formula_79, formula_80을 계산했기 때문에, 사용된 전체 연산의 수는
formula_81이다. 따라서, 이 알고리즘의 복잡도는 formula_82이다.
적용과 일반화.
플로이드-워셜 알고리즘은 다음의 문제들을 다른 알고리즘과 같이 해결할 수 있다:
수행.
플로이드-워셜 알고리즘은 많은 프로그래밍 언어에서 수행할 수 있다.
다른 최단 경로 알고리즘과 비교.
플로이드-워셜 알고리즘은 거의 대부분이나 모든 꼭짓점 쌍이 변으로 연결된 밀집 그래프에서 모든 꼭짓점 쌍 간의 경로를 계산할 때 적합하다. 음수 가중치가 없는 희소 그래프에서는 모든 꼭짓점에서 출발하는 데이크스트라 알고리즘이 반복 데이크스트라의 수행 시간(피보나치 힙을 사용하면 formula_83)은 formula_84가 formula_85에 비해 무시할 수 있을 정도면 플로이드-워셜 알고리즘의 수행 시간인 formula_86보다 적으므로 더 적합하다. 희소 그래프에서 음수 가중치가 있지만 음수 사이클은 없는 경우에는 존슨 알고리즘은 수행 시간이 반복 데이크스트라 시간과 같으므로 사용할 수 있다.
알려진 알고리즘 중에는 밀집 그래프에서 모든 쌍의 최단 경로 계산을 빠르게 하기 위해 빠른 행렬 곱셈을 사용하는 알고리즘도 있지만, 이러한 알고리즘들은 변의 가중치에 추가적인 제약 조건이 따른다(예를 들면 작은 정수여야 한다라는 식으로). 게다가, 수행 시간에서 큰 상수 인자 때문에, 이런 알고리즘들은 매우 큰 그래프에서만 플로이드-워셜 알고리즘보다 빠른 속도를 낼 수 있다.