최단경로탐색 - 다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘

다익스트라 알고리즘은 대표적인 최단 경로 탐색 알고리즘이다.

다익스트라 알고리즘의 작동 방식은 다음과 같다

 

1. 출발 노드를 설정

2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택

4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려해 최소 비용을 갱신

5. 3~4 반복

 

좀 더 이해를 돕기 위해 그림으로 예를 들어보자.

이를 구현한 코드는 아래와 같다.

 

#include <stdio.h>
 
int number = 6;
#define INF 100000000
 
int a[6][6] = {
    {0,2,5,1,INF,INF},
    {2,0,3,2,INF,INF},
    {5,3,0,3,1,5},
    {1,2,3,0,1,INF},
    {INF,INF,1,1,0,2},
    {INF,INF,5,INF,2,0}
};
int visited[6];
int distance[6]; //최단거리
 
//가장 최소 거리를 가지는 정점을 반환
int getSmallIndex() {
    int min = INF;
    int index = 0;
    for (int i = 0;i < number;i++) {
        if (distance[i] < min && !visited[i]) {
            min = distance[i];
            index = i;
        }
    }
    return index;
}
 
//다익스트라 수행 (선형탐색 / O(N*N) )... 시간초과.....
void dijkstra(int start) {
    for (int i = 0;i < number;i++)
        distance[i] = a[start][i];
    visited[start] = 1;
    for (int i = 0;i < number - 2;i++) {
        int current = getSmallIndex();
        visited[current] = 1;
        for (int j = 0;j < 6;j++) {
            if (!visited[j])
                if (distance[current] + a[current][j] < distance[j])
                    distance[j] = distance[current] + a[current][j];
        }
    }
}
 
int main() {
    dijkstra(0);
    for (int i = 0;i < number;i++)
        printf("%d ", distance[i]);
    return 0;
}

 

그런데, 이 코드는 최소 비용을 선형 탐색으로 찾기 때문에, O(N*N)이라는 시간 복잡도를 가지게 된다. 이 경우, 정점의 갯수에 비해 간선의 수가 현저히 적을 때 치명적으로 비효율적일 수 있다.

 

그럼 좀 더 효율적인 코드를 살펴보자. 아래의 코드는 힙구조를 사용하여 가장 비용이 적은 노드를 선형 탐색을 사용하지 않고 바로 찾도록 한다. 아래 코드는 인접 리스트 방식을 활용하여 구현한 것이다. 이 경우에는 시간 복잡도가 O(N*logN)이다.

 

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n = 6;
int INF = 10000000000;
 
vector<pair<int, int>>a[7];
int d[7];
 
//인접리스트 사용 (O(N*logN))
void dijkstra(int start) {
    d[start] = 0;
    priority_queue<pair<int, int>>pq;//힙구조
    pq.push(make_pair(start, 0));
    //가까운 순서대로 처리하므로 큐를 사용,,
    while (!pq.empty()) {
        int current = pq.top().first;
        // 짧은 것이 먼저 오도록 음수화
        int distance = -pq.top().second; //거리에 마이너스 붙여줌.. -> 최소힙처럼 만들기
        pq.pop();
        //최단 거리가 아닌 경우 스킵
        if (d[current] < distance) continue;
        for (int i = 0;i < a[current].size();i++) {
            //선택된 노드의 인접 노드
            int next = a[current][i].first;
            //선택된 노드를 거쳐서 인접 노드로 가는 비용
            int nextDistance = distance + a[current][i].second;
            //기존의 최소 비용보다 더 적으면 교체
            if (nextDistance < d[next]) {
                d[next] = nextDistance;
                pq.push(make_pair(next, -nextDistance));
            }
        }
    }
}
 
int main() {
    for (int i = 1;i <= n;i++) {
        d[i] = INF;
    }
    a[1].push_back(make_pair(2, 2));
    a[1].push_back(make_pair(3, 5));
    a[1].push_back(make_pair(4, 1));
 
    a[2].push_back(make_pair(1, 2));
    a[2].push_back(make_pair(3, 3));
    a[2].push_back(make_pair(4, 2));
 
    a[3].push_back(make_pair(1, 5));
    a[3].push_back(make_pair(2, 3));
    a[3].push_back(make_pair(4, 3));
    a[3].push_back(make_pair(5, 1));
    a[3].push_back(make_pair(6, 5));
 
    a[4].push_back(make_pair(1, 1));
    a[4].push_back(make_pair(2, 2));
    a[4].push_back(make_pair(3, 3));
    a[4].push_back(make_pair(5, 1));
 
    a[5].push_back(make_pair(3, 1));
    a[5].push_back(make_pair(4, 1));
    a[5].push_back(make_pair(6, 2));
 
    a[6].push_back(make_pair(3, 5));
    a[6].push_back(make_pair(5, 2));
 
    dijkstra(1);
 
    for (int i = 1;i < n;i++)
        printf("%d ", d[i]);
}