[C++] 최단 거리를 구하는 다익스트라( Dijkstra ) 알고리즘

다익스트라( Dijkstra ) 알고리즘 소개

다익스트라 알고리즘은 출발 노드로부터, 도달이 가능한 모든 노드까지의 최단 거리들을 한 번에 계산하는 알고리즘입니다.

이 알고리즘은 그래프에 음수 가중치의 순환 경로가 존재하는 경우, 최단 거리를 구하지 못하는 제약이 있습니다.

 

시간 복잡도

V: 노드의 수, E: 간선의 수일 때,

이 알고리즘의 시간 복잡도는 O( E logV )입니다.

 

알고리즘의 실행 과정

이 알고리즘의 실행 과정은 다음과 같습니다.

 

1. 출발 노드의 최단 거리를 0으로 설정합니다.

    그리고, 나머지 노드들은 최대 값( ∞ )의 최단 거리를 가진 것으로 설정합니다.

 

2. 현재, 최단 거리를 가진 노드를 선택합니다.

 

3. 선택된 노드에 연결된 모든 노드에 대해 다음의 비교를 수행해서 더 짧은 거리로 변경합니다.

 

min( 연결된 노드의 최단 거리, 선택된 노드의 최단 거리 + 간선의 거리 )

 

4. 위 2~3의 과정을 연결된 모든 노드에 대해 반복합니다.

 

다음 그래프에 대해 위의 실행 과정을 적용하여 최단 거리를 구해 봅시다.

 

 

이 알고리즘은 어떤 노드부터 시작해도 상관없습니다.

여기서는 1번 노드를 출발 노드라고 설정합니다.

그리고, 출발 노드는 최단 거리로 0을 가집니다.

나머지 노드의 최단 거리는 ∞로 설정합니다.

 

 

최단 거리를 가진 1번 노드에 연결된 2번과 3번 노드까지의 최단 거리를 비교해서 더 작은 값으로 변경합니다.

2번 노드에 대해선 min( ∞, 0 + 5 ) = 5가 최단 거리이고,

3번 노드에 대해선 min( ∞, 0 + 2 ) = 2가 최단 거리입니다.

 

 

현재, 3번 노드가 최단 거리를 갖고 있으므로, 3번 노드에 연결된 노드들부터 다시 최단 거리를 비교합니다.

4번 노드에 대해서 min( ∞, 2 + 7 ) = 9가 최단 거리입니다.

 

 

 

다음은, 2번 노드가 가진 최단 거리가 5로 가장 작습니다.

2번 노드에 연결된 노드들에 대해 최단 거리를 계산합니다.

4번 노드에 대해서 min( 9, 5 + 1) = 6이므로, 9를 6으로 대체합니다.

5번 노드에 대해선 min( ∞, 5 + 13 ) = 18이 최단 거리입니다.

 

 

 

다음은, 4번 노드가 가진 최단 거리가 6으로 가장 작습니다.

5번 노드에 대해서 min( 18, 6 + 10 ) = 16이 최단 거리입니다.

 

 

 

마지막, 5번 노드와 연결된 노드가 없으므로 알고리즘 적용을 마칩니다.

만약, 연결된 노드가 있더라도, 이미 방문된 노드는 재방문하지 않습니다.

 

 

 

이 과정을 코드로 작성하면 다음과 같습니다.

#include <vector>
#include <queue>
#include <limits.h> // for INT_MAX
using namespace std;

#define SIZE    20000
using Edge = pair<int, int>;    // < 노드, 가중치 >

vector<Edge> graph[SIZE+1];
int minDist[SIZE+1];    // 최단 거리를 저장할 배열
bool visited[SIZE+1];

struct myComp{

    bool operator()( const Edge& a, const Edge& b){ // 내림차순으로 정렬
        return a.second > b.second;
    }
};

void dijkstra(int start, int vect_cnt){

    priority_queue< Edge, vector<Edge>, myComp> q;  // 최소 heap

    for( int i = 1; i <= vect_cnt; i++){
        minDist[i] = INT_MAX;  // 초기화
    }

    minDist[start] = 0; // 출발 노드의 최단 거리는 0
    q.emplace( start, 0);
    
    while(!q.empty()){

        const Edge& edge = q.top();
        
        int vert = edge.first;

        q.pop();

        if ( visited[vert]) // 방문했던 노드를 다시 방문할 필요없음
            continue;

        visited[vert] = true;

        for( const auto& x : graph[vert]){
            
            int next = x.first;
            int nextDist = minDist[vert] + x.second;

            if ( nextDist < minDist[next]){
                minDist[next] = nextDist;
                q.emplace( next, minDist[next]);
            }
        }  
    } 
}

위의 코드에서, 우선순위 큐를 사용함으로써, 최단 거리를 가진 노드를 우선 탐색할 수 있게 하고 있습니다.

이렇게 하면, 불필요한 간선 비교 횟수를 줄일 수 있습니다.

 

우선순위 큐를 사용하는 이유

 

 

이 알고리즘을 사용하여 실제 문제를 해결 과정은 여기에서 볼 수 있습니다.

[백준/BOJ] 1753번: 최단 경로 ( 다익스트라 알고리즘 ) - C++ 문제 풀이

 

그런데, 간선의 가중치가 음수인 경우, 이 알고리즘을 적용할 수 없는 이유는 무엇일까요?

 

음수의 가중치를 갖는 순환 경로

 

 

위와 같은 그래프의 경우, 간선 가중치의 합( 1 + 10 - 13 = -2 )이 음수가 되는 순환 경로를 반복해서 방문하면, 방문할 때마가 거리의 합이 더욱 작아집니다.

예를 들어, 정점 1에서 출발해서 3번 정점까지의 최단 거리는, 순환 경로를 돌아서 3번 정점에 재방문할 때마다 작아집니다.

이렇듯, 무한히 작아지는 최단 거리 문제가 발생합니다.

 

하지만, 벨만-포드( Bellman-Ford ) 알고리즘은 위의 경우가 발생하는 경우를 판단할 수 있습니다.

벨만-포드와 관한 내용은 여기에서 볼 수 있습니다.

[C++] 최단 거리를 구하는 벨만-포드( Bellman-Ford ) 알고리즘