[알고리즘] 다익스트라 - 선형 탐색, 우선순위 큐

다익스트라 알고리즘 (Dijkstra's algorithm)

 

특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘

 

다익스트라 알고리즘은 음의 간선이 있는 그래프에서는 사용이 불가능하지만 현실 세계에서는 음의 간선이 존재하지 않으므로 현실 세계에서 쓰기에 적합하다.

 

다익스트라는 그리디로 분류된다. 매상황 가장 비용이 적은 노드를 선택해 임의의 과정을 반복해준다.

 

동작 과정

 

1. 출발 노드를 설정해준다.

 

2. 최단거리 테이블을 초기화한다.

 

3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다.

 

4. 해당 노드에서 다른 노드로 가는 최단 거리 테이블을 갱신해준다.

 

5. 3번과 4번을 반복한다.

 

알고리즘 사례

 

위와 같은 그래프가 있다고 하자 출발점은 0이다.

 

이제부터 0번 노드부터 모든 노드로의 최단경로를 다익스트라 알고리즘으로 구해보자. 

 

시작 할 때는 자기 자신의 노드를 제외한 모든 노드로 가는 길을 무한대로 설정해준다, 자기 자신으로 가는 최단 거리는 0이므로 0으로 설정한다.

 

0번 노드부터 시작하면,

 

 

1번 노드로 가는 거리 4 < ∞ 이므로 갱신해준다.

2번 노드로 가는 거리 3 < ∞ 이므로 갱신해준다.

3번 노드로 가는 거리 5 < ∞ 이므로 갱신해준다.

 

나머지에 대한 데이터는 없으므로 갱신하지 않는다.

 

방문하지 않은 노드 중에 가장 최단 거리가 적은 노드는 2번이므로 2번 노드부터 탐색을 시작한다.

 

3번 노드로 가는 거리 3 + 1 < 5 이므로 갱신해준다.

4번 노드로 가는 거리 3 + 8 < ∞ 이므로 갱신해준다.

5번 노드로 가는 거리 3 + 3 < ∞ 이므로 갱신해준다.

 

방문하지 않은 노드 중에 최단 거리가 가장 적은 노드는 1과 3이다. 1번 노드를 먼저 탐색해준다

 

5번 노드로 가는 거리 4 + 1 < 6 이므로 갱신해준다.

 

방문하지 않은 노드 중에 최단 거리가 가장 적은 노드는 3이므로 3번 노드를 탐색해준다.

 

4번 노드로 가는 거리 5 + 4 < 11 이므로 갱신해준다.

 

방문하지 않은 노드 중에 최단 거리가 가장 적은 노드는 5번이므로 5번 노드를 탐색해준다.

 

4번 노드로 가는 거리 5 + 2 < 9 이므로 갱신해준다.

 

4번 노드 빼고 모든 노드를 방문했으므로 4번 노드를 방문해준다.

 

모든 노드를 방문했으므로 알고리즘을 종료한다.

 

 

이 방식으로 최단거리가 가장 짧은 노드를 선형탐색으로 찾는다면 노드의 개수만큼 시간복잡도는 제곱이 되기 때문에 노드가 어느정도 높은 값이면 시간복잡도는 높아질 수밖에 없다.

 

그렇기 때문에 여기서 우선순위 큐를 써주면 시간복잡도를 낮출 수 있다.

 

우선순위 큐(priority queue)

 

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조.

 

힙(heap)

 

우선순위 큐 구현을 위해 이용하는 자료구조 중 하나이다.

 

최소 힙과 최대 힙이 있는데 기본적으로 c++에서는 최대힙을 사용하므로 다익스트라를 구현해줄 때는 최소힙으로 바꾸어서 사용해야한다.

 

우선순위 큐를 이용한 알고리즘 사례

 

갱신하는 과정은 위의 사례를 참고하길 바란다.

 

 

처음 방문하는 노드의 최단 거리와 노드 번호를 우선순위 큐에 입력해준다.

 

 

최단 거리가 갱신이 된 노드의 최단 거리와 노드 번호를 우선 순위 큐에 입력한다.

(이 때, 거리가 적은 순대로 정렬해주는 우선순위 큐여야만 한다.)

 

 

우선 순위 큐에 있는 노드의 거리가 현재 배열에 입력 되어 있는 거리보다 클 경우 스킵해준다.

 

위의 경우처럼 노드 3까지의 최단 거리가 4인데 우선순위 큐에 맨 위에 있는 (거리 5, 노드 3)은 최단 거리보다 크므로 스킵해준다.

 

 

우선순위 큐를 이용해서 다익스트라 알고리즘을 구현하면 선형탐색으로 구현하는 것보다 훨씬 시간 복잡도를 아낄 수 있다.

 

선형 탐색으로 구현한 다익스트라 VS 우선순위 큐로 구현한 다익스트라

 

선형 탐색으로 구현한 다익스트라 알고리즘은 총 $O(V)$번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야한다. 

 

따라서 전체 시간복잡도는 $O(V^2)$이다.

 

우선 순위 큐(힙)를 이용해 구현한 다익스트라 알고리즘의 시간 복잡도는 $O(E \mathrm{log} V)$이다.

 

직관적으로 전체 과정이 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다.

 

시간 복잡도를 $O(E \mathrm{log} E)$로 판단할 수 있다.

 

중복 간선을 포함하지 않는 경우는 $O(E \mathrm{log} V)$로 정리할 수 있다.

 

 

https://kimmessi.tistory.com/181?category=833468 

[다익스트라] BOJ 1916 최소비용 구하기 (C++)

https://kimmessi.tistory.com/182

[다익스트라] BOJ 1504 특정한 최단 경로 (C++)

 

https://kimmessi.tistory.com/180

[다익스트라] BOJ 1753 최단경로 (C++)

 

위 방법대로 다익스트라 알고리즘을 이용해 풀이한 문제들이다.