문서 보기문서 편집수정 내역 플로이드-워셜 알고리즘 (덤프버전으로 되돌리기) [목차] == 개요 == '''플로이드-워셜 알고리즘'''(Floyd-Warshall Algorithm)은 [[그래프]]에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 시간복잡도는 <math>O(V^3)</math>이다. [[다익스트라 알고리즘]]과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이다. 플로이드와 워셜이 개발하였으며, 이 중 플로이드는 공로를 인정받아 [[튜링상]]을 받았다.[* 정확히 이야기하면, 워셜의 알고리즘을 기반으로 하여 플로이드가 아이디어를 제시한 것에 가깝다. 때문에 플로이드 알고리즘이라고도 부를 때도 있다.][* 다만 이 업적만으로 튜링상을 받은 건 아니고, 플로이드는 컴퓨터 과학 전반적으로 기여한 바가 지대하다. 플로이드는 특히 초창기 프로그래머로서 [[컴파일러]]의 기반이 되는 파서(parser)의 선구자였고, [[프로그래밍 언어]] 이론을 비롯해 자동화된 프로그램 검증과 합성 등 분야의 개척자였다. 소프트웨어 공학의 아버지라고 불려도 무방하다.] == 설명 == 플로이드-워셜 알고리즘은 임의의 노드 '''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]); } }}} [[분류:알고리즘]]캡챠되돌리기