콘텐츠로 이동

Dijkstra 알고리즘

$n$개의 정점과 $m$개의 간선으로 이루어진 방향 또는 무방향 가중치 그래프가 주어집니다. 모든 간선의 가중치는 음수가 아닙니다. 또한 시작 정점 $s$가 주어집니다. 이 글에서는 시작 정점 $s$에서 다른 모든 정점까지의 최단 경로 길이를 구하고, 최단 경로 자체를 출력하는 방법을 다룹니다.

이 문제는 단일 출발점 최단 경로 문제라고도 합니다.

알고리즘

다음은 네덜란드의 컴퓨터 과학자 Edsger W. Dijkstra가 1959년에 기술한 알고리즘입니다.

각 정점 $v$에 대해 $s$에서 $v$까지의 현재 최단 경로 길이를 $d[v]$에 저장하는 배열 $d[]$를 만듭시다. 처음에는 $d[s] = 0$이고, 다른 모든 정점에 대해서는 이 길이가 무한대입니다. 구현에서는 충분히 큰 수(가능한 어떤 경로 길이보다도 크다고 보장되는 수)를 무한대로 사용합니다.

$$d[v] = \infty,~ v \ne s$$

또한 각 정점 $v$가 표시되었는지 여부를 저장하는 불리언 배열 $u[]$를 관리합니다. 처음에는 모든 정점이 표시되지 않은 상태입니다:

$$u[v] = {\rm false}$$

Dijkstra 알고리즘은 $n$번 반복 수행됩니다. 각 반복에서는 표시되지 않은 정점 중 $d[v]$ 값이 가장 작은 정점 $v$를 선택합니다:

당연히 첫 번째 반복에서는 시작 정점 $s$가 선택됩니다.

선택된 정점 $v$를 표시합니다. 다음으로, 정점 $v$에서 완화를 수행합니다: $(v,\text{to})$ 형태의 모든 간선을 살펴보고, 알고리즘은 각 정점 $\text{to}$에 대해 $d[\text{to}]$ 값을 개선하려고 시도합니다. 현재 간선의 길이가 $len$이라면, 완화 코드는 다음과 같습니다:

$$d[\text{to}] = \min (d[\text{to}], d[v] + len)$$

이러한 간선을 모두 살펴보면 현재 반복이 끝납니다. 마지막으로 $n$번의 반복이 끝나면 모든 정점이 표시되고 알고리즘이 종료됩니다. 이렇게 구한 값 $d[v]$가 $s$에서 모든 정점 $v$까지의 최단 경로 길이라고 주장합니다.

시작 정점 $s$에서 도달할 수 없는 정점이 있다면, 그 정점들의 $d[v]$ 값은 무한대로 남아 있다는 점에 유의하십시오. 당연히 알고리즘의 마지막 몇 번의 반복에서는 이러한 정점들이 선택되지만, 이 정점들에 대해서는 유용한 작업이 수행되지 않습니다. 따라서 선택된 정점까지의 거리가 무한대가 되는 즉시 알고리즘을 중단할 수 있습니다.

최단 경로 복원

보통은 최단 경로의 길이뿐만 아니라 최단 경로 자체도 알아야 합니다. $s$에서 임의의 정점까지의 최단 경로를 복원하기에 충분한 정보를 어떻게 유지하는지 살펴봅시다. 선행자 배열 $p[]$를 유지하는데, 여기서 각 정점 $v \ne s$에 대해 $p[v]$는 $s$에서 $v$까지의 최단 경로에서 끝에서 두 번째 정점입니다. 여기서는 어떤 정점 $v$까지의 최단 경로를 택해 이 경로에서 $v$를 제거하면 정점 $p[v]$에서 끝나는 경로를 얻게 되고, 이 경로가 정점 $p[v]$에 대한 최단 경로가 된다는 사실을 이용합니다. 이 선행자 배열을 사용하면 임의의 정점까지의 최단 경로를 복원할 수 있습니다. $v$에서 시작하여 시작 정점 $s$에 도달할 때까지 현재 정점의 선행자를 반복해서 택하면, 정점이 역순으로 나열된 원하는 최단 경로를 얻습니다. 따라서 정점 $v$까지의 최단 경로 $P$는 다음과 같습니다:

$$P = (s, \ldots, p[p[p[v]]], p[p[v]], p[v], v)$$

이 선행자 배열을 구성하는 것은 매우 간단합니다. 완화에 성공할 때마다, 즉 선택된 어떤 정점 $v$에 대해 어떤 정점 $\text{to}$까지의 거리가 개선될 때마다 $\text{to}$의 선행 정점을 정점 $v$로 갱신합니다:

$$p[\text{to}] = v$$

증명

Dijkstra 알고리즘의 정확성이 기반하는 주요 명제는 다음과 같습니다:

임의의 정점 $v$가 표시된 이후에는 그 정점까지의 현재 거리 $d[v]$가 최단이며, 더 이상 변하지 않습니다.

증명은 귀납법으로 합니다. 첫 번째 반복에서는 이 명제가 자명합니다. 표시된 정점은 $s$뿐이고, 그 거리 $d[s] = 0$은 실제로 $s$까지의 최단 경로의 길이입니다. 이제 이 명제가 이전의 모든 반복에 대해, 즉 이미 표시된 모든 정점에 대해 참이라고 가정하고, 현재 반복이 끝난 후에도 이 명제가 깨지지 않음을 증명합시다. 현재 반복에서 선택된 정점을 $v$라 합시다. 즉, $v$는 알고리즘이 표시할 정점입니다. 이제 $d[v]$가 실제로 그 정점까지의 최단 경로의 길이 $l[v]$와 같음을 증명해야 합니다.

정점 $v$까지의 최단 경로 $P$를 생각해 봅시다. 이 경로는 두 부분으로 나눌 수 있습니다. 표시된 노드로만 이루어진 $P_1$(적어도 시작 정점 $s$는 $P_1$에 속합니다)과 경로의 나머지 부분 $P_2$(표시된 정점을 포함할 수도 있지만, 항상 표시되지 않은 정점으로 시작합니다)입니다. 경로 $P_2$의 첫 번째 정점을 $p$로, 경로 $P_1$의 마지막 정점을 $q$로 나타냅시다.

먼저 정점 $p$에 대해 명제를 증명합니다. 즉, $d[p] = l[p]$임을 증명합시다. 이는 거의 자명합니다. 이전 반복 중 하나에서 정점 $q$를 선택하고 그 정점에서 완화를 수행했습니다. (정점 $p$의 선택 방식에 의해) $p$까지의 최단 경로는 $q$까지의 최단 경로에 간선 $(p,q)$를 더한 것이므로, $q$에서의 완화가 $d[p]$의 값을 최단 경로의 길이 $l[p]$로 설정했습니다.

간선의 가중치가 음이 아니므로, 최단 경로의 길이 $l[p]$(방금 $d[p]$와 같음을 증명했습니다)는 정점 $v$까지의 최단 경로의 길이 $l[v]$를 넘지 않습니다. $l[v] \le d[v]$라는 점(Dijkstra 알고리즘이 가능한 최단 경로보다 더 짧은 경로를 찾았을 수는 없기 때문입니다)을 고려하면 다음 부등식을 얻습니다:

$$d[p] = l[p] \le l[v] \le d[v]$$

한편, 정점 $p$와 $v$가 모두 표시되지 않았고 현재 반복에서 $p$가 아닌 정점 $v$를 선택했으므로, 또 다른 부등식을 얻습니다:

$$d[p] \ge d[v]$$

이 두 부등식으로부터 $d[p] = d[v]$라는 결론을 얻으며, 앞서 구한 방정식들로부터 다음을 얻습니다:

$$d[v] = l[v]$$

증명 끝.

구현

Dijkstra 알고리즘은 $n$번의 반복을 수행합니다. 각 반복에서 값 $d[v]$가 가장 작은 표시되지 않은 정점 $v$를 선택하여 표시하고, 모든 간선 $(v, \text{to})$를 확인하며 값 $d[\text{to}]$를 개선하려고 시도합니다.

알고리즘의 실행 시간은 다음으로 구성됩니다:

  • $O(n)$개의 표시되지 않은 정점 중에서 값 $d[v]$가 가장 작은 정점을 찾는 $n$번의 탐색
  • $m$번의 완화 시도

이 연산들을 가장 단순하게 구현하면 매 반복마다 정점 탐색에 $O(n)$번의 연산이 필요하고, 각 완화는 $O(1)$에 수행할 수 있습니다. 따라서 알고리즘의 최종 점근적 동작은 다음과 같습니다:

$$O(n^2+m)$$

이 복잡도는 밀집 그래프, 즉 $m \approx n^2$일 때 최적입니다. 그러나 $m$이 최대 간선 수 $n^2$보다 훨씬 작은 희소 그래프에서는 $O(n \log n + m)$ 복잡도로 문제를 해결할 수 있습니다. 해당 알고리즘과 구현은 희소 그래프에서의 Dijkstra 문서에서 찾아볼 수 있습니다.

const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;

void dijkstra(int s, vector<int> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);
    p.assign(n, -1);
    vector<bool> u(n, false);

    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        }

        if (d[v] == INF)
            break;

        u[v] = true;
        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }
}

여기서 그래프 $\text{adj}$는 인접 리스트로 저장됩니다. 각 정점 $v$에 대해 $\text{adj}[v]$는 이 정점에서 나가는 간선들의 리스트, 즉 pair<int,int>의 리스트를 담고 있으며, 쌍의 첫 번째 원소는 간선의 반대편 끝에 있는 정점이고 두 번째 원소는 간선의 가중치입니다.

이 함수는 시작 정점 $s$와 반환값으로 사용될 두 개의 벡터를 인자로 받습니다.

먼저 코드는 거리 $d[]$, 표시 $u[]$, 선행 정점 $p[]$ 배열을 초기화합니다. 그런 다음 $n$번의 반복을 수행합니다. 각 반복에서는 표시되지 않은 모든 정점 중 거리 $d[v]$가 가장 작은 정점 $v$를 선택합니다. 선택된 정점 $v$까지의 거리가 무한대이면 알고리즘을 종료합니다. 그렇지 않으면 해당 정점을 표시하고, 이 정점에서 나가는 모든 간선을 확인합니다. 간선을 따라 완화가 가능하면(즉, 거리 $d[\text{to}]$를 개선할 수 있으면) 거리 $d[\text{to}]$와 선행 정점 $p[\text{to}]$를 갱신합니다.

모든 반복을 수행하고 나면 배열 $d[]$에는 모든 정점까지의 최단 경로 길이가 저장되고, 배열 $p[]$에는 (시작 정점 $s$를 제외한) 모든 정점의 선행 정점이 저장됩니다. 임의의 정점 $t$까지의 경로는 다음과 같이 복원할 수 있습니다:

vector<int> restore_path(int s, int t, vector<int> const& p) {
    vector<int> path;

    for (int v = t; v != s; v = p[v])
        path.push_back(v);
    path.push_back(s);

    reverse(path.begin(), path.end());
    return path;
}

참고 문헌

  • Edsger Dijkstra. A note on two problems in connexion with graphs [1959]
  • Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms [2005]

연습 문제