다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.
알고리즘의 원리는 다음과 같다.
1. 출발 노드를 설정한다(start)
2. 최단 거리 테이블을 초기화한다.([0,0,0,...])
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3번과 4번을 반복한다.
다익스트라 알고리즘을 구현하는 방법 2가지를 소개한다.
방법1. 구현하기 쉽지만 느리게 동작하는 코드
방법2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드
최단 경로 알고리즘을 응용해서 풀 수 있는 고난이도 문제들이 많기 때문에 방법2를 이해하고 정확히 구현할 수 있다면 다양한 고난이도 문제를 만났을 때에도 도움을 얻을 수 있다.
방법1의 간단한 다익스트라 알고리즘의 경우, O()의 시간 복잡도를 가지며, 다익스트라에 의해서 처음 고안되었던 알고리즘이다.
처음에 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언한다. 이후에 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차탐색)한다.
시간복잡도가 인 이유는 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문이다. 전체 노드의 개수가 5,000개 이하라면 이 코드로 문제를 풀 수 있다. 하지만 노드의 개수가 10,000개가 넘어가는 문제라면 이 코드로는 문제를 해결하기 어렵다.
방법2의 개선된 다익스트라 알고리즘에 대해 알아보자. 이 방법을 구현하여 이용하면 O(ElogV)를 보장하여 해결할 수 있다.
여기서 V는 노드의 개수이고, E는 간선의 개수이다.
간단한 다익스트라 알고리즘은 '최단 거리가 가장 짧은 노드'를 찾기 위해서, 매번 최단 거리 테이블을 선형적으로(모든 원소를 앞에서부터 하나씩) 탐색해야 했다. 이 과정에서만 O(V)의 시간이 소요된다.
이 개선된 알고리즘에서는 단순히 선형적으로 찾지 않고 힙자료구조를 이용한다. 힙 자료구조를 이용하게 되면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드롭터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있게 된다.
힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나이다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다. 파이썬에서 우선순위 큐를 구현할 때 PriorityQueue 혹은 heapq를 사용할 수 있는데, 이 두 라이브러리는 모두 우선순위 큐 기능을 지원하지만 일단 heapq를 사용하도록 한다. 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위 설정
파이썬 라이브러리에서는 기본적으로 최소 힙 구조를 이용하는데 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선하여 방문하므로 최소 힙 구조를 기반으로 하는 파이썬의 우선순위 큐 라이브러리를 그대로 사용하면 적절하다.
우선순위 큐를 이용해서 시작 노드로부터 '거리'가 짧은 노드 순서대로 큐에서 나올 수 있도록 다익스트라 알고리즘을 작성하면 된다.
우선순위 큐를 적용해도 다익스트라 알고리즘이 동작하는 기본원리는 동일하고, 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다고 생각하면 된다.
출처 : https://www.hanbit.co.kr/store/books/look.php?p_code=B8945183661
댓글