최단경로 찾기 - 플로이드 워셜 알고리즘
- Algorithm/Concept
- 2021. 12. 8.
플로이드 워셜 알고리즘 (Floyed-Warshall Algorithm)
플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 사용하는 알고리즘이다.
단계마다 '거쳐가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다. 노드의 개수가 N개일때 알고리즘 상으로 N번의 단계를 수행하며, 단계마다 O(N제곱)의 연산을 통해 '현재 노드를 거쳐가는' 모든 경로를 고려한다. 따라서 플로이드 워셜 알고리즘의 시간복잡도는 O(N3제곱)이다.
모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야하기 때문에 2차원 리스트에 '최단거리' 정보를 저장한다. 플로이드 워셜 알고리즘은 다이나믹 프로그래밍이라는 특징이 있다. 노드의 개수가 N개라고 할대, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문이다.
점화식
각 단계에서는 해당 노드를 거쳐가는 경우를 고려한다.
(예시) 1번 노드
1번 노드를 중간에 거쳐가는 모든 경우를 고려한다. 예를들어, A -> 1번 노드 -> B로 가는 비용을 확인한 후에 최단 거리를 갱신한다. 현재 최단 거리 테이블에 A번 노드에서 B번 노드로 이동하는 비용이 3으로 기록되어 있을 때, A번 노드에서 1번 노드를 거쳐 B번 노드로 이동하는 비용이 2라는 것이 밝혀지면 A번 노드 -> B번 노드의 이동 비용을 2로 갱신하는 것이다.
따라서 알고리즘에서는 현재 확인하고 있는 노드를 제외하고, N - 1 개의 노드 중에서 서로 다른 노드 (A, B)쌍을 선택한다. 이후에 A번 노드 -> 1번 노드 -> B번 노드로 가는 비용을 확인한 뒤에 최단 거리를 갱신한다.
점화식
전체적으로 3중 반복문을 사용하여 이 점화식에 따라 최단 거리 테이블을 갱신하면 된다.
1) A번 노드 -> B번 노드로 가는 최소 비용
2) A번 노드 -> K번 노드 -> B번 노드로 가는 최소 비용
위 2가지를 비교하여 더 작은 값으로 갱신하겠다는 의미이다.
동작원리
아래 그래프를 예시로, 플로이드 워셜 알고리즘의 동작 원리를 이해해보자.
이런 그래프가 있을때, 최소 비용을 담는 2차원 배열을 아래와 같이 초기화할 수 있다.
우선 A번 노드 -> B노드 노드 로 가는 경로로 값이 셋팅된 모습이다. 출발이 행, 도착이 열이다.
[Step1] 1번 노드를 거쳐가는 경우 탐색
D23 점화식을 이해해보자.
1) 기존의 2번 노드 -> 3번 노드로 가는 비용
2) 2번 노드 -> 1번 노드 -> 3번 노드로 가는 비용
위 2가지 중 더 작은 값으로 갱신해주겠다는 의미다.
[Step2] 2번 노드를 거쳐가는 경우 탐색
[Step3] 3번 노드를 거쳐가는 경우 탐색
[Step3] 4번 노드를 거쳐가는 경우 탐색
최종 결과
예를들어, D13을 보면 1번 노드 -> 3번 노드로 가는 최단거리가 8이라는 의미로 해석하면 된다.
구현코드
package Y19_ShortestPath.floyedwarshall;
import java.util.Arrays;
import java.util.Scanner;
public class FloyedWarshall {
/* 무한을 의미 */
public static final int INF = (int) 1e9;
/* 노드의 개수 */
public static int n;
/* 간선의 개수 */
public static int m;
/* 2차원 배열(그래프 표현)를 만들기 */
public static int[][] graph = new int[501][501];
public static void main(String[] args) {
input();
/* 점화식에 따라 플로이드 워셜 알고리즘을 수행 */
for (int k = 1; k <= n; k++) {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
/* 수행된 결과를 출력 */
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (graph[a][b] == INF) { /* 도달할 수 없는 경우, 무한(INFINITY)이라고 출력 */
System.out.print("INFINITY ");
} else { /* 도달할 수 있는 경우 거리를 출력 */
System.out.print(graph[a][b] + " ");
}
}
System.out.println();
}
}
private static void input() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
/* 최단 거리 테이블을 모두 무한으로 초기화 */
for (int i = 0; i < 501; i++) {
Arrays.fill(graph[i], INF);
}
/* 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 */
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (a == b) graph[a][b] = 0;
}
}
/* 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화 */
for (int i = 0; i < m; i++) {
// A에서 B로 가는 비용은 C라고 설정
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
graph[a][b] = c;
}
}
}
위 점화식은 아래의 코드로 구현되었다.
/* 점화식에 따라 플로이드 워셜 알고리즘을 수행 */
for (int k = 1; k <= n; k++) {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
참고 도서 : 이것이 코딩테스트다
'Algorithm > Concept' 카테고리의 다른 글
| 최소 신장트리 알고리즘, 크루스칼 알고리즘 (Kruskal) (0) | 2021.12.15 |
|---|---|
| 서로소 집합 (Disjoint Sets) 알고리즘 (0) | 2021.12.15 |
| 우선순위 큐 (Priority Queue) (0) | 2021.12.03 |
| 최단 경로 알고리즘 - 다익스트라 알고리즘 우선순위 큐 사용 버전 (2) | 2021.12.03 |
| 최단 경로 알고리즘 - 다익스트라 알고리즘 기본 버전 (0) | 2021.12.03 |