120. Dial's Algorithm

다이얼 알고리즘(Dial's Algorithm)은 간선들의 가중치가 크지 않은 그래프에서 최단 경로를 구할 때 사용할 수 있는 알고리즘으로, $0$-$1$ BFS의 발전된 버전이라고 생각할 수도 있다. 각각의 간선의 가중치가 $0$ 이상 $c$ 이하의 정수일 때 다이얼 알고리즘은 $(c+1)$개의 큐를 사용하여 최단 경로를 구한다. 큐 대신 스택, 벡터 등을 사용할 수도 있다. $c = 1$일 경우 $0$-$1$ BFS와 매우 유사한 형태가 되며, $2$개의 큐를 하나의 덱으로 바꾸면 $0$-$1$ BFS와 같아진다.

 

다이얼 알고리즘의 작동 방식은 다음과 같다.

    1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 경로를 $d_i$라고 한다.

    2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다.

    3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다.

    4. 빈 큐 $(c+1)$개에 $0$부터 $c$까지 번호를 붙이고, $0$번 큐에 정점 $k$를 추가한다.

    5. 현재까지 확인한 정점들의 $d_i$의 최댓값을 체크하는 피벗 변수를 $p$라고 한다. $p$의 초기값은 $0$이다.

    6. $p$번 큐가 비었을 경우 $p$를 $(p+1) \bmod (c+1)$로 바꾼다.

    7. $p$번 큐에 정점이 존재할 경우, $p$번 큐에서 정점 하나를 뺀다. 이 정점을 $u$라고 하자.

    8. $u$가 아직 선택되지 않았을 경우, $u$를 선택하고 $u$와 인접한 정점들을 확인한다. $u$와 인접한 각각의 정점 $v$에 대해, $d_u + w(u, v) < d_v$일 경우 $d_v$를 $d_u + w(u, v)$로 바꾼 다음 $(p + w(u,v)) \bmod (c+1)$번 큐에 정점 $v$를 추가한다.

    9. 모든 정점을 선택한 경우 실행을 종료한다. 그렇지 않다면 6번으로 돌아간다.

 

설명은 다소 복잡하지만, 간단하게 요약하면 $(c+1)$개의 큐를 차례로 확인하는 과정을 반복하면서 정점들의 $d_i$ 값을 갱신하는 것으로 이해할 수 있다. 시간복잡도를 계산해 보면, 확인하는 큐의 개수는 $\max(d_i) + 1$이고 정점과 인접한 정점들을 확인하는 횟수가 $n$이며 큐에 정점이 추가되는 횟수는 최대 $2m$이므로 $O(n+m+\max(d_i))$가 나온다. 그런데 $\max(d_i) \le (n-1)c$이므로 시간복잡도를 고쳐서 $O(cn+m)$으로 쓸 수 있다.

 

구현은 다음과 같다.

#import<bits/stdc++.h>
using namespace std;
int cnt, p, d[100005], vi[100005];
vector<pair<int, int>>e[100005];
int main()
{
    int c, k, m, n, x, y, z;
    cin >> n >> m >> c >> k;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        e[x].push_back({y, z});
    }
    fill(d + 1, d + n + 1, 1 << 30);
    d[k] = 0;
    queue<int>Q[c + 1];
    for(Q[0].push(k); cnt < n;)
    {
        if(Q[p].empty())
        {
            ++p %= (c + 1);
            continue;
        }
        int u = Q[p].front();
        Q[p].pop();
        if(vi[u])continue;
        vi[u] = 1;
        cnt++;
        for(auto &v: e[u])
        {
            if(d[u] + v.second < d[v.first])
            {
                d[v.first] = d[u] + v.second;
                Q[(p + v.second) % (c + 1)].push(v.first);
            }
        }
    }
}

변수 $cnt$는 방문한 정점의 수를 저장하며, $cnt$가 $n$이 되었을 때 반복을 종료한다. 만약 시작 정점에서 도달할 수 없는 정점이 있다면 이 반복문이 무한루프가 되기 때문에 종료 조건을 바꿔야 한다. $(c + 1)$개의 큐가 모두 비었을 때 반복을 종료하게 하는 방법이 대안이 될 수 있다.

#import<bits/stdc++.h>
using namespace std;
int cnt, p, d[100005], vi[100005];
vector<pair<int, int>>e[100005];
int main()
{
    int c, k, m, n, x, y, z;
    cin >> n >> m >> c >> k;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        e[x].push_back({y, z});
    }
    fill(d + 1, d + n + 1, 1 << 30);
    d[k] = 0;
    queue<int>Q[c + 1];
    Q[0].push(k);
    for(cnt = 1; cnt > 0;)
    {
        if(Q[p].empty())
        {
            ++p %= (c + 1);
            continue;
        }
        int u = Q[p].front();
        Q[p].pop();
        cnt--;
        if(vi[u])continue;
        vi[u] = 1;
        for(auto &v: e[u])
        {
            if(d[u] + v.second < d[v.first])
            {
                d[v.first] = d[u] + v.second;
                Q[(p + v.second) % (c + 1)].push(v.first);
                cnt++;
            }
        }
    }
}

변수 $cnt$의 의미가 '$(c+1)$개의 큐에 포함된 원소의 개수의 합'으로 변했다.