비순환 그래프에서의 경로

그래프에 사이클이 없으면 최단 경로를 매우 쉽게 찾을 수 있습니다.

이 경우 주어진 정점에서 나머지 모든 정점까지의 최단 거리를 구하는 문제는 동적 계획법 방식으로 해결할 수 있습니다. 정점 $v$까지의 최단 거리는 최단 경로 위의 마지막 간선이 될 수 있는 모든 후보를 살펴봄으로써 구할 수 있습니다:

이 식을 계산하려면 주어진 정점 $v$에 대해 모든 역방향 간선을 빠르게 순회할 수 있어야 하며, $d_v$를 계산할 때 필요한 모든 $d_u$가 이미 계산되어 있도록 하는 순회 순서를 찾아야 합니다.

#구현

구체적으로, 그래프를 전치하여 인접 리스트 형식으로 변환합니다. 즉, 각 정점마다 그 정점으로 들어오는 간선들의 목록을 가중치와 함께 구성합니다:

vector< pair<int, int> > t[N]; // откуда ведет ребро и его вес

각 정점마다 시작 정점으로부터의 거리를 저장할 배열 $d$를 만듭시다. 편의상 시작 정점의 번호는 0이라고 하겠습니다. 이 배열은 처음에 첫 번째 칸을 제외한 모든 칸이 «무한대», 즉 어떤 올바른 거리보다도 확실히 큰 수로 채워집니다.

vector<int> d(n, inf);
d[0] = 0;

이제 그래프의 정점들을 어떤 위상 정렬 순서대로 — 이 순서는 별도의 순회로 구할 수도 있고 어떤 식으로든 암묵적으로 구할 수도 있습니다 — 차례로 방문하면서, $v$의 역방향 간선들을 살펴보고 위 공식에 따라 $v$까지의 거리를 완화(더 최적인 값으로 갱신)하겠습니다:

for (int v = 1; u < n; u++)
    for (auto [u, w] : t[v])
        d[v] = min(d[v], d[u] + w);

이러한 알고리즘은 매우 간단하며 $O(m)$에 동작합니다.

안타깝게도 그래프에 사이클이 있는 일반적인 경우에는 이 방법이 작동하지 않습니다. 완화 d[v] = min(d[v], d[u] + w)는 임의의 $v$와 $y$에 대해 항상 올바르며 아무것도 망가뜨리지 않지만, 핵심 가정은 필요한 이전 거리가 모두 이미 계산되어 있는 순회 순서가 존재한다는 것이며, 일반적인 경우 그러한 순회를 찾는 문제는 최단 경로를 찾는 문제 자체보다 쉽지 않습니다.

#경로 복원

거리뿐만 아니라 경로 자체도 복원할 수 있도록, 각 정점마다 거리와 함께 마지막 완화가 어느 정점에서 이루어졌는지를 저장할 수 있습니다:

vector<int> p(n);

for (int v = 1; u < n; u++) {
    for (auto [u, w] : t[v]) {
        if (d[v] < d[u] + w) {
            d[v] = d[u] + w;
            p[v] = u;
        }
    }
}

이제 $v$까지의 최단 경로를 복원하려면 정점 $v$의 조상들을 따라 거슬러 올라가기만 하면 됩니다:

while (v != 0) {
    cout << v << endl;
    v = p[v];
}

또한 문제에서는 그래프의 「뼈대」를 살펴보는 것이 유용한 경우가 많습니다. 즉, 최단 경로를 찾는 알고리즘을 아무것이나 하나 실행한 뒤, 어떤 최단 경로 위에 놓인 간선, 즉 $d_v = d_u + w_{uv}$를 만족하는 간선만 그래프에 남깁니다. 이러한 부분 그래프는 비순환이므로 다루기 쉬우며, 예를 들어 같은 방식으로 여러 가지 DP를 계산할 수 있습니다.

연습 문제. 비순환 그래프에서 $s$에서 $t$로 가는 최단 경로의 개수를 $O(m)$에 구하십시오.