[알고리즘] 최단 거리 알고리즘 - 다익스트라, 백준 1753 C++ 풀이까지

https://blog.encrypted.gg/1037

[실전 알고리즘] 0x1D강 - 다익스트라 알고리즘

바킹독님의 블로그를 참고하여 공부한 내용을 기록한 글입니다.

---

Naive 다익스트라 알고리즘

플로이드 알고리즘은 모든 점의 쌍 (All Pair)에 대한 최단 거리를 구하는 알고리즘이다.

반면 다익스트라는 한 시작점에서 다른 모든 정점까지의 최단 거리를 구한다.

 

또한 플로이드는 음수인 간선에 대해서도 문제 없이 최단 거리를 구할 수 있고, 음수 사이클의 경우만 제한이 존재했다. 다익스트라는 음수 가중치인 경우 아예 사용할 수 없다.

 

알고리즘을 보자. 기본적으로 매 step마다 도달할 수 있는 정점 중 거리가 가장 가까운 정점을 구해서 그 거리를 확정하는 방식으로 동작한다.

각 단계가 뭔지, 단계마다 도달할 수 있는 정점의 의미가 뭔지 위의 그래프를 예시로 생각해보자.

1. 첫 단계는 도달할 수 있는 정점이 출발 단계인 1만 존재한다. 따라서 1 -> 1의 거리를 0으로 확정한다.
2. 1이 확정되었고, 1에서 도달할 수 있는 정점은 2 / 3 / 4가 존재한다. 가장 가까운 거리는 3이고 그와의 거리는 2로 확정한다.
3. 현재 확정된 정점은 1, 3 이다. 1, 3에서 도달할 수 있는 정점은 다음과 같다.
   a. 1 -> 2 (3)
   b. 1 -> 4 (5)
   c. 3 -> 4 (2 + 2)
   가장 짧은 거리는 1 -> 2이며 2로 거리를 확정한다.
4. 네 번째 step에서는 1, 2, 3이 방문상태이며 똑같이 도달할 수 있는 정점 중 가장 짧은 거리의 정점을 확정하면 된다.

여기서 구현적으로 시간을 줄일 수 있는 아이디어가 존재한다.

이렇게 1, 2, 3번 정점까지 확정한 뒤 다음 정점을 계산할 때이다. 1 -> 4 까지 거리가 4이고 1 -> 5 까지 거리가 11이란걸 계산할 때 1번과 연결된 노드를 다 보고, 2번과 연결된 노드를 다 보는 방식으로 O(VE)로 구할 수 있겠지만 새 정점을 추가할 때 마다 미리 테이블에 거리를 계산해두면 O(V^2 + E)로 줄일 수 있다.

 

이게 무슨말이냐면 일단 다시 처음으로 돌아서 1번 노드만 확정된 경우, 2 / 3 / 4 까지의 거리를 아래와 같이 미리 계산해둔다.

이제 최단 거리 테이블에서 최소값을 찾는다. d[3]이 2로 최소이므로 3번 정점을 확정할 수 있다. 그리고 3번 정점이 확정되었으니, 그 다음은 3번 노드에서 뻗어나가는 간선의 거리만을 새로 계산하면 된다. 결과는 아래와 같다.

---

알고리즘의 증명

알고리즘을 다시 생각해보면, 첫 단계에서 1 -> 3이 가장 거리가 짧으므로 3번 정점을 확정할 수 있었다. 이게 왜 가능할까?

 

귀류법으로 생각해서 중간에 다른 정점을 거쳐 거리 2보다 짧은 경로가 존재한다고 가정해보자.

예를 들어 1 -> 3 보다 1 -> 2 -> 3이 더 짧은 것이다. 이 경우 중간에 음수 간선이 존재하는게 아닌 이상 1 -> 2를 첫 단계에서 선택할 것이었으므로 이런 케이스는 존재할 수 없다. 

 

똑같은 논리로 다익스트라는 음수 간선을 처리할 수 없다.

다익스트라 알고리즘에 따르면 첫 단계로 3번 노드를 확정시킨다. (1 -> 3 : 2)

그리고 1 -> 2를 확정시키고 끝이나는데, 음수 간선이 존재하므로 사실은 1- > 2 -> 3이 더 짧은 거리이다.

---

우선순위 큐를 이용한 현대의 다익스트라 알고리즘

다익스트라 알고리즘은 매 번 가까운 정점을 뽑아내야 한다. 아래의 과정대로 구현하면 된다.

1. 우선순위 큐에 (0, 시작점) 추가
2. 우선순위 큐에서 거리가 가장 작은 원소를 선택, 해당 거리가 최단 거리 테이블에 있는 값과 다르다면 해당 원소를 제거하고 3번 과정은 스킵
3. 선택된 정점 v에 대해, 현재 최단 거리 테이블에 있는 v의 이웃의 값보다 v를 경유해서 가는 것이 더 짧은 거리인 경우 최단 거리 테이블의 값 갱신. 우선순위 큐에 (거리, 이웃 정점) 추가
4. 우선순위 큐가 빌 때 까지 2~3 반복

예시로 보자.

1번 정점만 확정된 초기 상태이다. 1번 원소가 선택되었고 해당 거리 (0)가 최단 거리 테이블 d[1] = 0과 다르지 않으므로 이웃인 2, 3, 4에 대해 현 시점의 최단 거리를 채워 넣는다. 여기서 최단 거리란 최단 거리 테이블 or 1번 정점을 경유하는 경우이다. 

또한 우선순위 큐도 같이 채워 준다.

 

다음 차례에서는 (2, 3)을 뽑는다. d[3] = 2이므로 이웃 정점들을 본다. 3 -> 4가 존재하므로 d[3] + 2 = 4. 따라서 (4, 4)를 삽입하고 최단 거리 테이블 또한 갱신한다.

이 경우 우선순위 큐에는 4번 정점에 대한 노드가 두 개 존재하게 된다. 이래서 최단 거리 테이블과 우선순위 큐에서 뽑은 정점이 같은 값인지 확인하는 과정이 필요한 것이다.

 

단계를 쭉 거치다보면 (5, 4)를 뽑게 될 것이고 d[4]는 5와 다르므로 (5, 4) 노드는 그냥 큐에서 제거하고 넘어가면 된다.

 

이렇게 우선순위 큐를 활용하는 경우 O(E log E)가 된다. 간선 1개당 최대 1개의 원소가 추가될 수 있기 때문이다. 바로 구현을 해보자.

https://www.acmicpc.net/problem/1753

이 문제로 코드를 짜보고 확인하면 된다.

 

/** 다익스트라 1753 최단경로 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

int v, e, st;

vector<pair<int, int>> adj[20005];
const int INF = 0x3f3f3f3f;
int d[20005]; // 최단 거리 테이블

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> v >> e >> st;
    fill(d, d + v + 1, INF);

    while (e--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // 최소 힙

    d[st] = 0;
    pq.push({d[st], st});

    while (!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();

        // d[cur]과 우선순위 큐 정점이 다른 경우
        if (d[cur.second] != cur.first)
            continue;
        for (auto nxt : adj[cur.second])
        {
            if (d[nxt.second] <= d[cur.second] + nxt.first)
                continue;
            // cur을 거쳐 nxt로 가는게 더 가까운 경우
            d[nxt.second] = d[cur.second] + nxt.first;
            pq.push({d[nxt.second], nxt.second});
        }
    }

    for (int i = 1; i <= v; i++)
    {
        if (d[i] == INF)
            cout << "INF\n";
        else
            cout << d[i] << '\n';
    }
}

 

구현 시 다음 사항은 꼭 주의하자!

1. 반드시 최소 힙으로 선언해야 한다. C++에서 최소 힙은 greater 이다.
2. 우선 순위 큐에 {거리, 정점 번호} 순으로 넣어 거리가 작은 것이 큰 우선순위를 가지게끔 설정해야 한다.