Dijkstra Algorithm
첫 번째로 다루어 볼 SSP( Single Source Shortest Path, 단일 출발지 최단 경로 ) 알고리즘은 다익스트라 알고리즘 ( Dijkstra Algorithm ) 이다.
다익스트라 알고리즘은,
음의 가중치가 없는 그래프 에서
한 노드에서 다른 모든 노드들까지의 최단 거리 를 구하는 알고리즘이다.
(다양한 최단 경로 알고리즘이 있는 만큼, 규칙과 이유를 정확하게 알고 있어야 한다!)
기본적인 원리는 Greedy Algorithm 이다.
출발점으로부터의 최단거리를 ‘확실히’ 알고 있는 점들의 집합을 S 라고 두자.
매 단계마다 S의 집합에 포함된 정점들만을 이용하여 갈 수 있는 최단거리의 배열 dist를 업데이트 하고,
( dist[i] : i번 노드까지의 최단 거리 )
이를 이용하여 S 에 한 개씩 정점을 추가한다.
노드의 개수가 총 V개라면, V 번의 단계를 거치면 모든 점들의 최단 거리를 구할 수 있다!
따라서, 위와 같은 방법으로 반드시 최단 거리를 찾을 수 있다.
다익스트라 알고리즘을 조금 더 자세히 파헤쳐 보자.
dist 배열을 초기화한다. 기본값은 ‘도달하지 못한다’의 무한대 이므로, 적당히 INF = 999999999 정도로 초기화 시켜준다.
출발점을 S에 넣고, S로부터 “한 번만에” 갈 수 있는 모든 점들의 dist를 업데이트한다.
출발점과 직접 연결되어 있으면 dist 값이 업데이트될 것이며, 그렇지 않다면 INF로 남아있을 것이다.dist의 값들 중 가장 크기가 작은 점을 뽑아, S에 넣는다.
이후, S에 방금 추가한 점으로부터 “한 번만에” 갈 수 있는 모든 점들의 dist를 업데이트한다.
이 때, 기존에 노드의 dist 값이 정해져 있다면 더 작은 경우에만 업데이트 해주면 된다.dist의 배열 중 가장 작은 값의 노드를 S에 넣고, 위 과정을 반복하면 된다.
( 참고 : S 집합은 설명을 위해 사용되는 것 뿐이며, 실제 코드 구현에선 하지 않는다 )
다익스트라 알고리즘의 정당성(Greedy Algorithm의 정당성)을 조금 더 자세히 생각해 보자.
S가 주어져 있을 때, S 외부의 한 점 Vi에 대하여 Vi까지의 최단거리는 S의 점들만을 거치거나 S 외부의 점들을 거치는 두 가지 경우 중 하나이다.
만약 Vi의 dist 값이 최소여서 Vi를 S에 추가하려 하는데, 현재 dist에 저장된 값보다 S 밖의 점을 거치는 것이 사실 최단 경로였다고 가정해 보자.
이 경우, Vi 까지의 경로 중 거치는 S 밖의 점 까지의 거리가 반드시 Vi 까지의 거리보다 작다.
따라서, Vi의 dist 값이 최소라는 가정에 모순이다.
마지막으로, 다익스트라 알고리즘의 시간 복잡도에 대해 생각해 보자. (점 V개, 간선 E개)
위 알고리즘에서는 두 가지 작업이 진행된다.
- 각 정점마다 인접한 간선들을 모두 조사하여, dist 값을 업데이트 하는 과정.
- dist 중 최소의 값을 찾아 S에 넣어주는 과정.
기본적으로 과정 1 에서는 $O(E)$, 과정 2에서는 $O(V)$의 시간복잡도가 걸려 총 $O(EV)$의 시간복잡도가 소요된다.
여기서, 우선 순위 큐 (Priority_Queue)를 활용하면 과정 2의 시간복잡도를 $O(log V)$으로 줄일 수 있다.
힙 구조를 이용하면, 최소값을 찾는 탐색 과정을 log 의 단위로 해낼 수 있기 때문이다.
따라서, 우선 순위 큐를 이용하여 구현한 다익스트라 알고리즘의 시간복잡도는 $O(ElogV)$ 이다.
필자가 직접 구현한 다익스트라 알고리즘의 코드는 Baekjoon 1753 (최단경로) 에서 확인 가능하다.
참고 : INF 끼리 계산이 되지 않도록 주의해야 한다. ( INF 이면 return을 바로 해버린다거나, 건너뛴다거나 등 )
실제로 무한대면 문제가 없지만, 코드 상에서 INF는 그저 큰 값에 불과하므로 INF 끼리 연산하면 문제가 발생할 수도 있다.
Dijkstra Algorithm
