플로이드 워셜 알고리즘

개요

그래프의 한 정점에서 다른 정점으로 갈 때의 최단 경로를 구하는 대표적인 알고리즘은 `다익스트라 알고리즘`과 `플로이드 워셜 알고리즘`이 있다.

 

다익스트라 알고리즘은 어느 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이고, 여기서 알아볼 플로이드 워셜 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다.

 

💡 플로이드 워셜 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다.

 

플로이드 워셜 알고리즘의 순서는 다음과 같다.

1. 모든 정점에서 각자의 간선에 따른 최단 거리 테이블을 갱신한다.
2. 2~N번 정점이 1번 정점을 거쳐갈 수 있는 경로가 있거나 최소가 되는 경로가 있다면 최단 거리 테이블을 갱신한다.
3. 1, 3~N번 정점이 2번 정점을 거쳐갈 수 있는 경로가 있거나 최소가 되는 경로가 있다면 최단 거리 테이블을 갱신한다.
4. 해당 과정을 모든 정점이 기준 노드를 한번씩 할 때까지 반복한다.

이렇게 플로이드 워셜 알고리즘을 수행하면 모든 정점에서 모든 정점에 대한 최단 경로를 찾을 수 있다.

 

소스 코드

알고리즘 자체가 간단한만큼 소스 코드도 간단하다.

// 초기화 코드
int[][] shortest = new int[n + 1][n + 1];
for (int v1 = 1; v1 <= n; v1++) {
	for (int v2 = 1; v2 <= n; v2++) {
		if (v1 == v2) shortest[v1][v2] = 0;
		else if (v1 -> v2로 가는 것이 있다면) shortest[v1][v2] = w;
		else shortest[v1][v2] = INF;
	}
}

// 실제 알고리즘
for (int v1 = 1; v1 <= n; v1++) {
	for (int v2 = 1; v2 <= n; v2++) {
		for (int v = 1; v <= n; v++) {
			shortest[v2][v] = Math.min(shortest[v2][v], shortest[v2][v1] + shortest[v1][v]);
		}
	}
}

 

단순하게 중간 노드 v1, 최단 경로 시작 노드 v2, 최단 경로 도착 노드 v 순으로 3중 for문을 만들면 된다.

 

 

1238 - 파티 : https://www.acmicpc.net/problem/1238