[Algorithm/Java] 플로이드 - 워셜(floyd - warshall) 알고리즘 (최단거리)

플로이드 - 워셜(floyd - warshall) 알고리즘

플로이드 - 워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다. 

시작점을 정해놓고, 해당 시작점에서 다른 모든 노드로의 최단거리를 구하는 다익스트라, 벨만-포드 알고리즘과 다르게

각각의 모든 노드에 대하여 다른 모든 노드로의 최단거리를 구할 수 있는 알고리즘이다.

• 모든 노드 간에 최단 경로를 탐색할 수 있다.
• 음수 가중치 간선이 있어도 수행할 수 있다.
• 동적 계획법을 이용하여 코드가 비교적 간단하다.
• 다른 알고리즘과 다르게 모든 노드사이의 최단거리를 도출하는 알고리즘이기 때문에 3중 for문을 이용한다.
• 시간 복잡도는 O( N^ 3)이다.

---

플로이드 - 워셜 알고리즘 동작 원리

1. 핵심 이론 

2차원 배열에 모든 노드에 대하여 다른 모든 노드로의 최단거리를 저장한다.

가장 핵심적인 원리는 A 노드에서 B까지의 최단경로를 이미 구했는데, 해당 노드가 A -> C -> B의 경로로 이동한다면

A -> C의 최단경로 + C -> B의 최단경로를 통해 이동하게 된다는 것이다.

즉, 하나의 노드에서 다른 노드로의 최단경로에 포함된 부분 경로들은 모두 최단경로들이라는 의미이다.

 

따라서 A부터 B까지의 최단경로는 아래와 같은 방법으로 업데이트할 수 있다.

(A -> C -> B가 A에서 B로 가는 최단경로 일 때)

distance[A][B] = Math.min(distance[A][B], distance[A][C] + distance[C][B]);

---

2. 배열을 선언하고 초기화 하기

distance [s][e]는 노드 s에서 노드 e까지의 최단경로를 저장한다.

s = e인 경우 최단경로는 0으로, 이외의 경우에는 최단경로를 INFINITY로 초기화한다.

코드로 나타내면 아래와 같다. 

final int INF = 1_000_000_000;

int[][] distance = new int[N+1][N+1]; //N : 노드 수
for (int i = 1; i <= N; i++) {
	for (int j = 1; j <= N; j++) {
		if(i != j){
			distance[i][j] = INF;
		}
	}
}

다익스트라, 벨만-포드 알고리즘에서는 INFINITY 값을 Integer.MAX_VALUE로 초기화했지만, 

플로이드 워셜 알고리즘에서는 10억 정도의 적당히 큰 수로 초기화 한다.

플로이드-워셜 알고리즘에서 업데이트할 때는 INF 값에 어떤 수를 더한 값을 비교할 수도 있기 때문에 

오버플로우가 되어서 오류가 발생할 수도 있기 때문이다.

---

3. 최단 거리 배열에 그래프 데이터 저장하기

출발 노드는 s, 도착 노드는 e, 이 간선의 가중치는 w라고 했을 때, distance [s][e] = w로 주어진 그래프 정보를 업데이트한다.

코드로 나타내면 아래와 같다.

int[][] data; // E x 3 배열, 
//data[E][0] : 시작노드  / data[E][1] : 도착 노드 / data[E][2] : 가중치
for (int i = 0; i < e; i++) {
	distance[data[i][0]][data[i][1]] = data[i][2];
}

---

4. 삼중 for문을 돌며 배열 업데이트하기

위의 핵심 원리 부분에서 구한 업데이트 조건에 따라 배열의 값을 업데이트한다.

for(int k = 1; k <= N; k++){
    // i->j (k를 거쳐서 가는 경우가 짧을 때 업데이트
    for (int i = 1; i <= N ; i++) {
        for (int j = 1; j <= N ; j++) {
            //k를 거쳐가는 비용이 INF인 경우 의미가 없음
            if(distance[i][k] == INF || distance[k][j] == INF){
                continue;
            }
            // i -> j 비용과 i -> k -> j 비용을 비교하여 작은값으로 업데이트
            distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
        }
    }
}

---

5. 배열 완성

위의 과정을 통해 완성된 배열은 모든 노드 간의 최단거리 데이터를 담고 있다.

이 배열의 정보가 의미하는 바는 아래와 같다.

• D [1][2] = 8 : 1번 노드에서 2번 노드로 가는 최단경로는 8이다.
• D [3][5] = 15 : 3번 노드에서 5번 노드로 가는 최단경로는 15이다.
• D [4][1] = INF : 4번 노드에서 1번 노드로는 갈 수 없다.

플로이드 워셜 알고리즘은 모든 노드 간의 최단 거리를 확인해 주기 때문에 시간 복잡도가 O(N^3)으로 느리다.

따라서 모든 노드 간의 최단거리가 필요하지 않고, 하나의 노드에서 다른 노드들까지의 최단거리가 필요할 때는 다른 알고리즘을 이용하는 것이 좋다.

---

아래 문제는 위에서 다룬 완전 기본적인 내용만 다룬 코딩테스트 문제이다.

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

위에서 다룬 내용만 그대로 이용해서 풀면 되니, 한번 풀어보세요

---

(이미지 출처) Do it! 알고리즘 코딩 테스트 자바 편
http://www.yes24.com/Product/Goods/108571508