플로이드-워셜 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

플로이드-워셜 알고리즘은 동적 계획법의 일종으로, 그래프 내의 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다. 로버트 플로이드가 1962년에 발표했으며, 버나드 로이, 스티븐 워셜 등의 연구와도 관련이 있다. 이 알고리즘은 각 정점 쌍을 지나는 모든 경로를 비교하여 최단 경로를 찾아내며, 그래프의 꼭짓점 개수를 N이라고 할 때, 시간 복잡도는 O(N^3)이다. 플로이드-워셜 알고리즘은 유향 그래프의 최단 경로 탐색, 추이적 폐포 계산, 정규식 찾기 등 다양한 문제에 적용되며, C++, C#, 자바, 파이썬 등 여러 프로그래밍 언어로 구현 가능하다. 밀집 그래프에서 모든 쌍의 최단 경로를 계산할 때 유용하며, 희소 그래프에서는 데이크스트라 알고리즘 등 다른 알고리즘이 더 효율적일 수 있다.

플로이드-워셜 알고리즘

📚 더 읽어볼만한 페이지

의사코드가 있는 문서 - 플러드 필
플러드 필은 2차원 배열 또는 이미지에서 연결된 영역을 채우는 알고리즘으로, 4방향 또는 8방향 연결 방식을 사용하며, 이미지 편집 프로그램, 2D 게임 등 다양한 분야에 활용되지만 스택 오버플로우나 캐시 미스 등의 단점을 보완하기 위한 최적화 기법이 존재한다.
의사코드가 있는 문서 - 데이크스트라 알고리즘
데이크스트라 알고리즘은 에츠허르 데이크스트라가 고안한 알고리즘으로, 그래프에서 한 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾으며, 내비게이션과 네트워크 라우팅 등에 응용되고 가중치가 음수가 아닌 그래프에서 효율적으로 작동한다.
다항 시간 문제 - 벨먼-포드 알고리즘
벨만-포드 알고리즘은 그래프에서 단일 시작점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이며, 음수 가중치 간선이 있는 그래프에도 적용 가능하지만 음수 사이클이 존재하면 최단 경로를 찾을 수 없고 음수 사이클 탐지에 활용되며, 시간 복잡도는 O(|V| * |E|)이다.
다항 시간 문제 - 크러스컬 알고리즘
크러스컬 알고리즘은 그래프의 최소 신장 트리를 찾는 알고리즘으로, 간선들을 가중치 순으로 정렬하고 사이클을 형성하지 않는 간선들을 추가하여 최소 신장 트리를 구성하며 시간 복잡도는 O(E log V) 또는 O(E α(V))이다.
라우팅 알고리즘 - A* 알고리즘
A* 알고리즘은 가중치 그래프에서 시작 노드부터 목표 노드까지 최소 비용 경로를 찾는 정보 탐색 알고리즘으로, 경로 비용과 목표까지 추정 비용의 합을 최소화하여 경로를 탐색하며 내비게이션, 게임 AI 등에 활용된다.
라우팅 알고리즘 - 점프 플러딩 알고리즘
점프 플러딩 알고리즘(JFA)은 이미지 내 각 픽셀에서 가장 가까운 특징까지의 거리를 효율적으로 계산하는 알고리즘으로, 컴퓨터 그래픽스, 이미지 처리, 컴퓨터 비전 등 다양한 분야에서 활용되며, 특히 거리장 생성, 점 구름 렌더링, 특징 매칭, 소프트 섀도우 렌더링, 파워 다이어그램 계산, 게임 개발 등에 유용하게 사용됩니다.

1. 개요
2. 역사와 이름
3. 알고리즘
4. 해석
5. 적용과 일반화
6. 구현
7. 다른 최단 경로 알고리즘과 비교

2. 역사와 이름

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

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

3. 알고리즘

플로이드-워셜 알고리즘은 그래프 내의 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다. 각 정점 쌍을 지나는 모든 경로를 비교하며, 최대 $\Omega (|V|^2)$ 개의 간선(변)이 있을 수 있으므로, 총 $\Theta(|V|^3)$ 번의 비교를 통해 최단 경로를 찾는다.

핵심 아이디어는 두 정점 간의 최단 경로를 점진적으로 개선하는 것이다. 초기에는 직접적인 간선만 고려하고, 이후 중간 정점을 하나씩 추가하며 최단 경로를 갱신한다.

1부터 $N$ 까지 번호가 매겨진 $V$ 개의 정점을 가진 그래프 $G$ 에서, $\mathrm{shortestPath}(i,j,k)$ 함수는 $i$ 에서 $j$ 로 가는 경로 중, 중간 정점으로 집합 $\{1,2,\ldots,k\}$ 에 속하는 정점들만 사용 가능한 최단 경로를 반환한다. 이 함수를 이용해 모든 정점 $i$ 에서 모든 정점 $j$ 로 가는 최단 경로를 찾을 수 있다.

$\mathrm{shortestPath}(i,j,k)$ 는 다음 두 가지 경우 중 하나이다.

* (1) $k$ 를 지나지 않는 경로: 집합 $\{1,\ldots,k-1\}$ 에 속하는 정점만 중간 정점으로 사용한다.
* (2) $k$ 를 지나는 경로: $i$ 에서 $k$ 까지 ( $\{1,\ldots,k-1\}$ 만 거쳐서) 가는 경로와 $k$ 에서 $j$ 까지 ( $\{1,\ldots,k-1\}$ 만 거쳐서) 가는 경로로 구성된다.

$i$ 에서 $j$ 까지 $1$ 부터 $k-1$ 까지의 정점만 거치는 최단 경로는 $\mathrm{shortestPath}(i,j,k-1)$ 이다. $i$ 에서 $k$ 를 거쳐 $j$ 로 가는 더 짧은 경로가 있다면, 그 경로는 $i$ 에서 $k$ 까지 가는 최단 경로와 $k$ 에서 $j$ 까지 가는 최단 경로를 합친 것이다.

$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$ 일 때, $k=2$ 일 때, ..., $k=N$ 이 될 때까지 반복하여 최단 경로를 찾는다.

다음은 알고리즘의 의사 코드이다.

```
// 초기화
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u,v)
dist[u][v] ← w(u,v) // 변 (u,v)의 가중치
for each vertex v
dist[v][v] ← 0

// 본 계산
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]
dist[i][j] ← dist[i][k] + dist[k][j]
end if

3.1. 예시

플로이드-워셜 알고리즘은 위 그래프에서 다음과 같이 동작한다.

* k = 0: 초기 상태. 각 정점 쌍 사이의 최단 거리는 간선의 가중치로 주어진다. 연결된 간선이 없는 경우는 무한대(∞)로 표시한다.

👆

좌우로 밀어서 보기

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

* k = 1: 정점 1을 중간 정점으로 거쳐가는 경우를 고려한다.
* 2 → 3: 2 → 1 → 3 (4 + (-2) = 2) 경로가 기존의 3보다 짧으므로 갱신된다. (굵은 글씨로 표시)

👆

좌우로 밀어서 보기

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

* k = 2: 정점 1과 2를 중간 정점으로 거쳐가는 경우를 고려한다.
* 4 → 1: 4 → 2 → 1 (-1 + 4 = 3) 경로가 기존의 ∞보다 짧으므로 갱신된다.
* 4 → 3: 4 → 2 → 1 → 3 (-1 + 4 + (-2) = 1) 경로가 기존의 ∞보다 짧으므로 갱신된다.

👆

좌우로 밀어서 보기

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

* k = 3: 정점 1, 2, 3을 중간 정점으로 거쳐가는 경우를 고려한다.
* 1 → 4: 1 → 3 → 4 (-2 + 2 = 0) 경로가 기존의 ∞보다 짧으므로 갱신된다.
* 2 → 4: 2 → 3 → 4 (2 + 2 = 4) 경로가 기존의 ∞보다 짧으므로 갱신된다.

👆

좌우로 밀어서 보기

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

* k = 4: 정점 1, 2, 3, 4를 중간 정점으로 거쳐가는 경우를 고려한다.
* 1 → 2: 1 → 4 → 2 (0 + (-1) = -1) 경로가 기존의 ∞보다 짧으므로 갱신된다.
* 3 → 1: 3 → 4 → 1 (2 + 3 = 5) 경로가 기존의 ∞보다 짧으므로 갱신된다.
* 3 → 2: 3 → 4 → 2 (2 + (-1) = 1) 경로가 기존의 ∞보다 짧으므로 갱신된다.

👆

좌우로 밀어서 보기

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

최종적으로 모든 정점 쌍 사이의 최단 거리가 구해진다. 예를 들어, 정점 1에서 정점 2로 가는 최단 거리는 -1이다.

3.2. 음수 사이클에서 행동

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

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

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

3.3. 경로 복원

플로이드-워셜 알고리즘은 모든 꼭짓점 간의 최단 경로의 길이뿐만 아니라 실제 경로도 제공한다. 이를 위해 `next`라는 추가적인 배열을 사용한다. `next[i][j]`는 i에서 j로 가는 최단 경로에서 i 다음에 방문하는 꼭짓점을 저장한다.

초기화 단계에서 `next[i][j]`는 i에서 j로 가는 간선이 있다면 j, 그렇지 않다면 null 값으로 설정된다. 알고리즘의 각 단계에서 최단 거리가 갱신될 때, `next[i][j]`도 함께 갱신된다. 즉, `dist[i][j]`가 `dist[i][k] + dist[k][j]`를 통해 갱신된다면, `next[i][j]`는 `next[i][k]`의 값으로 갱신된다.

경로 복원은 다음의 `Path(u, v)` 프로시저를 통해 수행된다.

1. `next[u][v]`가 null이면, u와 v 사이에 경로가 없음을 의미하므로 빈 리스트를 반환한다.
2. 경로를 저장할 `path` 리스트를 초기화하고, 시작 꼭짓점 u를 추가한다.
3. u가 v와 같아질 때까지, `u`를 `next[u][v]`로 갱신하고 `path`에 추가하는 과정을 반복한다.
4. 최종적으로 `path` 리스트를 반환한다.

이러한 방식으로, 플로이드-워셜 알고리즘은 각 꼭짓점 쌍 사이의 최단 경로를 효율적으로 복원할 수 있다.

각각의 꼭짓점에서 다른 꼭짓점까지의 실제 경로를 저장하는 방법은 메모리 낭비가 심하기 때문에, 각 꼭짓점에 대해서 최단 경로 트리를 계산하여 저장하는 방법을 사용할 수 있다. 이 트리를 이용하면 두 꼭짓점 간의 경로를 효율적으로 재현할 수 있다.

4. 해석

$n$ 을 꼭짓점의 개수로 둔다. 모든 $i$ 와 $j$ 에 대해 $\mathrm{shortestPath}(i,j,k-1)$ 에서 $\mathrm{shortestPath}(i,j,k)$ 의 모든 $n^2$ 개를 찾으려면 $\Theta(n^2)$ 연산이 필요하다. $\mathrm{shortestPath}(i,j,0) = \mathrm{edgeCost}(i,j)$ 로 시작하여 $n$ 개의 행렬 시퀀스 $\mathrm{shortestPath}(i,j,1)$ , $\mathrm{shortestPath}(i,j,2)$ , $\ldots$ , $\mathrm{shortestPath}(i,j,n)$ 을 계산하는데, 각 행렬은 $\Theta(n^2)$ 의 비용이 들므로, 알고리즘의 총 시간 복잡도는 $n \cdot \Theta(n^2) = \Theta(n^3)$ 이다.

5. 적용과 일반화

플로이드-워셜 알고리즘은 다음과 같은 다양한 문제들을 해결하는데 사용될 수 있다.

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

6. 구현

플로이드-워셜 알고리즘은 다양한 프로그래밍 언어로 구현할 수 있다. 다음은 몇 가지 예시이다.

👆

좌우로 밀어서 보기

언어	라이브러리/패키지	비고
C++	[http://www.boost.org/libs/graph/doc/ boost::graph]
C#	[https://web.archive.org/web/20100317031339/http://www.codeplex.com/quickgraph QuickGraph]
C#	[https://www.nuget.org/packages/QuickGraphPCL/3.6.61114.2 QuickGraphPCL]	QuickGraph 포크, 이식 가능한 클래스 라이브러리와 호환성 개선
자바	[http://commons.apache.org/sandbox/commons-graph/ Apache Commons Graph]
자바스크립트	Cytoscape
MATLAB	[http://www.mathworks.com/matlabcentral/fileexchange/10922 Matlab_bgl]
펄	[https://metacpan.org/module/Graph Graph]
파이썬	SciPy (scipy.sparse.csgraph 모듈) 또는 NetworkX	[http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html scipy.sparse.csgraph]
R	e1071, Rfast	[https://cran.r-project.org/web/packages/e1071/index.html e1071], [https://cran.r-project.org/web/packages/Rfast/index.html Rfast]
줄리아	[https://docs.juliahub.com/Graphs/VJ6vx/1.7.0/algorithms/shortestpaths/#Graphs.floyd_warshall_shortest_paths-Union{Tuple{AbstractGraph{U}},%20Tuple{T},%20Tuple{U},%20Tuple{AbstractGraph{U},%20AbstractMatrix{T}}}%20where%20{U%3C:Integer,%20T%3C:Real} Graphs.jl] \|\|
C	pthreads를 사용한 [https://moorejs.github.io/APSP-in-parallel/ 병렬화된] 구현	SQLite 인터페이스 포함 ([https://github.com/gdavidbutler/pthreadChannel/blob/master/example/floydWarshall.h floydWarshall.h])

* JavaApplet 구현: [http://alexle.net/stuff/floyd-algorithm/ Alex Le's Blog]
* 파이썬 구현: [https://networkx.lanl.gov/ NetworkX] 패키지

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

플로이드-워셜 알고리즘은 모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘으로, 특히 밀집 그래프에서 효과적이다. 하지만 특정 상황에서는 다른 알고리즘들이 더 효율적일 수 있다.

* [[데이크스트라 알고리즘]]: 음수 가중치가 없는 희소 그래프에서, 모든 정점에서 출발하는 데이크스트라 알고리즘을 반복하는 것이 플로이드-워셜 알고리즘보다 빠르다. 피보나치 힙을 사용하면 데이크스트라 알고리즘의 수행 시간은 $O(|E||V| + |V|^2 \log |V|)$ 이며, 이는 $|E|$ 가 $|V|^2$ 보다 훨씬 작을 때 플로이드-워셜 알고리즘의 $O(|V|^3)$ 보다 작다. 가중치가 음수가 아닌 그래프에서 단일 정점에서 모든 최단 경로를 찾는 데에는 $\Theta(|E| + |V| \log |V|)$ 의 시간이 걸리고, 각 정점에서 시작하면 $\Theta(|E||V| + |V|^2 \log |V|)$ 의 시간이 걸린다. 그래프가 밀집되어 $|E| \approx |V|^2$ 인 경우 플로이드-워셜 알고리즘이, 희소하여 $|E|$ 가 $|V|^2$ 보다 현저히 작은 경우 다익스트라 알고리즘이 우세하다.

* [[존슨 알고리즘]]: 음수 가중치가 있지만 음수 사이클이 없는 희소 그래프에서 사용할 수 있으며, 반복적인 데이크스트라 알고리즘과 동일한 점근적 실행 시간을 가진다.

* [[행렬 곱셈|빠른 행렬 곱셈]]을 이용하는 알고리즘: 밀집 그래프에서 모든 쌍의 최단 경로 계산을 빠르게 수행할 수 있지만, 간선 가중치에 추가적인 제약 조건(예: 작은 정수)이 필요하다. 또한, 큰 상수 인자 때문에 매우 큰 그래프에서만 플로이드-워셜 알고리즘보다 빠르다.