D´Esopo-Pape 알고리즘¶

$n$개의 정점과 가중치가 $w_i$인 $m$개의 간선으로 이루어진 그래프와 시작 정점 $v_0$이 주어집니다. 정점 $v_0$에서 다른 모든 정점까지의 최단 경로를 구하는 것이 목표입니다.

D´Esopo-Pape 알고리즘은 대부분의 경우 Dijkstra 알고리즘과 Bellman-Ford 알고리즘보다 빠르게 동작하며, 음수 간선이 있어도 동작합니다. 그러나 음수 사이클이 있으면 동작하지 않습니다.

설명¶

배열 $d$에 최단 경로의 길이를 저장한다고 합시다. 즉, $d_i$는 정점 $v_0$에서 정점 $i$까지의 현재 최단 경로 길이입니다. 처음에는 $d_{v_0} = 0$을 제외한 모든 정점에 대해 이 배열을 무한대로 채웁니다. 알고리즘이 끝나면 이 배열에는 최단 거리가 저장됩니다.

배열 $p$에 현재 조상을 저장한다고 합시다. 즉, $p_i$는 $v_0$에서 $i$까지의 현재 최단 경로에서 정점 $i$의 직전 조상입니다. 배열 $d$와 마찬가지로 배열 $p$도 알고리즘이 진행되는 동안 점차 바뀌며, 마지막에 최종 값을 가지게 됩니다.

이제 알고리즘을 살펴봅시다. 각 단계에서 정점 집합 세 개를 관리합니다:

$M_0$ - 거리가 이미 계산된 정점들(최종 거리가 아닐 수도 있습니다)
$M_1$ - 거리를 현재 계산하고 있는 정점들
$M_2$ - 거리가 아직 계산되지 않은 정점들

집합 $M_1$의 정점들은 양방향 큐(덱)에 저장합니다.

알고리즘의 각 단계에서 집합 $M_1$에서(큐의 앞에서) 정점 하나를 꺼냅니다. 선택한 정점을 $u$라고 합시다. 이 정점 $u$를 집합 $M_0$에 넣습니다. 그런 다음 이 정점에서 나가는 모든 간선을 순회합니다. 현재 간선의 다른 쪽 끝을 $v$, 그 가중치를 $w$라고 합시다.

$v$가 $M_2$에 속하면, $v$를 큐의 뒤에 넣어 집합 $M_1$에 삽입합니다. $d_v$는 $d_u + w$로 설정합니다.
$v$가 $M_1$에 속하면 $d_v$의 값을 개선해 봅니다: $d_v = \min(d_v, d_u + w)$. $v$는 이미 $M_1$에 있으므로 $M_1$과 큐에 삽입할 필요가 없습니다.
$v$가 $M_0$에 속하고 $d_v$를 개선할 수 있다면($d_v > d_u + w$), $d_v$를 개선하고 정점 $v$를 큐의 맨 앞에 넣어 집합 $M_1$에 다시 삽입합니다.

물론 배열 $d$를 갱신할 때마다 배열 $p$의 해당 원소도 함께 갱신해야 합니다.

구현¶

각 정점이 현재 어느 집합에 속하는지 저장하기 위해 배열 $m$을 사용합니다.

struct Edge {
    int to, w;
};

int n;
vector<vector<Edge>> adj;

const int INF = 1e9;

void shortest_paths(int v0, vector<int>& d, vector<int>& p) {
    d.assign(n, INF);
    d[v0] = 0;
    vector<int> m(n, 2);
    deque<int> q;
    q.push_back(v0);
    p.assign(n, -1);

    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        m[u] = 0;
        for (Edge e : adj[u]) {
            if (d[e.to] > d[u] + e.w) {
                d[e.to] = d[u] + e.w;
                p[e.to] = u;
                if (m[e.to] == 2) {
                    m[e.to] = 1;
                    q.push_back(e.to);
                } else if (m[e.to] == 0) {
                    m[e.to] = 1;
                    q.push_front(e.to);
                }
            }
        }
    }
}

복잡도¶

이 알고리즘은 보통 상당히 빠르게 동작하며, 대부분의 경우 Dijkstra 알고리즘보다도 빠릅니다. 그러나 이 알고리즘이 지수 시간이 걸리는 경우도 존재하므로, 최악의 경우를 고려하면 적합하지 않습니다. 참고로 스택 오버플로와 Codeforces의 논의를 확인하십시오.