[자료구조] Heap의 응용 - 다익스트라 알고리즘 (Dijkstra Algorithm)
Heap 응용 - 다익스트라 알고리즘
Directed Path 혹은 Undirected path 가 주어졌을 때, 최단 경로를 구하고자 합니다.
이때 사용되는 알고리즘이 다익스트라 알고리즘 (Dijkstra Algorithm) 입니다.
다익스트라 알고리즘을 구현하는 방법은 여러가지가 있지만, 가장 효율적으로 구하기 위해
우리는 Heap 자료구조를 이용합니다.
assumption
- Red set 과 Blue set 을 설정합니다.
- Red set : real shortest path is known
- Blue set : shortest path using only red nodes in known
- repeat : move one node in blue set into red sets
초기 설정
Red set 에는 오직 source node 만을 포함하고 있습니다.
all other nodes : 만약 소스 노드에서 바로 접근할 수 있다면 경로는 그 가중치가 됩니다. 바로 접근할 수 없다면 경로는 무한대로 설정합니다.
주어진 정보들을 고려하여 최단 경로를 최신화 합니다.
at each round
Blue set 의 노드들 중 가장 짧은 경로를 가지고 있는 노드(v) 를 찾은 뒤, v 노드를 Red set 에 포함시킵니다.
v 노드가 Red set 에 들어갔으므로 v에서 바로 연결된 노드들을 최신화 합니다.
다익스트라 알고리즘을 구현할 때 Heap 자료구조에는 Blue set 의 노드들이 들어가 있습니다.
그러므로 Heap 자료구조 특성으로 인해 가중치가 가장 작은 Blue 노드들을 얻을 수 있기 때문에, 다익스트라 알고리즘은 Heap 자료구조를 이용합니다.
Heap 자료구조를 사용하지 않은 다익스트라 알고리즘은 최단경로를 O(NM) 의 시간복잡도로 구할 수 있습니다.
하지만 Heap 자료구조를 사용한 다익스트라 알고리즘은 최단경로를 O((N+M)logM) 의 시간복잡도로 구할 수 있습니다.
해당 알고리즘의 증명 과 구현은 나중에 알고리즘 Part 에서 포스팅하도록 하겠습니다