다익스트라 알고리즘
1. 다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.
참고로 그래프 알고리즘 중 최소 비용을 구하는 데에 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다.
2. 동작 단계
- 출발 노드와 도착 노드를 설정한다.
- ‘최단 거리 테이블’을 초기화한다.
- 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.
- 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 ‘최단 거리 테이블’을 업데이트한다.
- 3~4의 과정을 반복한다.
‘최단 거리 테이블’은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록한다. N개 크기의 배열을 선언하고 큰 값을 넣어 초기화 시킨다.
‘노드 방문 여부 체크 배열’은 방문한 노드인지 아닌지 기록하기 위한 배열로, 크기는 ‘최단 거리 테이블’과 같다.
3. 동작 예
- 출발 노드 1번, 도착 노드는 6번이라고 하고 거리 테이블을 전부 큰 값, 여기서는 inf(무한대)로 초기화, 가 노드를 잇는 가중치 역시 표시했다.
- 출발 노드를 먼저 선택하고 거리를 0으로 한다.
- 1번 노드와 연결된 인접 노드는 2,4 이다. 그곳까지 가는 거리를 각각 기존의 거리값과 비교해 최솟값으로 업데이트한다. 가령 2의 경우 inf와 2중 작은 값인 2를 택해 할당한다.
- 최근 갱신한 테이블 기준, 방문하지 않는 노드 중 가장 거리값이 작은 번호를 다음 노드로 택한다. 위 상태에서는 4번 노드이다.
- 4번 노드에서 같은 작업을 수행한다. 4번과 연결된 2,5번까지 오는 거리를 계산한다.
- 가령 5의 경우엔 (4번까지 오는 데 필요한 거리 + 4->5 간선의 가중치) 값인 2와 기존의 값인 inf 중 최솟값을 계산한다.
- 2번 노드의 경우엔 기존 값인 2와 4번을 거쳐가는 값인 1+2 = 3을 비교한다. 그렇다면 2번 노드는 기존 값이 더 작으므로 업데이트하지 않는다.
- 다음으로 선택될 노드는 아직 방문하지 않은 노드 2,3,5,6 중 거리값이 가장 작은 노드이므로 2 또는 5이다. 거리 값이 같다면 일단 인덱스가 작은 노드를 택한다고 하고 2번으로 가보자.
- 2번 노드와 연결된 3,4번 노드에 대해 같은 과정을 반복한다.
- 그 다음 노드는 3,5,6번 중 가장 거리값이 작은 5번 노드가 되겠다.
- 5번 노드와 연결된 6번 노드에 같은 과정을 반복한다.
- 다음 노드를 선택해야 하는데, 아직 방문하지 않은 3번과 6번 중 거리값이 작은 것은 6번이다. 그런데 6번은 더 이어지는 노드도 없는데다 도착노드이다. 따라서 알고리즘을 종료한다.
4. 특징
- 위 동작 예시에서 볼 수 있듯이, 다익스트라 알고리즘은 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다.
- 또한 각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다.
- 도착 노드는 해당 노드를 거쳐 다른 노드로 가는 길을 찾을 필요는 없다.
- 다익스트라 알고리즘은 가중치가 양수일 때만 가능하다는 중요한 특징이 있다.
위 그림의 상황에서 1-> 4의 경로가 최단경로이려면 3+k가 1보다 커야한다. 즉 k > -2가 성립해야 한다.
반대로 k가 -5라고 한다면 오히려 1->2->4 경로가 더 최단 경로가 된다. 그 말인 즉, 1번에서 연결된 노드 중 4번이 가중치가 적다는 이유로 최단 거리를 1이라 할 수는 없다는 이야기이다.
따라서 다익스트라 알고리즘을 사용하기 위해서는 정점 사이를 잇는 간선의 가중치가 양수여야 한다. 그래야 한 번 방문한 정점에 대해서는 값을 업데이트 하지 않아도 되는 것이다.
5. 구현 방법
다익스트라 알고리즘을 구현하는 방법에는 ‘방문하지 않은 노드’를 다루는 방식에서 ‘순차 탐색’할 것인지 ‘우선순위 큐’를 쓸 것인지로 나뉜다.
5.1 순차 탐색
‘방문하지 않은 노드 중 거리값이 가장 작은 노드’를 선택해 다음 탐색 노드로 삼는다. 그 노드를 찾는 방식이 순차 탐색이 된다. 즉 거리 테이블의 앞에서부터 찾아내야 하므로 노드의 개수만큼 순차 탐색을 수행해야 한다. 따라서 노드 개수가 N이라고 할 때 각 노드마다 최소 거리값을 갖는 노드를 선택해야 하는 순차 탐색이 수행되므로 $(N-1) \times N = O(N^2)$의 시간이 걸린다.
5.2 우선순위 큐
순차 탐색을 사용할 경우 노드 개수에 따라 탐색 시간이 매우 오래 걸릴 수 있다.
이를 개선하기 위해 우선순위 큐를 도입하기도 한다.
거리 값을 담을 우선순위 큐는 힙으로 구현하고, 만약 최소 힙으로 구현한다면 매번 루트 노드가 최소 거리를 가지는 노드가 될 것이다.
우선순위 큐에서 사용할 ‘우선순위’의 기준은 ‘시작 노드로부터 가장 가까운 노드’가 된다. 따라서 큐의 정렬은 최단 거리인 노드를 기준으로 최단 거리를 가지는 노드를 앞에 배치한다.
위의 순차 탐색을 쓰는 구현과는 다르게 우선순위 큐를 사용하면 방문 여부를 기록할 배열은 없어도 된다. 우선순위 큐가 알아서 최단 거리의 노드를 앞으로 정렬하므로 기존 최단 거리보다 크다면 무시하면 그만이다. 만약 기존 최단거리보다 더 작은 값을 가지는 노드가 있다면 그 노드와 거리를 거리를 우선순위 큐에 넣는다.
간선의 수를 E(Edge), 노드의 수를 V(Vertex)라고 했을 때 $O(Elog V)$가 된다.
우선순위 큐에서 꺼낸 노드는 연결된 노드만 탐색하므로 최악의 경우라도 총 간선 수인 E만큼만 반복한다. 즉 하나의 간선에 대해서는 $O(logE)$이고, E는 $V^2$보다 항상 작기 때문에 E개의 간선을 우선순위 큐에 넣었다 빼는 최악의 경우에 대해서는 $O(Elog V)$가 성립한다.