12. 자료구조론 - Dijkstra's algorithm

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점으로의 최단 거리를 구하는 알고리즘입니다.

이때 그래프의 가중치는 음수이면 안됩니다. 음수인 가중치가 있으면 계속 해당 간선을 지나며 무한한 음수가 될 수 있기 때문입니다.

알고리즘

다익스트라 알고리즘에서 그래프의 각 노드의 상태는 다음 두 가지 중 하나입니다.

• 최단거리가 결정된 노드
• 아직 최단거리가 구해지지 않은 노드

알고리즘의 진행을 간단히 살펴보면 다음과 같습니다.

1. 시작 정점 S로부터 각 정점 V로 가는 최단거리를 의미하는 d[V]를 초깃값으로 초기화해놓는다.
   • 이때 초깃값은 어떤 최단거리보다도 큰 임의의 최댓값으로 설정해야함.
2. 시작 정점 S에서 연결된 노드들의 d[V]를 간선의 가중치로 업데이트해준다.
3. 모든 노드v에 대해 d[v]가 가장 작은 노드를 선택한다. 그러면 해당 노드는 최단 거리가 해당 d[v]로 결정된 것이다. 
   • 해당 노드에 대해서는 최단거리가 구해진 노드라는 표시를 해둔다.
4. 아직 최단거리가 구해지지 않은 노드가 존재한다면, 3번에서 선택된 노드를 가지고 연결된 노드들의 d[V]를 업데이트해주고 3번을 반복한다.
5. 모든 노드의 최단거리가 구해졌다면 종료한다. 

시작정점으로부터 업데이트된 모든 거리 중 최소 거리를 갖는다면, 해당 거리보다 작은 거리를 갖는 다른 경로는 존재하지 않음이 확실하기 때문에 위의 알고리즘이 성립합니다. 

시작 정점으로부터 각 정점으로의 최단거리를 저장하는 d[V]에서 계속해서 가장 작은 값을 선택해야 하기 때문에 min heap 자료구조를 사용하면 좋습니다.

Example

위와 같은 그래프를 살펴보겠습니다.

처음에 각 노드의 거리는 최댓값(무한대)으로 초기화해둡니다. t는 temporary로 아직 최단거리가 결정되지 않은 노드를 의미합니다.

시작 노드인 1번 노드와 연결된 2, 3, 6번 노드의 거리를 업데이트해줍니다.

2번 노드가 거리 7로 최소 거리를 가지므로, 2번의 최단거리는 7로 결정됩니다. 따라서 p(permanent) 상태가 됩니다.

2번노드가 permanent한 노드가 되었으므로, 2번노드로부터 연결된 노드들의 거리를 업데이트해줍니다.

다음으로 최소 거리를 갖는 노드는 3번 노드이므로 permanent 상태로 바뀝니다.

이 과정을 계속 반복하면,

위와 같은 상태가 되며 모든 노드의 최단거리를 구할 수 있게됩니다.

 

간단한 알고리즘을 수도코드로 보면 다음과 같습니다.

// d[v] : 시작 정점으로부터 노드v까지의 최단거리
// pred[v] : 최단경로에서 노드v의 이전 노드
// S : 시작 정점
// W(a, b) : a에서 b사이 간선의 가중치
for v in Vertex {
    d[v] = infinity;
    pred[v] = null;
}

d[S] = 0;
priority_queue<Node> pq;
for v in S의 인접노드 {
    d[v] = W(S, v);
    pred[v] = S;
    pq.push(v);
}

while (!pq.empty()) {
    minNode = pq.deleteMin();
    for v in minNode의 인접노드 {
        if (d[minNode] + W(minNode, v) < d[v]) {
            d[v] = d[minNode] + W(minNode, v);
            pred[v] = minNode;
            pq.push(v);
        }        
    }
}

시간복잡도를 계산해보면 처음에 초기화하는데에 O(N)이 소요됩니다.

그리고 priority queue에서 minNode를 가져오는 것은 O(logN)이 소요되고, 결국은 모든 노드에 대해 불리기 때문에 총 O(NlogN)이 소요됩니다.

마지막으로 minNode의 모든 인접노드에 대해 (if문은 모두 통과한다고 가정) priority queue에 push하는 과정이 수행되는데, 한번 새 노드를 heap에 집어넣는데 O(logN)이 소요되고, 모든 간선의 개수만큼 해당 과정이 수행되기 때문에 O(e*logN) 이 됩니다.

따라서 이를 모두 합치면 O(N) + O(NlogN) + O(e*logN) => O((n+e)logN)이 됩니다. (e는 간선의 개수)

예제 문제

https://www.acmicpc.net/problem/1238

1238번: 파티

위 문제는 다익스트라를 활용해 풀 수 있는 대표적인 문제입니다.