나무모에 미러 (일반/어두운 화면)
최근 수정 시각 : 2024-08-17 07:50:10

플로이드-워셜 알고리즘

플로이드 알고리즘에서 넘어옴
1. 개요2. 설명
2.1. 코드

1. 개요

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

시간복잡도는 O(V3)O(V^3)이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이다. 로버트 플로이드와 스티븐 워셜이 개발하였으며, 이 중 플로이드는 공로를 인정받아 튜링상을 받았다.[1][2]

2. 설명

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

조금 더 구체적인 설명을 위해, 임의의 노드 s 부터 e 까지 가는데 걸리는 최단거리를 d[s][e]라고 하자. (처음에 d[s][e]의 값은 노드 s와 노드 e가 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)로 초기화한다.[3]) 이 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] 의 값으로 업데이트한다.

2.1. 코드

단순히 반복문을 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]);
}

[1] 정확히 이야기하면, 워셜의 알고리즘을 기반으로 하여 플로이드가 아이디어를 제시한 것에 가깝다. 때문에 플로이드 알고리즘이라고도 부를 때도 있다.[2] 다만 이 업적만으로 튜링상을 받은 건 아니고, 플로이드는 컴퓨터 과학 전반적으로 기여한 바가 지대하다. 플로이드는 특히 초창기 프로그래머로서 컴파일러의 기반이 되는 파서(parser)의 선구자였고, 프로그래밍 언어 이론을 비롯해 자동화된 프로그램 검증과 합성 등 분야의 개척자였다. 소프트웨어 공학의 아버지라고 불려도 무방하다.[3] INF에 대한 설명은 다익스트라 알고리즘 문서를 참고.

분류