문서:플로이드-워셜 알고리즘

[목차]
== 개요 ==
'''플로이드-워셜 알고리즘'''(Floyd-Warshall Algorithm)은 [[그래프]]에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.

시간복잡도는 <math>O(V^3)</math>이다. [[다익스트라 알고리즘]]과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이다. 플로이드와 워셜이 개발하였으며, 이 중 플로이드는 공로를 인정받아 [[튜링상]]을 받았다.[* 정확히 이야기하면, 워셜의 알고리즘을 기반으로 하여 플로이드가 아이디어를 제시한 것에 가깝다. 때문에 플로이드 알고리즘이라고도 부를 때도 있다. ]

== 설명 ==
플로이드-워셜 알고리즘은 임의의 노드 '''s'''에서 '''e'''까지 가는 데 걸리는 최단거리를 구하기 위해, '''s'''와 '''e''' 사이의 노드인 '''m'''에 대해 '''s'''에서 '''m'''까지 가는 데 걸리는 최단거리와 '''m'''에서 '''e'''까지 가는 데 걸리는 최단거리를 이용한다.

조금 더 구체적인 설명을 위해, 임의의 노드 '''s''' 부터 '''e''' 까지 가는데 걸리는 최단거리를 {{{d[s][e]}}}라고 하자. (처음에 {{{d[s][e]}}}의 값은 노드 '''s'''와 노드 '''e'''가 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)로 초기화한다.[* INF에 대한 설명은 [[다익스트라 알고리즘]] 문서를 참고.]) 이 {{{d[s][e]}}}를 구하기 위해서, '''s'''와 '''e''' 사이의 모든 노드 '''m'''에 대해, 현재 {{{d[s][e]}}}에 저장되어 있는 값과, {{{d[s][m]+d[m][e]}}}의 값을 비교한다. 이 때 {{{d[s][m]+d[m][e]}}}의 값이 현재의 {{{d[s][e]}}} 값보다 작으면, {{{d[s][e]}}}를 {{{d[s][m]+d[m][e]}}} 의 값으로 업데이트한다. 

=== 코드 ===
단순히 반복문을 3번 중첩시키기만 하면 되기 때문에 구현에 있어 크게 어려운 부분은 없다. 단, 유의하여야 할 점은 for문에서 가운데 노드(m)이 제일 위에 있어야 한다는 점이다. 어쨌든 매우 간결하다.

C언어로 구현한 플로이드-워셜 알고리즘은 다음과 같다.(C++)

{{{#!syntax cpp
void Floyd_Warshall() {
  for(m=1; m<=N; m++)
    for(s=1; s<=N; s++)
      for(e=1; e<=N; e++)
        if (d[s][e] > d[s][m] + d[m][e])
			d[s][e] = d[s][m] + d[m][e];
}
}}}

다음 프로그램은 플로이드-워셜 알고리즘을 사용하여 그래프를 인접 행렬 형태로 입력받아 임의의 노드로부터 임의의 노드까지 가는 최단거리를 구해준다.

{{{#!syntax cpp
//Floyd calculates shortest dist from all nodes to all nodes

/*
0. Initialize d with inf except adj nodes
1. Find d[s][e] by comparing current d[s][e] with d[s][m]+d[m][e]
*/

#include <stdio.h>
#define INF 1<<20

int d[1000][1000];
int n, m;

void Init()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if(i!=j) d[i][j] = INF; 
}

void Floyd()
{
	for (int m = 1; m <= n; m++) //가운데 노드
		for (int s = 1; s <= n; s++) //시작 노드
			for (int e = 1; e <= n; e++) //마지막 노드
				if (d[s][e] > d[s][m] + d[m][e])
					d[s][e] = d[s][m] + d[m][e]; //가운데를 거쳐가는 것이 더 빠르면 그걸로 업데이트한다.
}

int main()
{
	scanf("%d %d", &n, &m); //n: 노드의 개수, m: 간선의 개수
	Init(); //d의 모든 값을 무한으로 초기화(단, d[i][i]는 0)
	for (int i = 0; i < m; i++) { //인접행렬 입력받기
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);
		d[x][y] = c;
	}

	Floyd();

	for (int i = 1; i <= n; i++) //모든 경로의 최단거리 출력
		for(int j=1; j<=n; j++)
			printf("Shortest dist from %d to %d: %d\n", i, j, d[i][j]);
}
}}}
[[분류:알고리즘]]