Dijkstra

Dijkstra algorithm

다익스트라 알고리즘은 최단거리 알고리즘의 일종으로 모든 간선이 음이 아닌 가중치를 가질 때 사용할 수 있는 알고리즘이다. 해당 알고리즘은 시작점을 입력받아 모든 정점까지의 최단거리 및 경로를 반환할 수 있다. 다익스트라 알고리즘의 코드는 다음과 같다.

vector<pair<int, int>> route[100001];
long dist[100001];

void dijkstra(int s){
    dist[s] = 0;
    priority_queue<pair<long,int>,vector<pair<long,int>>,greater<pair<long,int>>> pq;
    pq.push(make_pair(0, s));
    while(!pq.empty()){
        long d = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if(dist[cur] < d) continue;
        for(int i=0; i<route[cur].size(); i++){
            long next_d = d + route[cur][i].second;
            int next = route[cur][i].first;
            if(next_d < dist[next]){
                dist[next] = next_d;
                pq.push(make_pair(next_d, next));
            }
        }
    }
}

기본적으로 다익스트라 알고리즘은 지금까지 발견한 최단거리를 짧은 것부터 채워나간다. route는 입력받은 그래프를 저장하여 first에는 목적지의 정점, second에는 해당 정점까지의 거리가 들어간다. dist는 정점 s로 부터 각 점점까지의 최단거리를 저장하며, 힙으로 구현된 우선순위 큐에는 거리가 짧은 순으로 정렬되어 저장된다. 따라서 큐를 순회하면서 거리가 짧은 순으로 해당 정점과 이어진 다른 정점과의 거리를 통해 최단거리를 갱신한다.

Proof of Dijkstra’s algorithm

다익스트라 알고리즘은 방문한 정점의 수에 대해 귀납법으로 증명한다. 이때 사용되는 귀납 가설은 다음과 같다.

모든 방문한 정점 $v$에 대해 $dist \lbrack v \rbrack$는 $s$에서 $v$까지의 최단거리이다.

아래 귀납 증명에서 $S$는 방문한 정점의 집합이다.

Induction Case($\vert S \vert = k+1$): $\vert S \vert = k$일 때, 귀납 가설이 참임을 가정하자. 이때, $(k+1)$번째로 방문할 정점을 $w$, 그리고 그 직전에 방문한 정점을 $v$라고 하자. 다익스트라 알고리즘은 거리가 짧은 순으로 방문하므로 다익스트라 알고리즘의 정의에 의해 그래프 $G$의 정점의 집합에서 방문한 정점의 집합을 제외한 집합에서 뽑은 $u$와 $w$는 다음과 같은 성질을 지닌다.

\[\forall u \in V(G) \setminus S, \ dist \lbrack u \rbrack \geq dist \lbrack w \rbrack\]

이제 다음의 명제를 귀류법으로 증명하자.
Claim1. $s$에서 $w$로의 최단경로 중 마지막 간선이 ($v \to w$)인 최단경로가 존재한다.
해당 명제가 거짓이라 가정하면 마지막 간선이 $v \to w$인 $s$에서 $w$로의 경로는 최단경로가 아니므로 이보다 거리가 짧은 경로 $s \to v_1 \to v_2 \to \cdots \to w$가 존재한다. 해당 경로에서 처음으로 $S$의 원소가 아닌 정점을 $v_i$라 하자. $w$는 $S$의 원소가 아니므로, 그러한 $v_i$는 항상 존재한다. $v_i$가 $S$의 원소가 아니므로 $dist \lbrack v_i \rbrack \geq dist \lbrack w \rbrack$가 성립하며 $v_i$부터 $w$까지의 모든 간선의 가중치가 0이상이므로, 경로 $s \to v_1 \to v_2 \to \cdots \to w$의 길이는 $dist \lbrack w \rbrack$ 이상이다. 이는 가정과 모순되므로 Claim1은 참이다.

Claim1에 의하여 마지막 간선이 $v \to w$인 $s$에서부터 $w$로의 최단경로가 존재하며, 귀납 가정에 의하여 $v$까지의 최단거리는 $dist \lbrack v \rbrack$이다. 따라서 $s$에서 $w$로의 최단거리는 $dist \lbrack w \rbrack = dist \lbrack v \rbrack + w(v \to w)$임을 알 수 있다.

다익스트라 알고리즘에서 음수 간선이 허용되지 않는 이유는 Claim1에서 알 수 있다. Claim1의 귀류법 증명에서 Claim1이 거짓이라는 가정이 모순으로 이어진다고 서술하며 각 간선의 가중치가 0이상이라는 점을 활용했다. 따라서 음수 가중치를 갖는 간선이 있다면, 동일한 논리를 활용할 수 없으므로 위 증명이 유효하지 않게 된다.

Multi-source dijkstra

다익스트라 알고리즘은 한 정점으로부터 모든 정점까지의 최단거리를 구하는 알고리즘이다. 그런데 만약 여러 개의 정점으로부터 각 정점까지의 최단거리의 최솟값을 구해야 할 수도 있다. 이런 경우 시작 정점의 수만큼 다익스트라 알고리즘을 실행하는 것 보다 효율적인 방법이 있다. 그 방법이 Multi-source dijkstra로 여러 정점으로부터 시작하는 다익스트라 알고리즘이다. 그래프 $G$와 시작 정점의 집합 $S$가 주어질 때, 다음과 같은 방법으로 구현할 수 있다.

function Multi-source dijkstra($G, S$):
 $G^\prime \gets G$
 add $\sigma$ to $V(G^\prime)$
 for $v \in S$:
  add $(\sigma \to v)$ with weight 0 to $E(G^\prime)$
 return Dijkstra($G, \sigma$)

요약하면 가상의 시작 정점 $\sigma$를 만들고 모든 시작 정점에 가중치 0의 간선으로 이어준다. 가중치가 0이므로 초반에 시작 정점들을 모두 방문하게 되며, 결과적으로 여러개의 정점으로부터 시작하는 다익스트라 알고리즘이 된다.

k-th shortest path

다익스트라 알고리즘은 한 정점으로부터 모든 정점까지의 최단거리를 구하는 알고리즘이지만, 가장 짧은 경로 말고 $k$번째 최단경로의 길이가 필요할 때도 있다. 우선 $k$번째 최단경로를 정의하면, 어떤 경로 $P$가 $s$에서 $t$로의 $k$번째 최단경로라는 것은 $s$에서 $t$로의 서로 다른 모든 경로를 그 길이 순으로 정렬했을 때 길이가 $P$보다 짧거나 같은 경로의 수가 $k$개인 경로를 말한다. 길이가 동일한 경로가 여러 개 존재할 수 있으므로 편의상 $P$보다 짧은 경로가 $k$개보다 적고 $P$보다 짧거나 같은 경로의 수가 $k$개 이상인 경우를 지칭하기도 한다.

$k$번째 최단경로를 다익스트라 알고리즘을 활용해 구하는 아이디어는 dist 배열의 각 값을 하나의 수가 아닌 크기 $k$의 배열로 관리하는 것이다. 각 정점마다 $k$개의 최단경로의 길이를 관리하며, 지금까지 발견한 $k$개의 최단경로보다 짧은 경로를 발견한다면 이를 추가하는 형태이다. k-th shortest path dijkstra는 기존의 다익스트라 알고리즘 정당성 증명과 동일하게 길이가 짧은 경로부터 고려된다는 사실을 이용하면 어렵지 않게 정당성을 보일 수 있다. 시간복잡도의 경우, 각 정점의 $i$번째 최단거리를 확정지으며 각 $i$마다 한 번씩 $Q$에서 제거되므로 $O(k(E+V)logV)$임을 알 수 있다.

Reference

1. 공군 휴머니스트 air-wiki