개요
다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘으로, 네비게이션과 같은 SW에서 많이 사용된다.
다익스트라
특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 그대로 사용한다.
수행 과정
- 출발 노드를 선정한다.
- 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
- 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
- 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.
- 3~4번 과정을 모든 노드를 방문할 때까지 반복한다.
예시
위 그림에서 동그라미 안의 번호는 노드 번호를 의미하며 빨간색 숫자는 노드에서 노드로 가는 비용을 의미한다. 표로 정리하면 다음과 같다.
1행 1열은 1번 노드에서 1번 노드로 가는 비용을 의미하며 그 값은 '0'이다. 1행 2열의 경우는 1번 노드에서 2번 노드로 가는 비용을 의미하며 그 값은 '2'인 방식이다. 1행 4열의 경우 1번 노드에서 4번 노드로 가는 경로가 없어 비용은 'INF'가 된다. 여기서 수행 과정을 진행하면 다음과 같다.
-
1번 노드를 출발 노드로 지정한다.
-
이때 각 노드로 이동하는 최소 비용은 다음과 같다.
-
빨간색은 자기 자신으로 가는 경우를 의미하며 방문한 노드로 취급한다. 따라서 방문하지 않은 노드 중 가장 비용이 적은 노드는 3번 노드와 6번 노드이다. 인덱스가 작은 경우부터 진행한다.
-
1번 노드에서 3번 노드를 거쳐서 다른 노드로 이동할 수 있는 최소 비용을 갱신해야 한다.
2번 노드로 가는 경우, 1+3으로 '4'의 비용이 든다. 하지만, 1번 노드에서 2번 노드로 바로 가는 비용은 '2'로 기존보다 큰 비용이 들기에 갱신을 하지 않는다.
4번 노드로 가는 경우, 1+3인 '4'의 비용이 든다. 1번 노드에서 4번 노드로 바로 가는 경로는 없으므로 '4'의 비용으로 최소 비용을 갱신한다.
5번 노드로 가는 경우, 1+2인 '3'의 비용이 든다. 1번 노드에서 5번 노드로 바로 가는 경로의 비용은 '4'로 최소 비용인 '3'으로 갱신한다.
6번 노드로 가는 경우, 1+2인 '3'의 비용이 든다. 하지만, 1번 노드에서 6번 노드로 바로 가는 경로의 비용은 '1'로 갱신을 하지 않아도 된다.
-
위 과정을 통해 3번 노드를 거치는 모든 경우의 수를 확인했다. 다음 방문하지 않은 노드 중 가장 비용이 적은 노드는 6번 노드로, 3번 노드와 같은 과정을 반복한다.
2번 노드로 가는 경우, 갈 수 있는 경로가 없으므로 갱신하지 않는다.
4번 노드로 가는 경우, 1+2인 '3'의 비용이 든다. 이전에 갱신했던 '4'보다 작으므로 최소 비용을 갱신한다.
5번 노드로 가는 경우, 1+1인 '2'의 비용이 든다. 이전에 갱신했던 '3'보다 작으므로 최소 비용을 갱신한다.
-
다음 방문하지 않은 노드 중 가장 비용이 적은 노드는 2번 노드이다.
4번 노드로 가는 경우, 2+1인 '3'의 비용이 든다. 이전에 갱신했던 '3'과 같으므로 최소 비용을 갱신하지 않는다.
5번 노드로 가는 경우, 갈 수 있는 경로가 없기에 최소 비용을 갱신하지 않는다.
-
다음으로 적은 비용은 5번 노드이다.
4번 노드로 가는 경우, 갈 수 있는 경로가 없기에 최소 비용을 갱신하지 않는다.
-
이렇게 이전까지 구했던 최단 거리 정보를 그대로 사용하며 1번 노드에서 다른 모든 노드로 가는 최소 비용을 갱신했다.
시간 복잡도
위 과정은 선형 탐색 방법으로 시간 복잡도는 O(N^2)이 된다. 하지만, 전체 노드의 갯수가 많고 그 노드를 지나는 경로의 수가 적다면 이 방법은 굉장히 비효율적인 방법이 된다. 조금 더 빠르게 동작하고 싶다면 힙(heap) 구조로 구현하여 시간 복잡도를 O(N x log N)으로 만들 수 있다.
코드 구현
다익스트라를 코드로 구현하면 다음과 같다.
#include <iostream>
int INF = 10000000;
int array[6][6] = {
{0, 2, 1, INF, 4, 1},
{2, 0, 3, 1, INF, INF},
{1, 3, 0, 3, 2, 2},
{INF, 1, 3, 0, INF, 2},
{4, INF, 2, INF, 0, 1},
{1, INF, 2, 2, 1, 0}
};
int getMinIndex(int d[6], int v[6]){
int min{INF}, min_index{0};
for (int i=0; i < 6; i++){
if (min > d[i] && !v[i]){
min = d[i];
min_index = i;
}
}
return min_index;
}
int main(){
int start_node{0}, d[6], v[6]{0}; //d는 시작 노드에서의 최소 비용 배열, v는 방문 여부
v[start_node] = 1;
for (int i=0; i < 6; i++){
d[i] = array[start_node][i];
}
for (int i=0; i < 6 - 2; i++){
int min_index = getMinIndex(d, v);
v[min_index]=1;
for (int j=0; j < 6; j++){
if (d[min_index] + array[min_index][j] < d[j] && !v[j]){
d[j] = d[min_index] + array[min_index][j];
}
}
}
std::cout << "d : ";
for (int i=0; i < 6; i++){
std::cout << d[i] << ' ';
}
return 0;
}
//d : 0 2 1 3 2 1Reference
