1. 다익스트라 알고리즘 (Dijkstra Algorithm)
ㅇ 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 데 사용
- 가중치가 있는 그래프에서 동작하며, 가중치가 음수가 아닌 경우에 만 올바른 결과를 보장
※ Dijkstra가 1956년에 개발하고, 1959년에 발표
- Edsger W. Dijkstra (1930~2002) : 네덜란드 과학자
2. 다익스트라 알고리즘의 특징
ㅇ 그래프 상의 특징
- 간선에서 음의 가중치를 허용 않음
- 순환 포함 허용
- 기본적으로, 탐욕 알고리즘에 속함
. 매번 가장 비용이 적은 노드를 선택하려고 함
- 그래프의 간선 가중치가 실시간으로 변경되는 경우, 즉각적인 업데이트가 어려움
ㅇ 방식 상의 특징
- 첫 출발 정점을 기준으로 함
- 연이어, 연결된 정점들을 추가해가며, 최단 거리를 갱신해 감
- 항상, 각 노드에 대해, 현재까지의 최단 거리 정보를 최단 경로 테이블(1차원 리스트)에 저장
- 이 최단 경로 테이블을 계속 갱신해 나감
- 결국, 시작 정점에서 모든 다른 정점까지의 최단 경로들은, 신장 트리를 형성하게 됨
3. 다익스트라 알고리즘의 입력,출력 및 상태 자료구조
ㅇ 입력, 출력
- 입력 : 그래프 (노드 개수, 간선 개수 등), 시작 노드
- 출력 : 통상, 출력은, 편의상, (각 노드별로) 최단 경로 길이가 담긴 테이블 1개 정도 만 요구함
. (각 노드별로) 최단 경로 길이 테이블
.. 각 노드별로, 시작 ~ 해당 노드까지, 최단 경로 상의 가중치들의 합 (최단 경로 길이)
. 때론 추가적으로, (각 노드별로) 각 노드까지 최단 경로를 열거할 수 있는 힌트 등
.. 최단 경로 상에 있는, 출발 직후 노드 (선행 노드) 또는 도착 직전 노드 (후행 노드) 등
ㅇ 상태 유지 자료구조
- 노드 집합
. 최단 경로를 찾은 노드 집합 : (점점 커짐)
.. 선택된(이미 방문한) 노드들의 집합으로, 처음에는 공집합으로 초기화됨
.. 이 상태 집합을 유지하는 이유는, 순환 방지를 위함임
- 최단 경로 길이 테이블/배열 : (이 자료가 출력됨)
. 각 노드별로, 노드 집합에 있는 정점 만 거쳐,
. 현재까지의 최단 경로 길이(최단 거리)를 갱신 저장해 두기 위함
4. 다익스트라 알고리즘의 단계별 표현
ㅇ 알고리즘 단계 : (단순한 방법 : 1956년 당시 Dijkstra가 제안한 방법)
* (초기화 단계)
- ① `최단 경로 길이 배열(테이블)`을 초기화함 : (노드별 거리값 갱신을 위함)
. 초기화 : (모든 노드에 하나의 거리값을 할당함)
.. 시작 노드의 경로 길이 가중치는, 영(0) 적용
.. 나머지 모든 다른 노드의 경로 길이 가중치 값은, 무한대(∞) 적용
.. 무한대 적용 이유는, 도달 못할 노드도 있기 때문임
. 최단 경로 길이 배열(테이블)의 준비 및 초기화
.. 각 노드별로, 현재까지의 최단 경로 길이(최단 거리, 거리값)를 갱신 저장해 두기 위함
- ② `이미 방문한 노드들의 집합`을 만듬 : (순환 방지를 위함)
. 초기화 : 처음에는 공집합 으로 함
.. 모든 원소들에 False 또는 Null 적용 (미방문 처리)
.. 시작 노드를 현재 노드로 설정
* (반복 단계) : (현재 경유 거리와 인접 기 저장 거리들을 비교, 최단 거리값 조정)
- ③ `순차 탐색`
. 미 방문 노드 마다, 인접 노드들 중 가장 작은 가중치 링크를 거치는 노드를 탐색 선택
- ④ 선택된 현재 노드의 거리와 인접 방문 노드의 기 저장된 거리들 중 가장 잛은 것 선택
. 현재 노드 경유 거리와 기존 저장된 거리를 비교하여, 더 짧은 거리이면 업데이트
* (모든 노드 선택까지, 매 반복 단계 마다, 현재 노드에 대한, 최단 거리가 확정됨)
ㅇ 알고리즘 단계 : (개선된 방법)
- ① 최단 경로 길이 배열(테이블)을 초기화함
. 위와 상동
- ② 순환 방지를 위해, 이미 방문한 노드들의 집합을 만듬
. 위와 상동
- ③ 정점 방문 큐(by 우선순위 큐)를 만들어 감
. 우선 그곳에 시작 노드를 넣어 둠
. 우선순위 큐를 사용함
. 현 노드에서 시작 노드까지 경로 길이가 짧을수록, 높은 우선순위를 줌
- ④ 현재 노드로부터 미 방문 노드들 모두를 방문
- ⑤ 방문 노드는 방문했음을 알리는 마크 표시
- ⑥ 노드 방문 큐가 빌 때까지 단계 ④부터 되풀이
5. 다익스트라 알고리즘의 시간복잡도
ㅇ 단순한 방법 : O(V2)
- 모든 노드들을, 매번 최단거리를 선형 탐색 해야 하고,
- 현재 노드과 연결된 노드들을, 매번 일일이 확인해야 함
ㅇ 개선된 방법 : O(E log V)
- 여기서, V : 노드 갯수, E : 간선 갯수