다익스트라 알고리즘 (Dijkstra algorithm)
최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다.
크게 3가지의 알고리즘이 있다.
- 다익스트라 알고리즘
- 플로이드 워셜 알고리즘
- 벨만 포드 알고리즘
다익스트라 알고리즘은 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
- '음의 간선'이 없을 때 정상적으로 작동하는 게 특징이다.
- 음의 간선이란 0보다 작은 값을 가지는 간선을 의미한다.
- 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.
- 기본적으로 그리디 알고리즘이다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다.
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3과 4번을 반복한다.
다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다.
출발 노드는 1이다. 초기 상태에서는 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화한다. 이제 1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다. 현재 1번 노드 까지 오는 비용은 0이므로, 1번 노드를 거쳐서 2번, 3번, 4번 노드로 가는 최소 비용은 차례대로 2(0 + 2), 5(0 + 5), 1(0 + 1)이다. 현재 2번, 3번, 4번 노드로 가는 비용을 갱신한다.
이후의 모든 단계에서도 마찬가지로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해야 한다. 따라서 4번 노드가 선택된다. 이어서 4번에서 갈 수 있는 3번, 5번을 확인하고 3번과 5번 노드로 가는 최소 비용은 4(1 + 3), 2(1 + 1)이다.
1번 노드 기준으로 2번과 5번 노드까지의 최단 거리가 2로 값이 같다. 이럴 경우 일반적으로 번호가 작은 노드를 선택한다. 그리고 2번 노드를 거쳐서 도달할 수 있는 노드 중에서 거리가 더 짧은 경우가 있는지 확인한다. 2번 노드를 거쳐 3번 노드로 이동하는 경우, 5(2 + 3)만큼의 비용이 발생한다. 하지만 이미 현재 최단 거리 테이블에서 3번 노드까지의 최단 거리는 4이므로, 값이 갱신되지 않는다.
이번에는 5번 노드가 선택된다. 5번 노드를 통해 3번, 6번 노드로 갈 수 있다. 5번 노드까지 가는 최단 거리가 2이므로 5번 노드에서 3번 노드로 가는 거리인 1을 더한 3이 기존 값인 4보다 작기 때문에 새로운 값 3으로 갱신된다. 또한 6번 노드로 가는 거리도 마찬가지로 4로 갱신된다.
이를 반복하면 최단 거리 테이블이 최종 갱신된다.
이는 1번 노드로부터 출발했을 때 2번, 3번, 4번, 5번, 6번 노드까지 가기 위한 최단 경로가 2,3,1,2,4라는 의미이다.
다익스트라 알고리즘의 특징은 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것이다.
각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언, 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 순차 탐색한다.
순차 탐색하기 대문에 시간 복잡도는 O(V^2)이다(여기서 V는 노드의 개수). 왜냐하면 총 O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하고, 현재 노드와 연결된 노드를 일일히 매번 확인하기 때문이다.
개선된 다익스트라 알고리즘에서는 각 노드에 대한 최단거리를 담는 1차원 리스트 대신, 우선순위 큐를 이용해 시간 복잡도를 줄일 수 있다. 보통 우선순위 큐는 힙(Heap) 자료구조를 통해 많이 구현되는데, 이를 사용하면 출발 노드로부터 가장 거리가 짧은 노드를 빠르게 찾을 수 있어 복잡도는 최악의 경우에도 O(ElogV)를 만족한다. 여기서 E는 총 최대 간선의 개수이다.