모든 쌍 최단 경로 알고리즘(플로이드 와샬)

가중치 그래프의 두 정점 사이의 거리 중 가장 최단거리는 어떻게 찾을 수 있을까?

 

이 문제를 해결하기 위해서는 모든 시작점으로부터의 최단 경로 정보가 필요하다.

그렇다면 다익스트라 알고리즘을 v번 호출하면 풀 수 있다.

 

https://0923ulee.tistory.com/entry/%EB%8B%A8%EC%9D%BC-%EC%8B%9C%EC%9E%91%EC%A0%90-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C

단일 시작점 최단 경로 알고리즘 (다익스트라, 벨만 포드)

 

그렇지만 더 짧은 길이의 코드로 손쉽게 푸는 방법이 있다!

 

플로이드 워셜 알고리즘

가능한 모든 시작점(모든 정점)으로부터의 최단 경로 정보가 필요할 때 사용하는 알고리즘이다.

 

작은 그래프를 인접 행렬로 저장하고, 3중 for문을 사용해서 최단 거리를 구한다.

 

플로이드 워셜 알고리즘은 DP 알고리즘이다.

3중 for문을 사용하기에 O(V^3)의 시간이 걸린다. 따라서 그래프가 작을 때 사용하는 것을 추천한다.

 

(+) 주어진 그래프의 크기가 작다면 (V<=400)이 알고리즘을 사용하자!

 

코드는 아래와 같다.

void FloydWarshall() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				v[i][j] = min(v[i][j], v[i][k] + v[k][j]); //relax
			}
		}
	}
}

 

안에 있는 2개의 for문은 선택된 두 정점(i,j)를 의미한다.

 

가장 큰 for문은 두 정점 사이에 있는 점 k를 선택해서, k를 통해 가는 경로가 더 짧은지 판단하기 위해 존재한다.

즉, relax하기 위한 점k를 찾기 위한 for문이다.

 

최단 경로를 구하기 위한 완화 작업(Relax)이란? 시작 정점 s에서 v로 가는 경로에서, 간선 u->v를 사용하는 것이 이득인지 판단하는 검사이다. 시작 정점 s에서 v로 가는 기존 경로와 시작 정점 s에서 정점 u를 지나 v로 가는 경로 중 더 짧은 거리를 선택한다는 의미이다. distance[v] = min(distance[v], distance[u] + weight(u->v)) //u를 거치는 방법으로 갱신이 일어난 경우 "완화했다"라고 표현한다.

 

 

아래는 가중치 그래프의 두 정점 사이의 거리 중 가장 최단거리를 찾는 가장 기본적인 플로이드 워셜 문제이다.

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

11404번: 플로이드