[알고리즘] 다익스트라 알고리즘

개요

다익스트라 알고리즘은 가중치가 있는 방향성 그래프에서, 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 문제이다.

 

알고리즘의 단계는 다음과 같다.

1. F는 공집합으로 둔다.

2. Y(최단 경로가 확정된 집합)에는 시작 정점 v1을 포함해 {v1}으로 둔다.

3. 최종해답을 얻을 때까지 다음 과정을 반복한다.

    (a) 선정 절차 / 적정성 점검 : V-Y에 속한 정점 중에서, v1에서 Y에 속한 정점만을 거쳐서 최단 경로가 되는 v를 선정한다.

    (b) v를 F에 추가한다.

    (c) v에서 F로 이어지는 최단경로 상의 이음선을 F에 추가한다.

    (d) 해답 점검 : Y = V가 되면 T = (V, F)가 최단경로를 나타내는 그래프가 된다.

 

예시

초기화 : v1에서 v2~v5까지의 최단 거리를 먼저 계산한다. (도달할 수 없다면 INF)

1. v1에서 제일 가까운 정점은 v5이므로, v5와 연결된 정점의 최단 거리를 갱신한다.

2. v5를 제외하고 v1에서 제일 가까운 정점은 v4이므로, v4와 연결된 정점의 최단 거리를 갱신한다.

3. 다음으로 v1에서 가까운 정점은 v3이므로, v3과 연결된 정점의 최단 거리를 갱신한다.

4. 마지막으로 v2를 방문하면 모든 정점의 최단 거리 갱신이 완료되었으므로 최종 해답을 얻을 수 있다.

 

추가 사항

다익스트라 알고리즘을 사용하기 위해서는 정점의 개수가 N이라고 할 때 touch[1...N]과 length[1...N] 배열을 유지해야 한다.

length[1...N] : Y에 속한 정점들만 중간에 거치도록 하여 v1에서 vi로 가는 최단경로의 길이

touch[1...N] : Y에 속한 정점들만 중간에 거치도록 하여 v1에서 vi로 가는 최단경로의 마지막 이음선을 <v, vi>라고 할 때 Y에 속한 정점 v

 

스도우코드

void Dijkstra(int n, const int W[][])
{
    int i, vnear;
    int touch[n + 1];
    int length[n + 1];
 
    // v1에서의 거리를 초기화한다.
    for (int i = 2; i <= n; i++)
    {
        touch[i] = 1;
        length[i] = W[1][i];
    }
 
    int roopNum = n;
 
    while (--roopNum)
    {
        // v1정점에서 최소 거리를 갖는 V-Y에 속한 정점을 찾는다.
        int min = INF;
        for (i = 2; i <= n; i++)
        {
            // 최소 거리를 갖는 정점을 찾았다면 min과 vnear를 갱신한다.
            if (0 <= length[i] < min)
            {
                min = length[i];
                vnear = i;
            }
        }
        
        // 찾은 vnear 정점에 연결된 다른 정점 사이의 최단 거리를 갱신한다.
        for (i = 2; i <= n; i++)
        {
            if (length[vnear] + W[vnear][i] < length[i])
            {
                length[i] = length[vnear] + W[vnear][i];
                touch[i] = vnear;
            }
        }
 
        // vnear를 Y에 넣는다.
        length[vnear] = -1;
    }
}

v[near] 선정

length[i] 재계산

시간 복잡도

(n-1) * 2(n-1) = 2(n-1)^2

 

위 방식으로 구한 다익스트라 알고리즘의 시간 복잡도는 n^2이다.

 

알고리즘 개선

length[i]를 갱신할 때 모든 정점에 대해 갱신해 줄 필요가 없다.

v와 연결된 V-Y에 속하는 정점만 갱신해주면 된다.

 

위 예시에서 length[i]를 update 해야 하는 횟수는 3번뿐이다.

Heap 구조를 사용하면 O(mlgn)으로 시간 복잡도를 줄일 수 있다. (m : 엣지의 개수)

 

최소 거리를 찾는 부분(find shortest and vnear)은 heap을 이용하면 O(lgn)만에 찾을 수 있다.

이것을 n-1번 반복하므로 시간 복잡도는 O(nlgn)이다.

최소 거리를 갱신하는 부분(update length and touch)은 최대 m번 발생한다. (정확히는 총 엣지수 m - v1에 연결된 엣지 수)

각각의 엣지는 다익스트라 알고리즘에서 한 번만 고려된다.

따라서 다익스트라 알고리즘의 시간 복잡도는 O(mlgn)이다.