Dijkstra 알고리즘과 실행시간(Priority Queue를 사용하는 이유)

정의

어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘


알고리즈 개요

데이크스트라 알고리즘은 각각의 꼭짓점 v에 대해 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.

데이크스트라 알고리즘은 변 경감(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지 길이가 w(u,v)인 변 (u, v)가 존재할 때, s에서 v까지의 최단 경로는 u까지의 최단 경로에 변 (u, v)를 추가함으로써 얻을 수 있다. 이 경로의 비용은 d[u]+w(u, v)가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다.

경감 연산은 모든 변 (u, v)에 대해 한번씩 경감이 적용되어 모든 d[v]가 최단 경로의 비용을 나타내게 되었을 때 끝난다.

실행시간

개의 변과 ${\displaystyle n}$개의 꼭짓점을 가진 그래프에 대해 대문자 O 표기법으로 데이크스트라 알고리즘의 실행시간을 나타낼 수 있다.
가장 간단한 구현으로, Q의 집합을 연결 리스트나 배열 구조로 구현하고 Extract-Min(Q) 함수를 단순한 선형 탐색으로 구현했을 때 실행 시간은 ${\displaystyle O(n^{2})}$ 시간이 된다.
만약 희소 그래프(sparse graph), 즉 ${\displaystyle n^{2}}$보다 훨씬 작은 개수의 변만을 갖는 그래프에 대해서는, 인접 리스트와 바이너리 힙 또는 피보나치 힙으로 구현한 우선순위 큐를 이용해 데이크스트라 알고리즘을 더 효율적으로 구현할 수 있다. 이진 힙을 이용하면 실행 시간은 ${\displaystyle O((m+n)\log n)}$ 시간이 되고, 피보나치 힙을 통해 ${\displaystyle O(m+n\log n)}$ 시간까지 개선할 수 있다.

우선순위 큐를 쓰는 이유
출처: http://makefortune2.tistory.com/26 [Simple in Complex with Simple] (감사합니다!)

결론적으로 말해서 최소거리 값 갱신 횟수의 증가때문이다. 먼저 우선순위 큐를 쓰지 않고 일반 큐를 써도 결과에는 차이가 없다. 하지만 우선순위 큐를 쓰는 이유는 속도에 이점이 있기 때문이다.
다익스트라 알고리즘에서 속도에 영향을 주는 요소는 큐에서 노드를 꺼내오는 횟수와 우선순위 큐의 갱신 횟수이다. 이게 무슨 뜻이냐면

예를들어 보자. 만약 위의 예제에서 일반 큐를 쓴다면 A에서 검사를 시작할 때, 연결된 두 노드 B와 C중 B부터

검사한다. 하지만 우선순위 큐라면 C부터 검사한다. 왜냐하면 우선순위 큐로 인해 최소 거리로 정렬된 순서
큐에서 추출되기 때문이다. 이 상황을 정리하면

A에서 E까지 최소거리를 검사할 때

일반 큐)

A -> B -> C -> E -> B -> D -> E -> E 순으로 검사

첫 번째 E 노드를 검사할 때, 현재 B까지 최소거리는 4, C까지 최소거리는 1, E까지 최소거리는 8이 된다.

하지만 그 다음 B노드를 검사할 때 B의 최소거리가 3으로 갱신되기 때문에 이전에 계산한 작업이 

무의미한 값이 된다. 이런 경우가 일반 큐를 사용할 때 나타나는 시간상의 비효율적인 대표 예이다.

우선순위 큐)

A -> C -> B -> B -> D -> E -> E -> E 순으로 검사

이 검사는 이전에 계산해둔 값이 그 단계에서 최소값이라는 것이 보장되기 때문에 갱신 횟수가 현저히 적어진다.

 이해를 돕기위한 작은 예지만 그래프의 크기가 커지면 커질수록 이런 일반 큐와 우선순위 큐 사이의 중복갱신

횟수가 일반큐가 월등히 많아지게 된다. 그러므로 최종적으로 일반 큐에서는 O(E+V^2)에서 우선순위 큐 사용 시

O(ElogV)으로 시간상의 이점이 발생하게 된다. (V는 정점 수, E는 엣지 수)

소스코드 : https://github.com/JaeguKim/Algorithm/tree/master/Dijkstra