Floyd Warshall 알고리즘

❒ Description

---

프로그래머스 Lv3. 순위 문제를 풀면서 알게된 Floyd Warshall 알고리즘에 대해서 학습하자.

프로그래머스

 

 

 

 

 

 

❒ Floyd Warshall 알고리즘

---

Floyd warshall 알고리즘은 모든 노드간의 최단 경로 탐색이 필요한 경우에 사용한다.

음의 가중치가 있어도 사용할 수 있으며, O(v³)의 시간 복잡도를 갖는 알고리즘이다. 

 

Floyd warshall 알고리즘의 핵심 아이디어는 거쳐가는 정점을 기준으로 최단거리를 구하는 것이다. 

Example image

거쳐가는 정점을 A로 하게 경로는 `C → A → B`, `B → A → C`, `D → A → C`, `D → A → B`로 총 4개가 된다.

※ 참고 블로그 
https://blog.naver.com/ndb796/221234427842
https://sh1mj1-log.tistory.com/151

 

 

 

 

 

❒ Java로 구현하기

---

Java 코드는 아래의 순서로 구현하면 된다.

 

i. 인접행렬 만들기

ii. 각 노드간의 최단 거리 인접행렬 update

iii. 3중 for문을 순회하며 인접행렬 update

 

위 순서를 적용하여 백준: 플로이드 문제를 풀어보자.

// i. 인접행렬 만들기
int INF = 1000000000;
int[][] distance = new int[n+1][n+1];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
    	if (i == j) {
        	distance[i][j] = 0;
        } else {
            distance[i][j] = INF;
        }
    }
}

// ii. 각 노드간의 최단 거리 인접행렬 update
for (int i = 0; i < m; i++) {
	int start = sc.nextInt();
    int end = sc.nextInt();
    int weight = sc.nextInt():
    distance[start][end] = Math.min(distance[start][end], weight);
}

// iii. 3중 for문을 순회하며 인접행렬 update
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
        }
    }
}

 

3중 for문으로 구성되어 있는 iii 번째 코드가 핵심이다.

k	중간 노드
i	출발 노드
j	도착 노드

 

K가 중간 노드인데 왜 가장 첫 번째 for문에 위치한 이유는 중간 노드인 K는 항상 고정되어 있어야 하기 때문이다.

즉, 중간 노드 k를 고정한 상태에서 출발 노드 i와 도착 노드 j에 대해 경로를 확인해야 하기 때문이다.

 

그리고 `i → j`의 거리와 `i → k` + `k → j`거리를 비교하여 더 짧은 거리를 distance 인접 행렬에 update한다.

이는 Floyd Washall 알고리즘의 점화식을 그대로 구현한 것이다. 

 ※ 점화식 : D₁₃ = min(D₁₃, D₁₂ + D₂₃)

 

 

 

 

 

 

---