최단경로 알고리즘
플로이드 워셜
- 그래프 내에서 최단경로를 찾는 알고리즘
- 일반적으로, 모든 정점으로부터 다른 모든 정점으로의 최단경로를 구하는데 사용된다
- 음수인 가중치를 가진 경로가 존재하더라도 사용할 수 있다
- 3중 반복문을 이용하여 구현
- 구현 원리 : 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용
- 즉, 기존까지 계산된 s -> e 경로에서, 중간지점 m을 거쳐가는 것이 더 빠른지 확인하고 최단경로로써 활용하는 것으로 해석할 수 있다
구현 방법
3중 반복문을 통해 구현한다. 알고리즘 또한 4줄이면 끝날 정도로 매우 간단한 것이 장점이라고 할 수 있다.
다만 어떤 정점을 기준으로 반복문을 설정할지에 따라 알고리즘의 진행이 결정된다. 항상 중간지점 m을 반복문의 가장 위에 배치할 것. 정석은 ‘중간지점 -> 시작점 -> 도착점’ 순이다.
반복문의 의미는 가장 위의 반복문에서 알 수 있다. 2번째와 3번째 반복문인 시작점에서 도착점까지 가기 위해, 1번째 반복문인 “1부터 k까지의 정점을 경유지점으로 하여 최단경로를 구할 수 있는가?” 에 대한 대답을 하는 것이라고 이해하면 된다. 즉 이것이 모든 정점에 대하여 돌게 되면 모든 정점에서 모든 정점으로 모든 정점을 경유점으로 하여 최단경로를 구할 수 있냐는 문제로 바뀌게 되며, 이것이 우리가 원하는 최단경로를 찾는 방법이다.
구현 예시
1
2
3
4
5
6
7
for (int k = 1; k <= N; ++k) {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
다익스트라
- 그래프 내에서 최단경로를 찾는 알고리즘 - 일반적으로, 시작지점이 정해져있는 경우 유용하게 사용 가능하다 ( 시작점으로부터 다른 모든 정점들로의 최단경로를 구할 수 있음 ) - 조건 : 모든 경로의 가중치는 nonnegative해야한다 ( 음수가 있으면 안됨 )
- DP를 이용하여 구현 - 구현 원리 : s -> e까지의 최단거리는 “거쳐가는 다른 정점들간의 최단거리” 의 합으로 계산되기 때문 - 즉, 하나의 최단거리를 구할 때, 이전에 계산해둔 최단거리 정보를 그대로 사용하기 때문에, dp문제로 해석할 수 있다
구현 방법
위에서 얘기했다시피 DP를 이용하여 구현한다. dp 작동 원리는 거쳐가는 다른 정점들간의 최단거리의 합으로도 최단거리를 표현할 수 있기 때문. 그래서 시작점으로부터 다른 모든 정점들로의 최단거리를 기록해두도록 구현해야한다. 간선은 음수의 가중치를 가질 수 없으므로, 간선을 지난다면 항상 거리가 줄어들지는 않는다. 그래서 지금까지의 거리가 가장 짧은 정점을 골라 그곳에서부터 갈 수 있는 다른 정점들을 탐색하면서 알고리즘이 진행된다. 이 때 선택된 정점은 더 이상 최단거리를 찾을 수 없으므로 최단거리가 고정된다.
최단거리를 갱신하기 위해 사용되는 수식은 아래와 같다.
\[\text{dist}[j] = \min{ (\text{dist}[j], \text{dist}[i] + \text{path}[i][j]) }\]최단거리는, 지금까지 계산한 최단거리와 다른 정점을 거쳐갈 때의 거리를 비교하여 계산한다. 지금까지 계산한 최단거리가 실제로 최단거리인가? 다른 정점을 거쳐가는게 오히려 빠르지 않을까? 그 물음을 계속해서 반복해나간다고 생각하면 편하다.
시나리오 예시
시나리오에서 사용할 그래프 예시이다. 총 5개의 정점이 있고 각각 A, B, C, D, E로 라벨링되어있다. 간선들은 방향이 있고, 각각의 가중치는 음수가 아닌 정수로 되어있다. 이것을 matrix로 표현하면 아래와 같다. (본인으로 향하는 간선은 존재하지 않는다고 가정한다)
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | - | 10 | 3 | - | - |
| B | - | - | 1 | 2 | - |
| C | - | 4 | - | 8 | 2 |
| D | - | - | - | - | 7 |
| E | - | - | - | 9 | - |
시나리오 절차
먼저 다익스트라 알고리즘의 시작점을 정해야한다. 문제를 풀다보면 조건에 의해 시작점을 임의로 정해야하는 경우도 있다. 이 예시에서는 A가 시작지점이라고 생각해보자.
지금까지의 최단거리를 기록할 배열을 하나 만들도록 하자. 시작지점의 최단거리는 0일 것이고, 다른 정점들로의 최단거리는, 아직 경로를 탐색하지 못했으므로 ‘경로 없음’을 나타내야한다. 일반적으로 INF값을 두어 경로가 존재하지 않는다고 표현한다. 예시로 보면 아래와 같다.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| dist | 0 | INF | INF | INF | INF |
그리고, 이 dist 값들 중에서 최솟값을 가진 정점을 선택해야한다. 이유는, 그 정점으로부터 출발하는 간선을 통해 다른 정점으로 이동하고, 그 거리가 최단거리인지 계속해서 갱신할 예정인데, 간선의 가중치가 음수가 아니기 때문에, 현재 정점들 중 dist값이 최소라면 그 정점으로의 최단거리가 dist라는 의미를 가지기 때문이다.
선택 : A 정점
dist값들 중 최솟값($0$) 을 가진 정점 A가 선택되었다. A로의 최단거리는 0으로 정해진 것. 이후 A를 거쳐서 다른 정점으로 갈 때, 그 거리가 최단거리가 될 수 있는지 판단해야한다. matrix에 의해, A에서 갈 수 있는 정점은 B와 C다. B와 C에서는 각각 현재까지의 최단거리와 A를 거쳐갈 때의 최단거리를 비교하게 된다. 그럴 때의 dist 배열은 아래와 같이 변화한다.
\[\begin{align} \text{dist}[B] &= \min{ (\text{dist}[B], \text{dist}[A] + \text{matrix}[A][B]) } = 10\\ \text{dist}[C] &= \min{ (\text{dist}[C], \text{dist}[A] + \text{matrix}[A][C]) } = 3 \end{align}\]| A | B | C | D | E | |
|---|---|---|---|---|---|
| dist | 0 | 10 | 3 | INF | INF |
dist 배열을 계산한 이후, 다음으로 선택할 정점을 골라야한다. A는 이미 선택되었으므로 제외하고, 가능한 것은 B, C (경로가 없다면 선택할 이유가 없다)
선택 : C 정점
선택되지 않은 dist값들 중 최솟값($3$) 을 가진 정점 C가 선택되었다. C로의 최단거리는 3으로 정해진 것. 이후 C를 거쳐서 다른 정점으로 갈 때, 그 거리가 최단거리가 될 수 있는지 판단해야한다. matrix에 의해, C에서 갈 수 있는 정점은 B, D, E다. 모든 정점에서 각각 현재까지의 최단거리와 C를 거쳐갈 때의 최단거리를 비교할 수 있다. 그럴 때의 dist 배열은 아래와 같이 변화한다.
\[\begin{align} \text{dist}[B] &= \min{ (\text{dist}[B], \text{dist}[C] + \text{matrix}[C][B]) } = 7\\ \text{dist}[D] &= \min{ (\text{dist}[D], \text{dist}[C] + \text{matrix}[C][D]) } = 11\\ \text{dist}[E] &= \min{ (\text{dist}[E], \text{dist}[C] + \text{matrix}[C][E]) } = 5 \end{align}\]| A | B | C | D | E | |
|---|---|---|---|---|---|
| dist | 0 | 7 | 3 | 11 | 5 |
이제는 이전의 절차를 계속해서 반복하며, 선택되지 않은 정점이 남지 않을 때까지 반복한다.
최종 결과
모든 정점을 선택한 이후 dist 배열은 아래와 같이 계산된다.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| dist | 0 | 7 | 3 | 9 | 5 |
구현 예시
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
void dijkstra(int start_point) {
/* dist init */
for (int i = 1; i <= n; ++i) {
if (i == start_point) {
dist[i] = 0;
} else {
dist[i] = INF;
}
visit[start_point] = false;
}
/* loop until all vertex were choosed */
int current_vertex;
while (true) {
current_vertex = 0;
for (int i = 1; i <= n; ++i) {
if (visit[i] == false && dist[i] < dist[current_vertex]) {
current_vertex = i;
}
}
if (current_vertex == 0) { // no more vertex left
break;
}
visit[current_vertex] = true;
/* modify all dist values */
for (int i = 1; i <= n; ++i) {
if (path[current_vertex][i] < INF) {
if (dist[i] > dist[current_vertex] + path[current_vertex][i]) {
dist[i] = dist[current_vertex] + path[current_vertex][i];
}
}
}
}
return;
}
개선점
grid 표기 방법
정점의 개수가 적을 때에는 인접 행렬 방법으로 간선을 기록해도 메모리나 시간상 문제가 생기지는 않는다. 하지만 정점의 개수가 많아지면 인접 행렬로 그래프를 표현하기에는 시간, 메모리 문제가 발생한다.
인접 행렬을 인접 리스트 방식으로 구현하는 방법이 있다. 인접행렬에서 인접리스트로 바꾸면 이점이 많다.
- 칸의 크기를 줄일 수 있다. 정점이 $N$개라면 인접행렬은 $N^2$개의 칸이 필요하다. 인접리스트는 간선의 개수 $E$개만큼 칸이 필요하다. 하지만 리스트의 head를 따로 저장해야하고, 리스트의 칸은 일반 배열의 칸보다 더 많은 변수(next 등) 를 기록해야하므로, 실질적으로 메모리 이득을 보기 위해서는 $E \times 2 < N$인 경우일 것. 그래도 $N$이 크다면 인접 리스트를 고려해야한다
- dist 배열을 modify할 때 탐색 횟수를 줄일 수 있다. 시간복잡도가 크게 향상되는 부분 중 하나. 위의 시나리오에서는 A를 선택했을 때 B, C, D, E를 모두 확인하며 간선이 있는지 확인했지만, 인접리스트로 구현한다면 A와 연결되어있는 정점들을 한눈에 확인 가능하다
우선순위 큐 구현
매 반복마다 dist값이 최소인 정점을 찾기 위해서, 우리는 모든 정점에 대해 반복하며 ‘방문하지 않았으면서 dist가 최소인 정점’을 찾았다. 이것은 불필요한 visit 배열을 만들게 시키고, 매 반복마다 정점을 매번 확인하도록 강요한다.
dist값에 대한 우선순위 큐를 만들게 되면 매 반복마다 $O(N)$이었던 최소정점 찾기가 $O(\log N)$으로 줄어들 수 있다. 이 부분 또한 시간복잡도를 매우 크게 줄일 수 있는 부분.
개선안
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
void dijkstra(int s) {
for (int i = 1; i <= n; ++i) {
if (i == s) {
ret[i] = 0;
} else {
ret[i] = INF;
}
push((ND){i, ret[i]});
}
while (top > 0) {
ND cur = pop();
if (cur.dist <= ret[cur.idx]) {
for (int i = 1; i <= n; ++i) {
if (grid[cur.idx][i] < INF) {
if (ret[i] > cur.dist + grid[cur.idx][i]) {
ret[i] = cur.dist + grid[cur.idx][i];
push((ND){i, ret[i]});
}
}
}
}
}
return;
}