다익스트라 알고리즘(Dijkstra's Algorithm)

다익스트라 알고리즘은 간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘 입니다.

여기서 말하는 1:N이란 한 정점 V를 기준으로 V와 같은 컴포넌트에 속해있는 모든 정점들과의 최단거리를 계산한다는 의미입니다.

보통 가중치가 없는 그래프에서의 1:N 최단거리는 BFS (O(V+E))를 통하여 계산해주고, 가중치가 있는 그래프에서의 N:N 최단거리는 플로이드 워셜(O(N^3))으로 계산해주는게 일반적입니다.

단 다익스트라를 포함한 위에서 제시한 알고리즘들은 가중치가 음수 일때는 사용하지 못합니다.

가중치가 음수일 경우 벨만포드 알고리즘(O(VE))이나 SPFA(O(VE))를 통하여 최단거리를 구해주어야 합니다.

그렇다면 다익스트라는 어떤 방식으로 1:N 최단거리를 구해낼까요?

일단 다익스트라 알고리즘의 아이디어는 최단거리는 최단거리로 이루어져 있다는 그리디(Greedy)한 생각에서부터 출발합니다.

최단거리는 최단거리로 이루어져 있다는게 무슨뜻이냐면 

예를들어 1번 정점에서 2번 정점으로 가는 최단거리의 경로가 1->4->3->2 으로 형성되어 있다고 가정해봅시다.

이때 1번정점에서 4번 정점으로 가는 최단거리와 1번정점에서 3번 정점으로 가는 최단거리는 1번 정점에서 2번 정점으로 가는 최단거리 내에 포함됩니다.

만약 1번 정점에서 4번 정점으로 가는 최단경로가 1->5->4라면 1번 정점에서 2번정점으로 가는 최단경로가 1->5->4->3->2가 되어야 하므로 모순이 됩니다.

고로 이 아이디어에 기반하여 정점 V로부터 최단거리를 구하는 과정에 구해지는 정점들을 이용하여 계속 최단거리를 구해나갑니다.

만약에 1->3의 최단거리를 구했다면 3에 연결 된 간선들은 최단경로의 후보가 될 수 있는 간선인거죠

이제 본격적으로 다익스트라 알고리즘이 어떻게 동작하는지 알아봅시다.

우선 다익스트라 알고리즘을 위하여 최단거리를 기록할 배열과 후보가 될 수 있는 간선중 최고로 작은 간선을 빠르게 뽑아낼 수 있는 힙(heap) 자료구조가 필요합니다.

동작원리는 V부터 시작하여 최단거리를 갱신해 나가는데 이 때 어떤 정점으로의 최단거리를 구해냈을 때 그 정점에 연결 된 간선(다른 정점으로 최단경로의 후보가 될 수 있는 간선)을 전부 힙에 삽입해주고 힙에서 가장 작은 정보부터 보면서 이미 최단거리가 계산 된 정점이면 건너뛰는 방식으로 구해나갑니다.

음... 글로 보는것보다 같이 한번 해봅시다

이러한 유향그래프에서 1번 정점에서부터 타 정점으로의 최단거리를 구해나가겠습니다. 

(간선에 적힌 숫자는 간선의 가중치입니다.)

1번 정점으로부터의 거리를 기록할 표도 만들어 줍니다.

우선 힙은 두가지 정보를 저장할것입니다. 하나는 1번 정점으로 부터의 거리 또 하나는 정점의 번호 입니다.

맨처음에 힙에는 (0,1)이 들어가게 될 것입니다. (1번정점이 1번정점으로부터 0만큼 떨어져 있다.)

이후 힙을 뒤져서 거리가 가장 작은 원소를 찾아내겠죠. 당연히 원소가 하나뿐이니 (0,1)이라는 정보가 나올 것입니다.

따라서 테이블 D[1]은 0으로 갱신되고 1번 정점에 연결 된 간선들의 정보가 1번 정점까지의 거리에 누적되어 힙에 정보가 들어갑니다.

힙에 빨간색으로 칠해진 간선들의 정보가 들어가게 됩니다.

이제 힙에는 (8,2) (9,3)의 정보가 들어가겠네요. 이 때 주의해야할 점이 힙에 들어가는 거리는 지금까지의 누적거리 이기 때문에 

정점 V에 연결 된 간선의 정보를 삽입할 때 d[V]+해당 간선의 가중치가 들어가야합니다. 이 경우에는 d[1]이 0이기 때문에 해당 간선의 가중치가 그대로 들어가게 된 것입니다.

이후 힙을 뒤져서 가장 작은 거리를 확인합니다. (8,2)의 정보를 뽑아내어 보니 2번 정점은 아직 최단거리가 구해지지 않았으니 d[2]를 8로 갱신한 뒤 2번 정점에 연결 된 간선의 정보를 힙에 삽입해줍니다.

현재 힙에는 (9,6) (9,3) (11,3) (15,5)의 정보가 담기게 됩니다.

이제 힙의 가장 작은 원소인 6번 정점의 최단거리를 갱신해준 뒤 6번 정점에 연결 된 간선들의 정보를 힙에 삽입해 줍니다.

다시 힙을 뒤져 3번 정점을 최단거리로 갱신해준 뒤 힙에 3번정점과 연결 된 간선의 정보를 삽입해줍니다.

다시 힙을 뒤져 보니 3번 정점의 정보가 나옵니다 하지만 이미 최단거리가 구해져있으므로 해당 정보는 버립니다.

그 다음 정보인 4번 정점을 갱신해준 뒤 연결 된 간선의 정보를 힙에 삽입해줍니다.

다시 힙을 뒤져보니 4번 정점의 정보가 나옵니다. 이미 계산 된 정보이기 때문에 지나쳐 줍니다. 다음 정보인 7번 정점을 갱신해준 뒤 연결 된 간선의 정보를 힙에 삽입해줍니다.

다시 힙을 뒤져보니 5번 정점의 정보가 나옵니다. 5번 정점의 최단거리를 갱신해 준 뒤 연결 된 간선의 정보를 힙에 삽입해줍니다.

이후 힙을 뒤져 정보를 확인하지만 이미 계산이 끝난 정점들 뿐이니 다 버려준 뒤 힙이 비게되면 함수를 종료합니다.

다익스트라는 이러한 방식으로 동작합니다.

물론 최적화를 위해 어떤 정점에 연결 된 간선의 정보를 힙에 삽입할 때 이미 최단거리가 계산 된 정점이면 삽입하지 않는 처리를 해줄 수 있습니다.

그리고 V->E 까지의 최단거리만 구해도 된다면 E에 대한 정보를 구했을 때 함수를 종료시켜도 되죠

자 이제 소스코드를 확인해봅시다.

힙을 직접 구현해서 쓰기보단 stl의 priority_queue를 이용하면 편리합니다.

기본적으로 priority_queue는 max heap이기 때문에 가중치에 -1을 곱하여 음수로 관리해주면 편리하게 계산 가능합니다.

다음은 BOJ 1753 최단경로 소스코드입니다.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int v, e, s, x, y, z, d[20002];
vector<vector<pair<int, int>>> vt;
int main() {
    scanf("%d%d%d", &v, &e, &s);
    vt.resize(v + 1);
    for (int i = 0; i < e; i++) {
        scanf("%d%d%d", &x, &y, &z);
        vt[x].push_back({ y,z });
    }    //인접리스트로 그래프를 형성
    memset(d, -1, sizeof(d));//거리가 담길 배열 d를 나올 수 없는 수(-1)로 초기화
    priority_queue<pair<int, int>> pq;//정보를 담을 힙(거리,정점)
    pq.push({ 0,s });//시작정점의 정보를 삽입
    while (pq.size()) {//pq가 빌 때까지 다익스트라 알고리즘 동작
        int here = pq.top().second;//현재 확인하는 정점
        int cost = -pq.top().first;//거리(비용) -를 붙이는 이유는 pq를 minheap으로 사용하기 위함
        pq.pop();
        if (d[here] != -1)
            continue;//이미 계산되었다면 넘어감
        d[here] = cost;//최단거리 정보를 갱신
        for (auto it : vt[here]) {
            int next = it.first;//다음 정점
            int acost = -it.second - cost;//누적 된 거리
            if (d[next] != -1)
                continue;//이미 계산되었다면 넘어감
            pq.push({ acost,next });
        }
    }
    for (int i = 1; i <= v; i++) {
        if (d[i] == -1)puts("INF");
        else printf("%d\n", d[i]);
    }//최단거리 출력
    return 0;
}

마지막으로 다익스트라 알고리즘의 시간복잡도는 어떻게 될까요?

pq에 삽입될 수 있는 정점이 최대 V^2이므로 O(log(V^2)) -> O(2*log(V)) -> O(log(V))번 pq에서 top을 꺼내게 됩니다.

이후 거리를 갱신하기 위해 간선을 보는게 결국 E번 이루어지기 때문에 

총 시간복잡도는 O(Elog(V))가 됩니다.