플로이드-워셜 알고리즘

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

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

1. 개요

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

2. 역사와 이름

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

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

3. 알고리즘

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

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

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$ 로 되돌아오는 음수 사이클이 존재한다는 것을 의미한다.

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

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

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

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. 적용과 일반화

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

유향 그래프에서 최단 경로를 찾는다. (플로이드 알고리즘)
유향 그래프의 추이적 폐포를 구한다. (워셜 알고리즘) 원래 워셜 알고리즘에서 그래프는 가중치가 없었고, 진릿값 인접 행렬로 표현되었다. 덧셈 연산 대신 논리곱(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$ 보다 현저히 작은 경우 다익스트라 알고리즘이 우세하다.

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

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

참조

_[1] 서적 Introduction to Algorithms
_[2] 서적 Discrete Mathematics and Its Applications, 5th Edition Addison Wesley
_[3] 저널 Algorithm 97: Shortest Path 1962-06
_[4] 저널 Transitivité et connexité. https://gallica.bnf.[...]
_[5] 저널 A theorem on Boolean matrices 1962-01
_[6] Mathworld Floyd-Warshall Algorithm
_[7] 서적 Automata Studies Princeton University Press
_[8] 저널 Algorithm 141: Path Matrix 1962-11
_[9] 웹사이트 Section 8.9: Floyd-Warshall algorithm for all pairs shortest paths http://www.ieor.berk[...] Department of Industrial Engineering and Operations Research, University of California, Berkeley 2014
_[10] 저널 The Floyd–Warshall algorithm on graphs with negative cycles 2010-04
_[11] 웹사이트 Free Algorithms Book https://books.goalki[...]
_[12] 서적 Path Problems in Networks Springer International Publishing 2022
_[13] 인용 Handbook of Graph Theory https://books.google[...] CRC Press
_[14] 저널 Algebraic Structures for Transitive Closure
_[15] 보고서 Scheduling Tasks with AND/OR precedence contraints (PhD Thesis, Appendix B) http://www.ece.ubc.c[...]
_[16] 인용 All pairs shortest paths using bridging sets and rectangular matrix multiplication 2002-05
_[17] 인용 More algorithms for all-pairs shortest paths in weighted graphs 2010-01
_[18] 서적 Introduction to Algorithms
_[19] 서적 Discrete Mathematics and Its Applications, 5th Edition Addison Wesley
_[20] 저널 Algorithm 97: Shortest Path 1962-06
_[21] 저널 Transitivite et connexite.
_[22] 저널 A theorem on Boolean matrices 1962-01
_[23] 매스월드 Floyd-Warshall Algorithm
_[24] 서적 Automata Studies Princeton University Press
_[25] 저널 Algorithm 141: Path Matrix 1962-11
_[26] 웹인용 Section 8.9: Floyd-Warshall algorithm for all pairs shortest paths http://www.ieor.berk[...] Department of Industrial Engineering and Operations Research, University of California, Berkeley 2018-07-09
_[27] 저널 The Floyd-Warshall algorithm on graphs with negative cycles http://www.sciencedi[...] 2010-04
_[28] 인용 Handbook of Graph Theory https://books.google[...] CRC Press
_[29] 웹인용 Algebraic Structures for Transitive Closure http://citeseerx.ist[...]
_[30] 인용 All pairs shortest paths using bridging sets and rectangular matrix multiplication 2002-05
_[31] 인용 More algorithms for all-pairs shortest paths in weighted graphs 2010-01

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com