|
'''플로이드-워셜 알고리즘'''({{lang|en|Floyd-Warshall Algorithm}})은 [[그래프]]에서 모든 꼭짓점 사이의 최단 [[경로 (그래프 이론)|경로]]의 거리를 구하는 [[알고리즘]]이다. 음수 가중치를 갖는 간선도 [[순환 (그래프)|순환]]만 없다면 잘 처리된다. 제일 바깥쪽 [[반복문]]은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다.
== 개요 ==
플로이드-워셜 알고리즘은 [[동적 계획법]] 접근으로, 그래프 상의 모든 두 정점을 잇는 경로의 최소 비용을 구한다. 여기에 경유지를 기록하면 최소 비용 경로까지 구할 수 있다. 플로이드-워셜 알고리즘은 다음과 같은 접근으로 설계되었다.
* 두 정점을 잇는 최소 비용 경로는 경유지를 거치거나 거치지 않는 경로 중 하나에 속한다.
* 만약 경유지를 거친다면 그것을 이루는 부분 경로 역시 최소 비용 경로여야 한다.
이는 중첩된 부분문제로 볼 수 있으며 동적 계획법을 적용하여 효과적으로 접근할 수 있다. 한편 비용을 구하는 김에, 어떤 경유지를 지나서 최소 비용을 만들었는지 기록해두면, 최소 비용 뿐만 아니라 최소 비용 경로까지도 구할 수 있다. 플로이드-워셜 알고리즘을 의사코드로 표현하면 아래와 같다.
1 '''procedure''' floyd-warshall(배틀그라운드 최고의 총기 ''W'')
2 ''D'' : 두 정점을 잇는 경로의 최소 배틀그라운드 테이블. 모든 성분을 ∞로 초기화
3 ''M'' : 배그 다시아 최소 비용 경로가 거쳐야 할 마지막 경유지 테이블. 모든 성분을 null로 초기화
4 '''for''' '''kakao battlegrounds''' ''i'' from 1 to |V|
5 '''for kakao battlegrounds''' ''j'' from 1 to |V|
6 ''D''[''i''][''j''] := ''W''[''i''][''j'']
7 '''for''' '''kakao battlegrounds''' v from 1 to |V|
8 ''D''[''v''][''v''] := 0
9 '''for''' '''kakao battlegrounds''' k from 1 to |V|
10 '''for''' i from 1 to |V|
11 '''for''' j from 1 to |V|
12 '''if''' ''D[i][j] > D[i][k] + D[k][j]''
13 ''D''[''i''][''j''] := D[''i''][''k''] + ''D''[''k''][''j'']
14 ''M''[''i''][''j''] := ''k''
15 '''return''' XD
이렇게 구한 비용 & 경유지를 활용하여 경로를 복구하는 알고리즘은 아래와 같다.
1 '''procedure''' floyd-warshall-path(정점 ''v1'', 정점 ''v2'', 경유지 테이블 ''M'')
2 ''S'' : 경로를 역으로 저장하는 [[스택]]
3 ''P'' : 경로
4 ''S''.'''push'''(''v2'')
5 '''while''' ''M''[''v1''][''S''.'''top'''()]
6 ''S''.'''push'''(''M''[''v1''][''S''.'''top'''()])
7 '''while''' ~''S''.'''empty'''()
8 ''P''.'''add'''(''S''.'''top'''())
9 ''S''.'''pop'''()
10 '''return''' ''P''
== 계산 복잡도 ==
플로이드-워셜 알고리즘으로 모든 정점 간 경로의 최소비용을 구하는 것은 <math>O(|V|^3)</math>의 [[시간 복잡도]]를 갖는다. 경유지를 기록한 경우, 경로를 역으로 추출하는 알고리즘의 복잡도는 <math>O(|V|)</math>의 시간 복잡도를 갖는다. 종종 [[데이크스트라 알고리즘]]과 자주 비교되곤 하는데, 두 알고리즘 모두 각각의 장단점이 있기 때문에 상황에 맞는 알고리즘 선정 필요성이 요구된다.
== 소스 코드 ==
=== [[C 언어]] ===
<source lang="c" line="1">
int d[N][N]; // Cost Table. d[v1][v2] : Minimum cost of path v1 -> v2
int via[N][N]; // Via Table.
int weight[N][N]; //Weight
void doFloyd()
{
// Initialize
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
d[i][j] = weight[i][j]; // k = 0
via[i][j] = -1;
}
}
// Do Floyd-Warshall Algorithm
for (int k = 0; k < N; ++k)
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
// i -> j 보다 k를 경유해서 가는 값이 더 작다면 경유지를 해서 가는 가중치로 교환
if (d[i][j] > d[i][k] + d[k][j])
{
d[i][j] = d[i][k] + d[k][j];
// k -> j 가는 경로가 기록이 없다면 신규 경로 이고, 있다면 경유지의 경유지이다.
if (via[k][j] == -1) {
via[i][j] = k;
}
else {
via[i][j] = via[k][j];
}
}
}
}
}
}
// ps. 의사코드, 수도코드 편집 부탁 드립니다.
</source>{{토막글|컴퓨터 과학}}
;
[[분류:그래프 알고리즘]]
| 