플로이드 워셜(Floyd - Warshall)

플로이드 워셜 알고리즘

그래프에서 모든 정점들 간의 최단거리를 구하는 알고리즘

 

 

다익스트라 알고리즘 비교

다익스트라 알고리즘은 하나의 시작 정점을 정해서 다른 모든 정점까지의 최단경로를 구한다.

반면에 플로이드 워셜 알고리즘은 모든 정점을 시작 정점으로 했을 때의 최단경로를 구한다.

따라서 정점 간의 모든 최단거리를 구할 경우에는 플로이드 워셜 알고리즘을 사용한다.

 

다익스트라 알고리즘은 가중치가 음수인 경우에는 사용할 수 없다.

플로이드 워셜 알고리즘은 가중치가 음수라도 사용이 가능하다.

 

---

 

플로이드 워셜 알고리즘에 대해 먼저 간단히 설명하면 이렇다.

플로이드 워셜 알고리즘에서 시작정점(s)와 도착정점(e)간의 최단거리를 구할 때, 경유하는 정점(t)에 관한 개념이 등장한다. 경유하는 정점(t)이란, 말그대로 시작정점(s)이 도착정점(e)에 도달하는 과정에서 정점(t)를 경유한다는 의미이다. 

정점(s)와 정점(e) 간의 최단거리는, 정점(s) 와 정점(t) 사이의 최단거리와 정점(t) 와 정점(e) 사이의 최단거리를 합한 결과가 된다.

dist[s][e] = dist[s][t] + dist[t][e]

(dist[u][v] : 정점(u) 과 정점(v)의 최단거리)

 

만약 시작정점(s)이 도착정점(e)에 도달하는 과정에서 또 다른 정점(t2)를 경유한다고 하자.

그런데 정점(t2)를 경유할 때의 최단거리가 정점(t)를 경유하여 도달할 때보다 더 짧을 수도 있다.

그러면 dist[s][e] 는 dist[s][t2] + dist[t2][e]로 갱신되어야 한다. 

 

정리하자면, 플로이드 워셜 알고리즘은 시작정점(s)에서 도착정점(e)로 도달할 때 경유하는 정점(t)이 무엇이냐에 따라 최단거리가 달라질 수 있으며, 더 짧은 dist[s][t] + dist[t][e]를 발견하면 거리를 갱신해가면서 두 정점간의 최단거리를 구하는 방법이다.

 

이제 예제를 통해 천천히 알고리즘 과정을 따라가보자.

 

시간 복잡도 : O(N³)

필요한 정보

- 그래프 문제가 늘 그렇듯, 간선의 정보를 가지고 있는 인접 행렬 혹은 인접 리스트가 필요하다.

- 두 정점간의 최단거리를 저장하는 dist 2차원 배열

  (dist[u][v] : 정점(u)부터 정점(v)까지 도달하는데 걸리는 최단거리

 

알고리즘

1. dist 이차원 배열을 초기화한다.

• 시작정점과 도착정점이 같은 경우에는 0으로 초기화(자기 자신으로 회귀하는 간선이 없다고 가정)
• 시작정점과 도착정점이 다른 경우에는 무한대(매우 큰 수)로 초기화무한대로 초기화해주는 이유는 알고리즘을 진행하면서 두 정점 사이의 거리를 계속 더 작은 값으로 갱신해주기 때문이다. 초기값을 엄청난 큰 수로 해야 최단거리를 갱신하기 위해 두 거리를 비교할 때, 초기값이 선택되는 일이 없어진다.

      여기서 주의할 점 :

      다익스트라의 경우에는 매우 큰 수로 초기화할 때 Integer.MAX_VALUE 혹은 Long.MAX_VALUE 를

      사용하는 경우가 많은데, 플로이드 워셜 알고리즘에서는 MAX_VALUE로 하면 오버플로우가 발생할 수        있다.

      ex) dist[s][e] = dist[s][t] + dist[t][e] 를 실행할 때, 만약 dist[s][t]도 Integer.MAX_VALUE, dist[t][e]도

           Integer.MAX_VALUE 이면 두 값을 더하면 Integer범위를 벗어나기 때문에 오버플로우가 발생한다.

 

		dist = new int[N + 1][N + 1];
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= N; j++) {
				if (i == j)
					dist[i][j] = 0;
				else
					dist[i][j] = INF;
			}
		}

 

2. 두 정점간에 간선이 존재하면 dist 이차원 배열에 간선의 정보(가중치)를 저장한다.

 

3. 경유정점(t)을 기준으로 두 정점이 해당 경유지를 거쳐갈 때 기존의 거리보다 짧다면 최단거리를 갱신

 

4. 정점이 N번 정점까지 존재한다고 할 때, 경유정점(t)의 후보는 정점1 ~ 정점N까지 될 수 있다.

   정점N까지 위의 과정을 반복

   

 

알고리즘 예제 

아래와 같은 그래프가 있고, 두 정점간의 최단거리를 나타내는 dist 이차원 배열을 표현한 것이 오른쪽이다.

INF 는 무한대라는 의미이며 Infinite의 약자이다. 

 

 

[경유정점이 1번]

 

시작정점(s)이 1번, 도착정점(e)이 1번~6번일 때 :

 

- dist[1][1] : dist[1][1] + dist[1][1] = 0 + 0 = 0  -> dist[1][1]의 초기값 0보다 크기 않으므로 갱신X

- dist[1][2] : dist[1][1] + dist[1][2] = 0 + 3 = 3  -> dist[1][2]의 초기값 3보다 크기 않으므로 갱신X

- dist[1][3] : dist[1][1] + dist[1][3] = 0 + 5 = 10 -> dist[1][3]의 초기값 5보다 크기 않으므로 갱신X

- dist[1][4] : dist[1][1] + dist[1][4] = 0 + INF = INF  -> dist[1][4]의 초기값 INF보다 크기 않으므로 갱신X

- dist[1][5] : dist[1][1] + dist[1][5] = 0 + INF = INF  -> dist[1][5]의 초기값 INF보다 크기 않으므로 갱신X

- dist[1][6] : dist[1][1] + dist[1][6] = 0 + INF = INF  -> dist[1][6]의 초기값 INF보다 크기 않으므로 갱신X

 

시작정점이 2번, 3번, 4번, 5번, 6번인 경우에도 과정은 똑같다.

경유정점이 1번일 때는 최단거리가 갱신되는 경우가 없다.(직접 해보길..여기서는 생략!)

 

 

[경유정점이 2번]

 

시작정점(s)이 1번, 도착정점(e)이 1번~6번일 때 :

 

- dist[1][1] : dist[1][2] + dist[2][1] = 3 + 3 = 6  

- dist[1][2] : dist[1][2] + dist[2][2] = 3 + 0 = 3  

- dist[1][3] : dist[1][2] + dist[2][3] = 3 + 1 = 4  -> dist[1][3] = 5보다 크므로 갱신! dist[1][3] = 4

- dist[1][4] : dist[1][2] + dist[2][4] = 3 + 4 = 7  -> dist[1][4] = INF보다 크므로 갱신! dist[1][4] = 7

- dist[1][5] : dist[1][2] + dist[2][5] = 3 + 6 = 9  -> dist[1][5] = INF보다 크므로 갱신! dist[1][5] = 9

- dist[1][6] : dist[1][2] + dist[2][6] = 3 + INF = INF

 

.

.

.

시작정점(s)가 2번, 3번, 4번, 5번, 6번일 때는 생략

 

 

 

이런식으로 경유정점(t)을 기준으로 두 정점간의 최단거리를 갱신시켜 나가면서 경유정점(t)이 6번인 경우까지 반복한다. 최종적으로 dist 이차원 배열에는 두 정점간의 최단거리가 남게 된다.

 

 

최종 dist 이차원 배열

 

 

플로이드 워셜 코드 : 

	public static void floydWarshall() {

		for (int t = 1; t <= N; t++) {
			for (int s = 1; s <= N; s++) {
				for (int e = 1; e <= N; e++) {
					dist[s][e] = Math.min(dist[s][e], dist[s][t] + dist[t][e]);
				}
			}
		}
	}

 

 

아래는 백준 2660번 : 회장뽑기 문제를 플로이드 워셜 알고리즘으로 구현한 소스코드이다.