출처: 이것이 취업을 위한 코딩테스트다.
다익스트라 최단 경로 알고리즘은 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘이다.
다익 스트라 최단 경로 알고리즘은 "음의 간선"이 없을 때 정상적으로 동작한다. (실제로 GPS에 쓰인다.)
다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다.
매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다.
알고리즘의 원리를 간략히 설명하면, 다음과 같다.
1. 출발노드를 정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 3~4 번을 반복한다.
다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며, 리스트를 계속 갱신한다는 특징이 있다.
매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다.
나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면, '더 짧은 경로도 있었네? 이제부터는 이 경로가 제일 짧은 경로야" 라고 판단한다.
따라서 '방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인'해서 그 노드에 대해 4번과정을 수행한다는 점에서 그리디 알고리즘으로 볼 수 있다.
다익스트라 알고맂므을 구현하는 방법은 2가지 이다.
1. 구현하기 쉽지만 느리게 동작하는 코드
2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드
간단한 다익스트라 알고리즘의 시간복잡도
: O(V^2)이다. 왜냐하면 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야하고 현재 노드와 연결된 노드를 매번 일일히 확인해야하기 때문이다.
전체 노드개수가 5000가 이하이면 풀 수 있지만, 10000개가 넘는다면 문제를 해결하기 어렵다.
=> 개선된 다익스트라 알고리즘 이용
개선된 다익스트라 알고리즘은 최악의 경우에도 O(ElogV)를 보장한다.
간단한 다익스트라 알고리즘은 최단거리가 가장 짧은 노드를 찾기 위해서,
매번 최단거리 테이블을 선형적으로 탐색하는 과정이 O(V)가 걸렸기 때문에 오래걸린 것이다.
하지만 최단거리가 가장 짧은 노드를 단순히 선형적으로 찾는게 아니라, 더욱 빠르게 찾을 수 있다면 알고리즘 시간복잡도를 줄일 수 있다.
그렇다면 어떻게 빠르게 찾을 수 있는가?
Heap을 사용한다.
Heap 자료구조를 사용하게 되면, 특정 노드까지의 최단 거리에 대한 정보를 Heap에 담아서 처리하므로,
출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다.
이 과정에서 선형 시간이 아닌 로그 시간이 걸린다.
