최단 경로 알고리즘 - 다익스트라(=데이크스트라) (feat.백준 1753번)
다익스트라 최단경로 알고리즘은 특정 노드에서 출발해서 다른 노드로 가는 각각의 최단 경로를 모두 구할 수 있는 알고리즘이다. (다만, 이번 글에서는 최단 경로의 거리만 구할 수 있는 알고리즘을 공부한다. 추후에 경로까지 구하는 알고리즘을 업데이트 하도록 하겠습니다)
다익스트라 알고리즘의 조건) 방향/무방향 그래프 모두에서 사용할 수 있으며, 간선 간에 음의 간선이 없어야 함. 음의 간선이 문제에서 주어질 일은 거의 없기 때문에 크게 신경쓰지 않아도 되는 조건임. 실제로 다익스트라 알고리즘은 현실 세계의 gps sw의 기본 알고리즘으로 쓰인다고 한다.
다익스트라 최단 경로 알고리즘의 분류: 그리디 알고리즘으로 분류됨. 즉, 매 순간에 최선(가장 비용이 적은 간선으로 갈 수 있는 노드)의 선택을 하기 때문이다.
다익스트라 최단 경로 알고리즘의 원리
1. 우선 출발 노드를 선정. (이제 여기서 정한 노드부터 다른 모든 노드까지의 최단거리를 구할것임)
2. 최단 거리 테이블 초기화. (최단 거리 테이블을 갱신하는 방식으로 진행할 것임. 처음 테이블은 무한값으로 초기화시킴)
3. 아직 방문하지 않은 노드 중 현재까지의 최단거리가 가장 짧은 노드를 선택함.
4. 3번 단계에서 선택한 노드를 활용(이 노드와 이어진 노드들에 대해서, 이 노드를 거쳐서 갈 때의 경로 거리를 계산함. 만약 현재 테이블의 값보다 작다면 갱신해주면 됨)해서 최단 거리 테이블에서 갱신 할 수 있는 부분을 모두 갱신해줌.
5. 3번과 4번 과정을 반복함. 즉, 안고른 것 중 짧은 거 고르고 테이블 갱신하고 다시 고르고 갱신하고 반복.
여기서 중요한 점은 최단 거리 테이블은 말 그대로, 시작 노드에서 각 노드에 대한 현재까지의 최단 거리 정보를 갖고 있는 1차원 리스트임.
위 5단계 중 3번과 4번 단계를 반복 수행해서 최단 거리 테이블을 찾아간다. 이때 3번 단계에서 선택한 노드는 앞으로 이 알고리즘을 수행하면서 더이상 최단거리가 갱신되지 않는 노드가 된다.
이유: 이 3번 단계에서 선택할때 우리는 방문하지 않은 노드들 중 현재까지의 최단거리가 가장 짧은 노드a를 선택한다. 이걸 반대로 생각해보면, 이때의 시작노드부터 a노드의 최단거리가 b라고 할때 a노드를 선택하지 않고 다른 노드를 거쳐서 a노드로 가는 길 중 b보다 짧은 거리는 없다는 것을 의미함. 이미 그 노드까지 가는 거리만 해도 b이상이였기 때문에 3번단계에서 선택받지 못했기 때문이다.
따라서, 다익스트라 최단거리 알고리즘은 매 진행마다 하나의 노드에 대한 (시작노드부터 시작해서) 최단 거리를 확실히 찾는다.
다익스트라 알고리즘 구현하기
우선, 위와 같은 원리로 정직하게 코드를 구현한다면 아래와 같이 구현하게 될 것임
=> 하지만 위와 같은 방식은 시간복잡도가 O(V^2)의 시간이 걸림. 이렇게 오랜 시간이 걸리는 이유는 get_smallest_node 함수가 너무나 정직하게 선형적으로 V개 노드를 모두 탐색하기 때문임.
그렇다면 어떻게 해결할 수 있을까? 바로 우선순위 큐를 활용하면 된다. 우선순위 큐를 리스트가 아닌 최소힙을 활용해서 구현한다면, get_smallest_node()의 역할을 수행하는데 최대 O(logE)의 시간이 걸린다(최소힙의 규칙에 따라 루트 노드를 제거하고 다시 재정렬해야하는데 걸리는 시간이 O(logE)입니다)
우선순위 큐를 활용한 다익스트라 알고리즘은 아래와 같습니다.
개선된 알고리즘을 잘 보면, E개의 간선 원소를 우선순위 큐에 넣었다가 모두 빼는 연산과 유사함. 따라서, 이는 O(ElogE)이다. 그런데 E는 중복된 간선이 없다면 최대 V(V+1)/2 임. 따라서, E는 항상 V^2보다 작다. 그러므로, O(ElogV)라고 볼 수 있다. 따라서 이 개선된 알고리즘이 개선 전 알고리즘과 시간이 비슷해지려면 (logV)/2가 V보다 커져야 함. 하지만 그런 경우는 자연수 V에 대해서 발생하지 않음. 따라서 이 개선된 알고리즘을 기억하자.
위 코드는 백준 1753번에 그대로 적용하면 되는 코드입니다.
또한 코드는 나동빈님의 '이것이 코딩테스트다' 를 참고했습니다.