티스토리 뷰

다익스트라 알고리즘은 간선에 가중치가 있는 그래프에서 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 최단경로 소스코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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<intint>>> 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, -1sizeof(d));//거리가 담길 배열 d를 나올 수 없는 수(-1)로 초기화
    priority_queue<pair<intint>> 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;
}
cs


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


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


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


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




댓글
  • 프로필사진 ㅇㅇ 안녕하세요! 자세한 설명 감사합니다. 이 블로그에서 정말 많이 배워가고있어요ㅋㅋ 저 근데 혹시

    if (d[here] != -1)
    continue;//이미 계산되었다면 넘어감

    이 부분에서 새로 계산된 값이 기존 값보다 더 작은 경우를 반영 못하지 않을까요? 예시에서 1-2-3이 만약 7로 1-3의 8보다 작다면 d[3]이 이미 계산되었지만 바꿔줘야 할거같아요
    2018.05.31 11:11
  • 프로필사진 JASON 자손9319 안녕하세요~. 힙을 이용한 다익스트라 알고리즘은 항상 최적의 경우를 반환하기 때문에 예시로 든 케이스는 발생하지 않습니다. 만약 1-2-3 이 7으로 가장 빠른 케이스라면 d[3]가 8이 되기전에 7로 먼저 갱신이 되기 때문입니다. 2018.05.31 11:15 신고
  • 프로필사진 ㅇㅇ 아 정말 그러네요 ㅋㅋㅋㅋㅋㅠ
    min-heap으로 항상 최솟값부터 갱신하는거군요. 답변 정말 빠르시네요 감사합니다!!
    2018.05.31 11:26
  • 프로필사진 ㅇㅇㅇ 정확한 자세한 설명 감사합니다. 이거보고 다익스트라 알고리즘 이해가 쉬워졌네요... 2019.10.05 01:42
  • 프로필사진 골드마스터 환상적인 소스 구성과 설명입니다... 2020.04.10 08:23
  • 프로필사진 Jun 혹시 어느부분에서

    "pq에 삽입될 수 있는 정점이 최대 V^2이므로 "

    가 되는지 알 수 있을까요?
    2020.11.02 19:51
댓글쓰기 폼