다익스트라 심화 - 플로이드 워셜(Floyd-Warshall)
Posted
By ROOT
7 min read
다익스트라의 한계
다익스트라(Dijkstra) 알고리즘 벨만 포드(Bellman-Ford) 알고리즘
이전 포스팅에서 다익스트라는 음수 가중치를 고려할 수 없다는 한계를 극복하기 위해 벨만 포드 알고리즘을 다뤘었다.
이외에 또다른 한계를 알아보자.
- 다익스트라는 하나의 점에서 모든 지점까지의 최단 경로를 구하는 알고리즘이다.
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하려면 어떻게 해야 할까?
[다익스트라 n번]
- 모든 지점에서 다익스트라를 사용하여 구할 수 있다.
- 그러나 이 경우, 음수 가중치가 고려되지 않을 것이다.
[벨만포드 n번]
- 모든 지점에서 벨만 포드를 사용하여 구할 수 있다.
- 이 경우, 간선 수가 희소한 경우에는 더 효과적일 수 있다.
- 하지만 구현 관점에서 플로이드 워셜이 더 간단하다.
[알고리즘 비교]
| Dijkstra | Bellman-Ford | Floyd-Warshall | |
|---|---|---|---|
| 시간 복잡도 | O(V^2) (Array) O(Elog(V)) (Heap) | O(V * E) | O(V^3) |
| 공간 복잡도 | O(V) | O(V) | O(V^2) |
| 특징 | 하나의 노드에서부터 모든 노드의 최단 경로를 구함 음수 가중치를 고려하지 못함 | 하나의 노드에서부터 모든 노드의 최단 경로를 구함 음수 가중치를 고려할 수 있음 | 모든 노드에서부터 모든 노드의 최단 경로를 구함 음수 가중치를 고려할 수 있음 |
플로이드 워셜(Floyd-Warshall) 알고리즘
- 플로이드 워셜은 모든 지점에서 모든 지점까지의 최단 경로를 구하면서 음수 가중치도 고려할 수 있다.
- 구현이 간단하다.
플로이드 워셜 로직
- 그래프의 인접 행렬(최단 거리 행렬)을 초기화한다.
- i에서 j로의 직접적인 간선이 존재하면 해당 가중치로 초기화한다.
- 자기 자신으로의 거리는 0으로 초기화한다.
- 이외에는 무한대로 초기화한다.
자바에서는 적당히 10억 정도로 초기화한다. 그래야 MAX와 계산했을 때 오버플로우가 발생하지 않기 때문이다.
삼중 for문을 수행한다. (i -> j -> k)- 가장 바깥쪽 for문 i는 경유지를 의미한다.
- j에서 k로 가는 경로를 기존 경로와 j -> i + i -> k 경로를 비교하여 더 작은 값으로 업데이트 한다.
- 음수 사이클을 확인하고 싶다면, 대각선 원소인
dis[i][i]를 확인한다.- 음수라면, 음수 사이클이 존재한다.
플로이드 워셜 로직
아무래도 시간복잡도가
O(V^3)인 만큼 경우의 수가 너무 많다보니 자세히 다루지는 않겠다.
아래 gif는 A - B - C - D - E 순서대로 경유지를 설정하여 그래프가 업데이트 되는 모습을 보여준다.
출처
BOJ 1613 - 역사 (골드 3)
- 플로이드 워셜을 사용한다.
- 최단 거리를 구하는 것이 아닌 사건들의 전후 관계를 나타나기 위해 해당 경로가 있다는 것만 나타내면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.io.*;
import java.util.*;
public class Main {
static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();
static int n;
static int k;
static int[][] table;
public static void main(String[] args) {
input();
}
static void input() {
n = scan.nextInt();
k = scan.nextInt();
table = new int[n + 1][n + 1];
for (int i = 0; i < k; i++) {
int from = scan.nextInt();
int to = scan.nextInt();
table[from][to] = 1;
}
solve();
int s = scan.nextInt();
for (int i = 0; i < s; i++) {
int front = scan.nextInt();
int back = scan.nextInt();
if (table[front][back] == 1) {
sb.append(-1).append("\n");
} else if (table[back][front] == 1) {
sb.append(1).append("\n");
} else {
sb.append(0).append("\n");
}
}
System.out.println(sb);
}
static void solve() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (table[j][k] == 0 && table[j][i] == 1 && table[i][k] == 1) {
table[j][k] = 1;
}
}
}
}
}
static class FastReader {
.
.
.
}
}
FastReader
플로이드 워셜을 사용하는 문제 리스트
플로이드 워셜을 풀다보면 특징이 보인다.
시간 복잡도가 세제곱이나 되기 때문에 정점의 개수가 1000개 이하로 주어진다.
이 점을 기억하면 코테에서도 쉽게 유형을 파악할 수 있을 것이다.
누군가가 물어본다면
플로이드 워셜은 모든 정점에서 모든 정점의 최단 경로를 구하는 알고리즘입니다.
벨만 포드와 마찬가지로 음수 가중치를 고려할 수 있고, 음수 사이클 존재를 판별할 수 있습니다.
또한 구현이 간단하다는 장점이 있습니다.
This post is licensed under CC BY 4.0 by the author.