최단경로 알고리즘은 플로이드 알고리즘과 다익스트라 알고리즘이 가장 대표적인 두 알고리즘이다.
다익스트라 알고리즘은 출발지가 주어졌을 때 그 출발지(one)로부터 모든 지점(all)으로 가는 최단 경로를 구하는 one-to-all 알고리즘이고 시간복잡도는 O(n^2)이다.
반면 플로이드 알고리즘은 그래프 상의 정점들의 모든 쌍에 대해서 그 두 점 사이의 최단경로 값을 다 구하는 알고리즘이다. 따라서 모든 출발지에서 모든 도착지로의 최단 경로를 구하는 all-to-all 알고리즘이고 시간복잡도는 O(n^3)이다.
정점이 n개인 그래프에서 다익스트라 알고리즘은 출발점이 한 개라면 플로이드 알고리즘은 출발점이 n개이다.
그렇기 때문에 당연히 플로이드 알고리즘이 시간복잡도가 높을 수밖에 없고 현실에서 플로이드 알고리즘보다 다익스트라 알고리즘을 더 많이 쓰는 이유가 바로 그것이다. 현실에서 필요할 것 같은 일 보다도 과하게 한꺼번에 일을 많이 하는 셈이다.
플로이드 알고리즘은 동적계획법으로 풀 수 있다.
다음 그래프를 가지고 풀어보자.
방법은 다음과 같다.
1. 어떠한 정점도 경유를 허용하지 않고 Vi에서 Vj로 가는 최단거리를 구해서 D0에 저장한다.
D0이라는 것은 아무 정점도 허용하지 않는다는 뜻이다.
이 그래프를 표현한 자료구조인 인접행렬은 정점 v1에서 v2 사이에 이음선이 있으면 그 가중치가 써있고 아니라면 무한대가 써있다. 즉, 어떠한 정점도 경유를 허용하지 않고 v1에서 v2로 가는 최단경로이다.
따라서 D0은 인접행렬 W와 같다. (Vi와 Vj 사이에 이음선이 없는 경우 INF(무한대)로 표기했다.)
W[i][j] 1 2 3 4 5
1 0 1 INF 1 5
2 9 0 3 2 INF
3 INF INF 0 4 INF = D0
4 INF INF 2 0 3
5 3 INF INF INF 0
2. V1만 경유할 수 있도록 허용했을 때 Vi에서 Vj로 가는 최단거리를 구해서 D1에 저장한다.
D1에서 1이란 V1까지 경유 가능하다는 뜻이다.
이전 단계에서는 아무 정점도 거치지 않고 Vi에서 Vj로 가는 최단경로였는데 이제 경유할 수 있는 정점이 한 개가 더 허용된 것이다.
이제 동적계획법의 특징인 이전 단계에서 구해놓은 것을 이용해야 한다.
허용된 정점이 하나 더 늘어난 것인데 그 추가로 허용된 정점을 Vk라고 하자.
이 경우 두 가지 경우가 발생한다.
첫번째 경우는 정점 k가 추가로 허용되었지만 Vk를 거치지 않고 이전단계에서처럼 Vi에서 Vj로 바로 가는 것이 더 이득인 경우이고
두 번째 경우는 Vk를 거쳐서 가는 덕분에 더 가중치가 적은 경로(최단경로)가 새로 발견되는 경우이다.
만약 Vi와 Vj를 바로 잇는 이음선이 없어서 Vi에서 Vj로 가는 경로가 존재하지 않아 D0에서 D0[i][j]는 무한대(INF)였는데 k를 경우하는 덕분에 Vi에서 Vj로 가는 경로가 생기는 경우는 두 번째 경우이다.
V5에서 V2로 가는 경우를 생각해보자.
V5와 V2를 바로 잇는 이음선이 없기 때문에 D0[5][2]는 무한대(INF)였다. 하지만 D1에서 V1을 경유하는 것을 허용하면 V5에서 V1을 경유해서 V2로 갈 수가 있다. 새로운 최단 경로가 발견되는 것이다.
따라서 D1[5][2]는 D0[5][1]+D[1][2] = 3+1=4가 된다.
첫 번째 경우는 D0[i][j]으로, 두 번째 경우는 D0[i][k] + D0[k][j]으로 표현할 수 있다.
즉 D1[i][j] = minimum(D0[i][j], D0[i][1]+D0[1][j])이다.
D1[i][j] 1 2 3 4 5
1 0 1 INF 1 5
2 9 0 3 2 14
3 INF INF 0 4 INF
4 INF INF 2 0 3
5 3 4 INF 4 0
3. V1, V2만 경유할 수 있도록 허용했을 때 (V2를 추가로 허용했을 때) Vi에서 Vj로 가는 최단거리를 구해서 D2에 저장한다.
D2에서 1이란 V2까지 경유 가능하다는 뜻이다.
이전 단계보다 경유할 수 있는 점이 V2 한 개가 더 허용된 것이다.
V2가 허용됨으로서 V1에서 V3으로 갈 수 있는 경로가 없었는데 4의 비용으로 갈 수 있게 되었고 V5에서 V3도 경로가 없었는데 7의 비용으로 갈 수 있는 경로도 생겼다.
이번에도 D2[i][j] = minimum(D1[i][j], D1[i][2]+D1[2][j])을 이용해 D2 배열을 채운다.
D2[i][j] 1 2 3 4 5
1 0 1 4 1 5
2 9 0 3 2 14
3 INF INF 0 4 INF
4 INF INF 2 0 3
5 3 4 7 4 0
4. V1, V2, V3만 경유할 수 있도록 허용했을 때 (V3을 추가로 허용했을 때)Vi에서 Vj로 가는 최단거리를 구해서 D3에 저장한다.
안타깝게도 이번 경우는 V3을 추가한다고 더 짧은 경로가 발견되는 경우는 없었다.
따라서 D3[i][j] = minimum(D2[i][j], D2[i][3]+D2[3][j]) 이긴 하지만 모두 첫 번째 경우에 해당하므로
이번 경우는 D3[i][j] = D2[i][j]가 된다.
D3[i][j] 1 2 3 4 5
1 0 1 4 1 5
2 9 0 3 2 14
3 INF INF 0 4 INF
4 INF INF 2 0 3
5 3 4 7 4 0
5. V1, V2, V3, V4만 경유할 수 있도록 허용했을 때 (V4를 추가로 허용했을 때) Vi에서 Vj로 가는 최단거리를 구해서 D4에 저장한다.
이번에는 V4를 추가함으로서 새로 발견되는 최단 경로가 많다.
이전 단계에서는 V2에서 V5로 가는 경로는 14의 비용이 들었는데 V4를 거침으로서 5로 줄어들었고
V5에서 V3으로 가는 경로의 비용도 7에서 6으로 줄어들었다.
그 계산은 각각 D4[2][5]=D3[2][4]+D3[4][5], D4[5][3]=D3[5][4]+D3[4][3] 이렇게 한 것이다.
이외에도 최단경로가 많이 갱신되었다.
갱신 방법은 D4[i][j] = minimum(D3[i][j], D3[i][4]+D3[4][j])
D4[i][j] 1 2 3 4 5
1 0 1 3 1 4
2 9 0 3 2 5
3 INF INF 0 4 7
4 INF INF 2 0 3
5 3 4 6 4 0
6. V1, V2, V3, V4, V5 즉, 모든 정점의 경유를 허용했을 때 (V5를 추가로 허용했을 때) Vi에서 Vj로 가는 최단거리를 구해서 D5에 저장한다. (이것이 우리가 구하고자 하는 궁극적인 정답인 배열 D이다.)
V5를 추가로 허용했을 때의 경로의 가중치를 D5에 저장한다.
D5[i][j] = minimum(D4[i][j], D[i][5]+D[5][j])
D5[i][j] 1 2 3 4 5
1 0 1 3 1 4
2 8 0 3 2 5
3 10 11 0 4 7
4 6 7 2 0 3
5 3 4 6 4 0이것이 플로이드 알고리즘의 답이다. 모든 정점에 대해서 Vi에서 Vj로 가는 경로의 길이(또는 비용)가 구해진 것이다.
D5[i][j]에 저장된 값은 정점 Vi에서 정점 Vj로 가는 최단 경로의 거리(비용)이다.
정답을 구하는 과정을 보면 이전 단계에서 구해놓은 것들의 단순 비교(대소비교)만으로 이번 단계의 해답을 구할 수 있었다.
Dk[i][j] = min(Dk-1[i][j], Dk-1[i][k]+Dk-1[k][j]) 이렇게 k번째 단계의 해답은 k-1번째에서 구해놓은 것들의 비교로 구했다.
이 그림에서 지금까지 발견된 경로인 Vi에서 Vj로 가는 경로와 새로 발견되는 경로인 Vi에서 Vk로 가는 경로+Vk에서 Vj로 가는 경로 중 어느 경로로 가야 비용이 적은지를 매 단계마다 선택하는 것이다.
여기에서 주목할 것은 두 개의 부분 경로 즉, Vi에서 Vk로 가는 경로, Vk에서 Vj로 가는 경로는
V1에서 Vk-1까지의 정점만 경유를 허용했을 때의 최단경로이다.
이것은 다 구하고 나서 전체를 보니 이런 사실들이 보이는 것이고 우리는 이것을 동적 계획법을 이용해서 아주 작은 문제부터 시작해서 큰 문제를 해결하는 상향식으로 푼 것이다.
그럼 이제 코드로 구현해보자.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
const int INF = 1000000; //이음선의 가중치로 나올 수 없는 아주 큰 값
int d[5][5] = { {0, 1, INF, 1, 5},
{9, 0, 3, 2, INF},
{INF, INF, 0, 4, INF},
{INF, INF, 2, 0, 3},
{3, INF, INF, INF, 0} };
for (int k = 0; k < 5; k++) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cout << d[i][j] << " ";
}
cout << endl;
}
return 0;
}3중 for문이 있는 것으로 봐서 시간복잡도가 O(n^3)이 될 것이라는 것을 추측해볼 수 있다.
우리는 D0(인접행렬 W)부터 D5까지 6개의 배열을 사용했는데 코드를 보니 이차원 배열 D 하나를 썼다. 심지어 인접행렬 W와 D 이렇게 두 개를 쓰지도 않았다. D는 인접행렬이었는데 거기에 덮어쓰면서 배열 한 개로 해결하고 있다.
이렇게 덮어써도 아무런 문제가 없을까?
그렇다.
왜냐하면 Dk를 구할 때에는 k행 k열은 변하지 않기 때문이다.
직접 해보는 것이 이해하는 데에 가장 확실한 방법이라고 생각한다. 나도 처음에 플로이드 알고리즘 자체를 이해하는 것은 어렵지 않았지만 D 배열 하나에 계속 덮어쓰는 것이 과연 괜찮을까? 하는 의문이 계속 들었었다.
교수님께서 꼭 손으로 따라가보라고 하셔서 직접 공책에 그래프를 그리고 D0부터 D5까지의 행렬을 직접 손으로 써서 구해보니 왜 D 배열 하나만으로 해결가능한지 확실히 이해가 잘 되었고 다시는 플로이드 알고리즘을 잊지 않을 것 같다.
이해가 가지 않는다면 직접 손으로 배열을 하나하나 따라가면서 구해보는 것을 추천한다.
이 그림에서 지금까지 발견된 경로인 Vi에서 Vj로 가는 경로와 새로 발견되는 경로인 Vi에서 Vk로 가는 경로+Vk에서 Vj로 가는 경로 중 어느 경로로 가야 비용이 적은지를 매 단계마다 선택하는 것이다.
여기에서 주목할 것은 두 개의 부분 경로 즉, Vi에서 Vk로 가는 경로, Vk에서 Vj로 가는 경로는
V1에서 Vk-1까지의 정점만 경유를 허용했을 때의 최단경로이다.
이것은 다 구하고 나서 전체를 보니 이런 사실들이 보이는 것이고 우리는 이것을 동적 계획법을 이용해서 아주 작은 문제부터 시작해서 큰 문제를 해결하는 상향식으로 푼 것이다.
※이렇게 작업할 때에는 화질이 선명한데 저장만 하면 왜 이렇게 화질이 깨지는지 모르겠다...
'알고리즘' 카테고리의 다른 글
| [알고리즘] 조합 (Combination) (0) | 2020.01.06 |
|---|---|
| [알고리즘] 순열 (Permutation) (0) | 2020.01.06 |