[C++] 플로이드 와샬 (Floyd-Warshall Algorithm)

Floyd-Warshall

플로이드 알고리즘, 로이-와샬 알고리즘, 로이-플로이드 알고리즘, WIFI 알고리즘 등으로 불린다.

 

그래프에서 최단경로를 찾는 문제를 해결하는 알고리즘의 한 종류이다. 다익스트라 알고리즘의 경우 가중치가 양수이고, 하나의 시작점으로부터 다른 모든 버텍스(vertex, node, 노드)까지의 최소 비용을 구한다. 플로이드 와샬은 이 다익스트라를 여러 번 행하여 모든 버텍스에서 다른 모든 버텍스까지의 경로를 구하는 알고리즘이다. 시간 복잡도는 O(n^3)이다. 이론적으로 이해하는 데에는 시간이 조금 걸리지만 코드는 그냥 반복문 세 개 갖다 쓰는 거라 매우 간단하다.

 

 

이론

현재 나의 위치가 i이고, j까지 가는 최단경로를 알고 싶다.

i에서 j로 한 번에 가지는 경우가 최단거리 일 수도 있지만, 어떤 지점 k를 거쳐가야 하는 경우도 존재한다.

즉 i에서 j로 갈 때 드는 최소 비용은 i에서 j로 바로 가는 것과, i에서 k를 들렸다 j로 가는 방법 둘 중 하나다.

 

 

위 예제를 통해 다시 한번 정리해 보자.

i에서 j로 가는 최단거리는 현재까지 i에서 j로 바로 가는 방법과 i에서 2를 들린 후, 2에서 j를 가는 방법이 있다.

그런데 i에서 j로 바로 가는 방법은 존재하지 않으므로, 최단거리는 i에서 2를 들린 후 2에서 j를 들리는 방법밖에 없다.

그럼 이제 i에서 2로 가는 최단거리를 구해보자.

i에서 2로 가는 최단거리는 i에서 4를 들리고 4에서 2로 가거나, i에서 3을 들리고 3에서 2 로가는 두 가지 방법이 존재한다. 이 둘 중 더 작은 값이 최단거리가 된다. top-bottom 방식으로 이렇게 따라가면 결국 i에서 j까지의 최단거리를 알 수 있다. 이런 방식으로 모든 노드를 i와 j라고 생각하고 작업하면 된다.

 

코드

for(int k=1; k<=n; k++) {
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			paths[i][j] = min(paths[i][j], paths[i][k]+paths[k][i]);
		}
	}
}

엄청 엄청 간단하다.

paths 배열은 i to j의 가중치를 저장하는 배열이다. 이때 길이 없는 경우는 99999와 같이 큰 값으로 설정해 주거나, 0으로 설정한 뒤 반복문에 조건문을 추가하여 처리한다.

i에서 j까지 가는데 k를 거쳐간 경우와 i에서 j로 바로 간 경우 중 더 작은 값을 저장하는 것이다.

 

예제

 

https://www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙

백준의 예제 문제를 풀어보자.

 

 

스포 주의

#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	
	int paths[n+1][n+1];
	
	// path initialize
	for(int i=0; i<=n; i++) {
		for(int j=0; j<=n; j++) {
			paths[i][j] = 99999;
		}
	}
	
	// find paths
	for(int i=0; i<m; i++) {
		int a, b;
		cin >> a >> b;
		paths[a][b] = 1;
		paths[b][a] = 1;
	}

	// find shortest paths
	for(int k=1; k<=n; k++) {
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				paths[i][j] = min(paths[i][j], paths[i][k]+paths[k][j]);
			}
		}
	}
	
//	for(int i=1; i<=n; i++) {
//		for(int j=1; j<=n; j++) {
//			cout << paths[i][j] << " ";
//		}
//		cout << endl;
//	}
	
	int target;
	int answer = 9999;
	for(int i=1; i<=n; i++) {
		int kevin = 0;
		for(int j=1; j<=n; j++) {
			if(i != j) {
				kevin += paths[i][j];
			}
		}
		if(kevin < answer) {
			target = i;
			answer = kevin;
		}
	}
	
	cout << target;
}

배열의 값을 9999로 초기화한 뒤 경로가 존재하는 부분은 1로 변경해 준다. 이후 플로이드 와샬 알고리즘을 돌면서 최단경로를 찾는다.