플로이드-워셜 알고리즘

플로이드-워셜 알고리즘

분류	(가중 그래프에서) 전체-쌍 최단 경로 문제
자료 구조	그래프
최악 시간복잡도	$\Theta (|V|^{3})$
최선 시간복잡도	$\Theta (|V|^{3})$
평균 시간복잡도	$\Theta (|V|^{3})$
공간복잡도	$\Theta (|V|^{2})$

컴퓨터 과학에서, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 $R$의 추이적 폐포를 찾거나, (슐츠 선거 제도와 결합해서) 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 찾는 것이 가능하다.

역사와 이름

플로이드-워셜 알고리즘은 동적 계획법의 한 예로, 로버트 플로이드가 1962년에 현재 알려진 형태로 발표했다. 하지만, 이 알고리즘은 본질적으로 버나드 로이가 1959년에 발표한 알고리즘과, 스티븐 워셜이 1962년에 발표한 알고리즘과 그래프의 추이적 폐포를 찾는다는 점,그리고 결정적 유한 오토마타를 정규 표현식으로 변환할 때, 클레이니 알고리즘(1956년에 발표됨)과 밀접한 관련이 있다는 점에서 동일하다. 이 알고리즘의 삼중 for 반복문의 공식은 1962년에 Peter Ingerman이 설명하였다.

이 알고리즘은 플로이드 알고리즘, 로이-워셜 알고리즘, 로이-플로이드 알고리즘, 또는 WFI 알고리즘으로 알려져 있다.

알고리즘

플로이드-워셜 알고리즘은 각각의 꼭짓점 쌍을 지나는 그래프의 모든 경로를 비교한다. 이 방법은 그래프에서 $\Theta (|V|^{3})$의 비교로 진행할 수 있다. 그 이유는 그래프에서는 최대 $\Omega (|V|^{2})$의 변이 있을 수 있고, 모든 변의 조합을 확인하기 때문이다. 이 알고리즘은 두 꼭짓점 간의 추정 최단 경로를 최적이 될 때 까지 점진적으로 개선시켜서 최단경로를 찾는다.

1에서 $N$까지 번호가 매겨진 $V$를 꼭짓점으로 갖는 그래프 $G$를 생각한다. 그 후 $i$에서 $j$로 집합 $\{1,2,\ldots ,k\}$의 꼭짓점들 만을 경유지로 거쳐 가는 최단 경로를 반환하는 함수 $\mathrm {shortestPath} (i,j,k)$를 생각한다. 함수가 주어졌을 때, 목표는 $\{1,2,\ldots ,N\}$에 있는 꼭짓점만을 이용해서 모든 꼭지점 $i$에서 모든 꼭짓점 $j$로 가는 최단 경로를 찾는 것이다.

각각의 꼭짓점 쌍에 대해서, $\mathrm {shortestPath} (i,j,k)$는 다음 중 한 가지에 속한다:

(1) $k$를 통과하지 않는 경로 (집합 $\{1,\ldots ,k-1\}$에 있는 꼭짓점만 거쳐간다.)

(2) $k$를 통과 하는 경로 ($i$에서 $k$까지와 $k$에서 $j$까지 가는 경로 모두 $\{1,\ldots ,k-1\}$에 있는 꼭짓점 만을 거쳐간다)

$i$에서 $j$까지 $1$에서 $k-1$의 꼭짓점 만을 거쳐가는 경로 중 최선의 경로는 $\mathrm {shortestPath} (i,j,k-1)$에 의해 정의된다는 것은 알고 있으며, 만약 $i$에서 $k$를 거쳐 $j$로 가는 더 나은 경로가 있다면, 그 경로는 $i$에서 $k$까지 ($\{1,\ldots ,k-1\}$만을 거쳐서) 가는 경로와 $k$에서 $j$까지 ($\{1,\ldots ,k-1\}$만을 거쳐서) 가는 경로를 합친 것이라는 것은 자명하다.

$w(i,j)$이 꼭짓점 $i$와 $j$ 간의 변의 가중치라면, $\mathrm {shortestPath} (i,j,k)$를 다음의 재귀적 공식으로 정의할 수 있다: 기본적인 경우는

$\mathrm {shortestPath} (i,j,0)=w(i,j)$

이고 재귀적인 경우는 다음과 같다

$\mathrm {shortestPath} (i,j,k)=$

$\mathrm {min} {\Big (}\mathrm {shortestPath} (i,j,k-1),$

$\mathrm {shortestPath} (i,k,k-1)+\mathrm {shortestPath} (k,j,k-1){\Big )}$.

이 공식은 플로이드-워셜 알고리즘의 핵심이다. 이 알고리즘은 처음에 모든 $(i,j)$쌍에 대해서 $k=1$일 때 $\mathrm {shortestPath} (i,j,k)$를 계산하고, 다음으로 $k=2$일 때를 계산하는 식으로 $k=N$이 될 때까지 계속하면, 모든 $(i,j)$쌍에 대해서 최단 경로를 찾게 된다. 기본적인 알고리즘의 의사코드는 다음과 같다:

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] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

예시

위의 알고리즘은 좌측 하단의 그래프에서 수행된다:

위에서 첫 번째 외부 반복문의 반복 이전은 k = 0으로 표시했으며, 이것을 통해 알게 된 경로는 그래프의 한 변에 대응한다. k = 1일 때, 꼭짓점 1을 통과하는 경로를 찾을 수 있다: 특히, 경로 [2,1,3]을 찾았기 때문에, 변이 더 적지만 더 (가중치의 관점에서)긴 경로인 [2,3]을 대체한다. k = 2일 때, 꼭짓점 {1,2}를 통과하는 경로를 찾았다. 빨간 색과 파란 색의 네모는 경로 [4,2,1,3]이 경로 [4,2]와 이전 반복에서 찾은 [2,1,3]이 2를 교차점으로 결합해서 이루어져 있다는 것을 나타낸다. 경로 [4,2,3]은 2에서 3까지 가는 경로가 [2,1,3]보다 길기 때문에 고려하지 않는다. k = 3일 때, {1,2,3}을 지나는 경로를 찾는다. 마지막으로, k = 4일 때, 모든 최단경로를 찾게 된다.

각각의 k의 반복에 대한 거리 행렬, 업데이트 된 거리는 굵은 글씨로 표시했다:

k = 0		j
		1	2	3	4
i	1	0	∞	-2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	-1	∞	0

k = 1		j
		1	2	3	4
i	1	0	∞	-2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	-1	∞	0

k = 2		j
		1	2	3	4
i	1	0	∞	-2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	-1	1	0

k = 3		j
		1	2	3	4
i	1	0	∞	-2	0
	2	4	0	2	4
	3	∞	∞	0	2
	4	3	-1	1	0

k = 4		j
		1	2	3	4
i	1	0	-1	-2	0
	2	4	0	2	4
	3	5	1	0	2
	4	3	-1	1	0

음수 사이클에서 행동

음수 사이클은 변의 가중치의 합이 음수를 갖는 사이클이다. 음수 사이클을 구성하는 어떤 꼭짓점 쌍$i$, $j$에 대해서든지 $i$에서 $j$로 가는 경로의 길이는 음의 무한으로 내려갈 수 있기 때문에 최단 경로가 존재하지 않는다. 수치적으로 의미있는 결과를 얻기 위해서, 플로이드-워셜 알고리즘은 입력에 음수 사이클이 없다고 가정한다. 반면, 음수 사이클이 존재할 경우에는 플로이드-워셜 알고리즘으로 감지할 수 있다. 그 과정은 다음과 같다:

• 플로이드-워셜 알고리즘은 모든 꼭짓점 쌍 $(i,j)$에 대해서 경로를 반복적으로 개선하며, $i=j$일 때에도 개선한다.
• 초기에, 경로 $(i,i)$의 거리는 0이다.
• 경로 $[i,k,\ldots ,i]$는 길이가 0보다 작을 때만 개선이 되므로, 이는 음수 사이클이 존재한다는 것을 의미한다.
• 그렇기 때문에, 이 알고리즘을 수행한 이후에 $(i,i)$가 음수라면 $i$에서 $i$로 되돌아오는 음수 사이클이 존재한다는 것을 의미한다.

따라서, 플로이드-워셜 알고리즘을 이용해서 음수 사이클을 감지하기 위해서는, 경로 행렬의 대각 성분을 확인해서 음수가 나타나는지를 확인한다. 음수가 발견되면 적어도 하나 이상의 음수 사이클이 존재한다는 것을 나타낸다. 수치적 문제를 피하기 위해서는 알고리즘의 안쪽 반복문에서 경로 행렬의 대각 성분에서 음수가 나타나는지를 확인해야 한다. 무향 그래프에서 음의 가중치가 있으면 그 인접한 꼭짓점 사이에서 음수 사이클이 생기는 것은 명백하다 (예: 닫힌 보행). 위의 예시의 모든 변을 방향이 없다고 생각하면, 꼭짓점 수열 4 - 2 - 4는 가중치의 합이 -2인 사이클이다.

경로 복원

플로이드-워셜 알고리즘은 모든 꼭짓점 간의 경로의 길이 만을 제공한다. 간단한 수정으로 두 끝점 사이의 실제 경로를 재현하는 방법을 만들 수 있다. 그중 한 방법으로 각각의 꼭짓점에서 다른 꼭짓점 까지의 실제 경로를 저장할 지도 모르지만, 그럴 필요가 없을 뿐 더러 메모리의 엄청난 낭비가 생긴다. 대신, 각각의 꼭짓점에 대해서 최단 경로 트리를 $\Theta (|E|)$시간복잡도에 각 트리를 저장하는데 $\Theta (|V|)$공간복잡도를 사용해서 계산 할 수 있으며, 이 트리를 이용해서 두 연결된 꼭짓점간의 경로를 효율적으로 재현할 수 있다.

let dist be a $|V|\times |V|$ array of minimum distances initialized to $\infty$ (infinity)
let next be a $|V|\times |V|$ 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] > 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

해석

$n$을 꼭짓점의 갯수 $|V|$로 두자. $n^{2}$개의 $\mathrm {shortestPath} (i,j,k)$ (모든 $i$와 $j$에 대해서)를 $\mathrm {shortestPath} (i,j,k-1)$에서 찾기 위해서는 $2n^{2}$개의 연산이 필요하다. 처음에는 $\mathrm {shortestPath} (i,j,0)=\mathrm {edgeCost} (i,j)$에서 시작했고 and compute the sequence of $n$개의 행렬 $\mathrm {shortestPath} (i,j,1)$, $\mathrm {shortestPath} (i,j,2)$, $\ldots$, $\mathrm {shortestPath} (i,j,n)$을 계산했기 때문에, 사용된 전체 연산의 수는 $n\cdot 2n^{2}=2n^{3}$이다. 따라서, 이 알고리즘의 복잡도는 $\Theta (n^{3})$이다.

적용과 일반화

플로이드-워셜 알고리즘은 다음의 문제들을 다른 알고리즘과 같이 해결할 수 있다:

• 유향 그래프에서 최단 경로(플로이드 알고리즘).
• 유향 그래프의 추이적 폐포(워셜 알고리즘). 워셜 알고리즘의 원래 공식에서, 그래프는 가중치가 없고 진릿값 인접 행렬로 나타냈었다. 그리고 덧셈 연산 대신에 논리곱 (AND)이, 뺄셈 연산을 논리합 (OR)으로 사용했었다.
• 유한 오토마타에서 받아들이는 정규 언어를 나타내는 정규식 찾기(클레이니 알고리즘, 플로이드-워셜 알고리즘의 밀접한 일반화)
• 실행렬의 역행렬 (가우스 요르단 알고리즘)
• 최적 라우팅. 이 적용에서는 두 꼭짓점 간의 최대 흐름을 찾는것이 목표이다. 즉, 위의 의사코드에서 최솟값을 적용하는 것이 아니라 최댓값을 적용해야 한다는 것이다. 변의 가중치는 흐름의 제약을 나타낸다. 경로의 가중치는 병목을 나타내므로 위의 덧셈 연산은 뺄셈 연산으로 대체한다.
• Pathfinder network의 빠른 계산.
• 최대 폭 경로/최대 대역폭 경로
• difference bound matrices (DBMs)의 표준식 계산
• 그래프 간의 유사도 계산

수행

플로이드-워셜 알고리즘은 많은 프로그래밍 언어에서 수행할 수 있다.

• C++: boost::graph 라이브러리
• C#: QuickGraph
• C#: QuickGraphPCL (A fork of QuickGraph with better compatibility with projects using Portable Class Libraries.)
• 자바: Apache Commons Graph 라이브러리
• 자바스크립트: Cytoscape 라이브러리
• MATLAB: Matlab_bgl 패키지
• 펄: Graph 모듈
• 파이썬: SciPy 라이브러리(모듈 scipy.sparse.csgraph)또는 NetworkX 라이브러리
• R: 패키지 e1071과 Rfast

다른 최단 경로 알고리즘과 비교

플로이드-워셜 알고리즘은 거의 대부분이나 모든 꼭짓점 쌍이 변으로 연결된 밀집 그래프에서 모든 꼭짓점 쌍 간의 경로를 계산할 때 적합하다. 음수 가중치가 없는 희소 그래프에서는 모든 꼭짓점에서 출발하는 데이크스트라 알고리즘이 반복 데이크스트라의 수행 시간(피보나치 힙을 사용하면 $O(|E||V|+|V|^{2}\log |V|)$)은 $|E|$가 $|V|^{2}$에 비해 무시할 수 있을 정도면 플로이드-워셜 알고리즘의 수행 시간인 $O(|V|^{3})$보다 적으므로 더 적합하다. 희소 그래프에서 음수 가중치가 있지만 음수 사이클은 없는 경우에는 존슨 알고리즘은 수행 시간이 반복 데이크스트라 시간과 같으므로 사용할 수 있다.

알려진 알고리즘 중에는 밀집 그래프에서 모든 쌍의 최단 경로 계산을 빠르게 하기 위해 빠른 행렬 곱셈을 사용하는 알고리즘도 있지만, 이러한 알고리즘들은 변의 가중치에 추가적인 제약 조건이 따른다(예를 들면 작은 정수여야 한다라는 식으로). 게다가, 수행 시간에서 큰 상수 인자 때문에, 이런 알고리즘들은 매우 큰 그래프에서만 플로이드-워셜 알고리즘보다 빠른 속도를 낼 수 있다.

외부 링크

• 플로이드-워셜 알고리즘의 조작 가능한 애니메이션