📌개요
모든 최단 경로를 구하는 알고리즘
다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이었다면, 플로이드워셜 알고리즘은 한 번 실행하여 모든 노드간(모든 정점에서 모든 정점까지의) 최단 경로를 구할 수 있다.
플로이드워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다.거쳐가는 정점을 기준으로 최단 거리를 구하는 것
🙅♂️다익스트라와의 차이
다익스트라는 한 노드에서 다른 특정 노드까지의 최단 경로를 구할 때 사용되고, 플로이드워셜은 모든 노드에서 다른 모든 노드까지의 최단 경로를 구할 때 사용된다.
우선순위큐를 활용하여 구현한 다익스트라의 시간복잡도는 O(ElogV)이다. 이때 V는 노드의 개수, E는 간선의 개수이다.
반면, 플로이드워셜은 시간복잡도가 O(n^3)이다. n번의 탐색동안 n^2번 값을 비교하여 업데이트해준다.
또한, 다익스트라는 그리디 알고리즘인데, 플로이드워셜은 dp를 기반으로 하는 알고리즘이라는 특징이 존재한다.
💁♀️플로이드워셜의 개념
플로이드워셜의 결과는 항상 2차원 배열이다. 모든 노드에서 모든 노드로 가는 최단 경로가 모두 포함된 테이블이 형성되기 때문이다.
우선 2차원 배열을 설정하고, 본인 노드에서 본인 노드로 오는 경우는 0, 또 직접적으로 이어지지 않은 경로에 무한대값을 넣는다.
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 4 | INF | 6 |
| 1 | 3 | 0 | 7 | INF |
| 2 | 5 | INF | 0 | 4 |
| 3 | INF | INF | 2 | 0 |
우선, 0번 노드부터 순차적으로 탐색한다.
이때, 0을 제외하고 출발 노드, 도착 노드 두 개의 노드를 선택한다.
(1->2), (1->3), (2->1), (2->3), (3->1), (3->2)
그럼 (1->2)와 (1->0->2)의 경로 중 더 짧은 경로로 업데이트한다.
이것을 순차적으로 모든 노드에 시행한다.
🔑코드
O(n^3)인 것은 시작노드, 중간 노드, 도착 노드 3개를 다 돌려보기 때문이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
(첫 번째 숫자는 노드의 개수, 두 번째 숫자는 간선의 개수 , N+2~번째 숫자들은 시작 노드 도착 노드 VALUE를 의미한다).
5
8
0 1 5
0 4 1
0 2 7
0 3 2
1 2 3
1 3 6
2 3 10
3 4 4
*/
public class Main {
static int N, M;
static int[][] dist;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
// 플로이드 초기 거리 테이블
dist = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 자기 자신으로 가는 길은 최소 비용이 0
if (i == j) {
dist[i][j] = 0;
continue;
}
// 자기 자신으로 가는 경우를 제외하고는 무한대
dist[i][j] = 100_000_000;
}
}
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
dist[a][b] = Math.min(dist[a][b], cost);
dist[b][a] = Math.min(dist[b][a], cost);
}
// 플로이드 워셜 알고리즘
// 노드를 1개부터 N개까지 거쳐가는 경우를 모두 고려한다.
for (int k = 0; k < N; k++) {//중간 노드
// 노드 i에서 j로 가는 경우.
for (int i = 0; i < N; i++) {//시작 노드
for (int j = 0; j < N; j++) {
//도착 노드
// k번째 노드를 거쳐가는 비용이 기존 비용보다 더 작은 경우 갱신
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
// 출력
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 연결이 안되어 있는 경우
if (dist[i][j] == 100_000_000) {
System.out.print("INF ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
}
}
야호