출처: [이것이 취업을 위한 코딩테스트다 - 나동빈 저](https://ridibooks.com/books/443000825
배너: godori님이 만드신 배너 메이커 활용
최단 경로 알고리즘
- 가장 짧은 경로를 찾는 알고리즘
- 다양한 문제 상황
- 한 지점에서 다른 한 지점까지의 최단 경로
- 한 지점에서 다른 모든 지점까지의 최단 경로
- 모든 지점에서 다른 모든 지점까지의 최단 경로
- 각 지점은 그래프에서 노드로 표현
- 노드의 개수는 V로 표현
- 지점 간 연결된 도로는 그래프에서 간선으로 표현
- 간선의 개수는 E로 표현
다익스트라(Dikjstra) 최단 경로 알고리즘
- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산
- 음(Negative)의 간선이 없을 때 정상적으로 동작함
- 현실 세계의 도로(간선)는 음의 간선으로 표현되지 안음
- 그리디 알고리즘으로 분류됨
- 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하기 때문
알고리즘 동작 과정
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해서 최단 거리 테이블 갱신
- 위 과정에서 3번과 4번을 반복
다익스트라 알고리즘의 특징
- 그리디 알고리즘: 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정 반복
- 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.
- 한 단계당 하나의 노드에 대한 최단 거리를 fix하는 것
- 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장됨
- 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야 함
간단하지만 느린 구현 방법
- 매 단계마다 1차원 테이블의 모든 원소를 확인(순차 탐색)하는 방식으로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
성능 분석
- 총 O(V) 번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 함
- 따라서 전체 시간 복잡도는 O(V²)이다.
- 일반적으로 코딩테스트의 최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 이 코드로도 문제를 해결할 수 있다.
- 하지만 노드의 개수가 10,000개를 넘어가는 문제라면 보다 빠른 구현 방법이 필요하다.
개선된 구현 방법
우선순위 큐(Priority Queue)
- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
- ex) 여러 개의 물건 데이터를 자료 구조에 넣었다가, 가치가 높은 물건 데이터부터 꺼내서 확인하는 경우에 사용할 수 있다.
- Python ,C++, Java를 포함한 대부분의 프로그래밍 언어에서 표준 라이브러리 형태로 지원한다.
힙(Heap)
- 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나
- 최소 힙(Min Heap)과 최대 힙(Max Heap)이 있다.
- 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용된다.
| 우선순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
|---|---|---|
| 리스트 | O(1) | O(N) |
| 힙(Heap) | O(logN) | O(logN) |
구현 방법
- 단계마다 힙(Heap) 자료구조를 이용해서 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 다익스트라 알고리즘이 작동하는 기본 원리는 동일
- 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이용한다는 점이 다르다.
- 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용한다.
성능 분석
- 힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)
- 우선순위 큐에서 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V 이상의 횟수로는 처리되지 않는다.
- 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대로 간선의 개수(E)만큼 연산이 수행될 수 있다.
- 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다.
- 시간 복잡도를 O(ElogE)로 판단할 수 있다.
- 두 노드 쌍 사이에서 중복 간선을 포함하지 않는 경우(두 노드 사이에 오는 간선, 가는 간선 이 2개까지만 존재 가능)에 이를 O(ElogV)로 정리할 수 있다.
- E <= V²
- O(ElogE) -> O(ElogV²) -> O(2ElogV) -> O(ElogV)
- 이 방법을 사용할 경우 통상적으로 간선의 개수가 10만 개, 20만 개, 그리고 노드의 개수도 만 개 이상으로 많아진다고 하더라도 대개 1초 안쪽의 시간으로 출발 노드부터 다른 모든 노드까지의 최단거리를 구할 수 있다.
