1. 개요
- 단일 출발지 최단거리 알고리즘
- 가중 그래프에서 사용할 수 있다.
- 구현에 우선 순위 큐가 사용되며, BFS와 거의 유사하다.
2. 설명
다익스트라 알고리즘의 핵심 개념은, 각 정점 간 최단 거리를 구하면,
결국 출발지를 기준으로 모든 정점에 대한 최단 거리를 구할 수 있다는 것이다.
이는 BFS과 같이 너비 탐색을 하며, 탐색 시간을 줄이기 위해 "우선 순위 큐"를 사용하게 된다.
- 초기 각 정점의 최단 거리는 모두 무한 값으로 설정이 되어야 한다.
- 우선 순위 큐에 들어가는 정보는 (시작점 - 현재 정점 까지의 거리, 현재 정점)과 같다.
- 시작 정점은 우선 순위 큐에 넣을 때 거리 0으로 지정하여 넣는다.
- 시작 정점의 최단 거리는 0 이다.
1) 동작 절차
다익스트라 알고리즘이 동작되는 절차는 아래와 같다.
1. 출발점 정보를 우선 순위 큐에 Push한다.
2. 우선 순위 큐에서 가장 거리 값이 작은 정점 정보를 Pop한다.
3. 현재 탐색중인 정점(Pop한)까지의 거리가 여태 탐색을 하며 찾은 최단 거리보다 큰지 비교한다.
3.1 최단 거리 값보다 크다면, 2번으로 되돌아간다.
4.현재 정점까지의 거리 값 + 연결된 정점과의 거리값을 연결된 정점의 최단 거리 기록과 비교
4.1 기록된 최단 거리보다 작다면, 현재 정점까지의 거리 값 + 연결된 정점의 거리값을 우선 순위 큐에 Push하며, 최단 거리를 갱신 한다.
4.1 기록된 최단 거리보다 크다면, 4번으로 돌아간다.
5. 우선 순위 큐가 다 비어질 때 까지 2 ~ 4 과정을 반복한다.
2) 예시
위와 같은 단순한 그래프가 있다.
1번 정점을 시작점으로 하여 다익스트라 알고리즘을 수행해보자.
동작 1. 출발점 정보를 우선 순위 큐에 Push한다.
동작 2.우선 순위 큐에서 가장 거리 값이 작은 정점 정보를 Pop 한다.
동작 3. 현재 탐색 중인 정점 까지의 거리가 여태 탐색을 하며 찾은 최단 거리보다 큰지 비교한다.
동작 4. 현재 정점까지의 거리 값 + 연결된 정점과의 거리값을 연결된 정점의 최단 거리 기록과 비교
동작 5. 우선 순위 큐가 다 비어질 때 까지 2 ~ 4 과정을 반복한다.
3) 시간 복잡도
(1) 기호
|V| 기호는 그래프 상의 총 정점 개수를 의미한다.
|E| 기호는 그래프 상의 총 간선 개수를 의미한다.
(2) 분석
최초의 다익스트라는 우선 순위 큐를 사용하지 않아 아래와 같은 시간 복잡도를 가진다.
우선 순위 큐를 사용한 다익스트라 알고리즘은 아래와 같은 시간 복잡도를 가진다.
두 가지의 측면으로 시간 복잡도를 분석할 수 있다.
1. 각 정점마다 인접한 간선들을 검사하는 것
다익스트라에서 각 간선은 한 번씩만 검사를 하므로, 아래와 같은 시간 복잡도를 가진다.
2. 우선 순위 큐에서 정점 정보들을 Pop, Push 하는 것
최악의 경우 매 간선마다 우선 순위 큐에 추가 될 수 있다. -> 간선 개수만큼 넣어질 수 있음
위와 같은 상황에서 우선 순위큐에서 Pop, Push하는 작업은 log(|E|)만큼 걸리며, 이 작업은 |E|번 만큼 수행될 수 있다.
1, 2 작업을 합치면
상수는 무시할 수 있으므로
그리고 대부분의 그래프에서 아래와 같은 경우가 성립하므로,
라고 볼 수 있다.
3. 구현
- 문제를 풀 때 시간이 많이 중요한 문제라면, PriorityQueue 대신 HeapQ를 사용하여 시간을 줄일 수 있다.
def dijkstra(s, e):
pq = PriorityQueue()
pq.put((0, s))
dists[s] = 0
while not pq.empty():
cur_dist, cur_v = pq.get()
if cur_dist > dists[cur_v]: continue
for n_dest in v[cur_v]:
n_dist = edge[cur_v][n_dest] + cur_dist
if n_dist < dists[n_dest]:
dists[n_dest] = n_dist
pq.put((n_dist, n_dest))
return dists[e]
4. 관련 문제
본 알고리즘을 응용해 문제 풀이한 것은 아래 링크에서 볼 수 있다.
*본 글에 대한 의견, 피드백은 언제나 환영하며, 감사드립니다.