[알고리즘] 다익스트라(Dijkstra) 알고리즘 : MinHeap 사용
다익스트라(Dijkstra) 알고리즘이란 무엇인지, 단순하게 MinHeap 구조 없이 구현하는 방법은
다익스트라(Dijkstra) 알고리즘이란?에서 확인할 수 있다.
위의 글의 소스코드 처럼 단순하게 다익스트라를 구현할 수 있지만, 이러한 경우 시간복도가 O(N^2)로 형성된다. 그러나 가장 저렴한(min값 인) 경유지를 선택할 때 다익스트라에 Min Heap을 사용하면, 성능을 더 높일 수 있고, 이때 시간복잡도가 O(NlogN)으로 형성된다.
MinHeap은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은, 즉 항상 가장 작은 값이 루트(root)에 존재하는 이진 트리이다.
실제로 여러 다익스트라 문제에서 MinHeap을 사용하지 않고 단순히 구현했을 때 시간 초과가 발생하는 경우를 직면할 수 있다. 단순하게 다익스트라(Dijkstra)를 구현하는 방법을 사용하다가 MinHeap을 사용하는 방법으로 변경하면 헷갈릴 수 있기 때문에(이거 나..😂) 처음부터 MinHeap으로 구현하는 방법을 공부하는 것을 추천한다.
기존 코드는 다음 경유지(가장 작은 비용의 노드)를 찾을 때 for문을 통해 탐색(선형 탐색)한다.
이러한 경우, 정점의 개수가 많은데 간선은 적을 때 치명적일 정도로 비효율적으로 작동할 수 있다.
아래의 코드는 다음 경유지를 찾을 때 힙 구조를 통해 빠르게 찾아낼 수 있다.
이 경우 정점에 비해 간선의 개수가 비정상적으로 적어도 안정적으로 처리할 수 있다.
💻 전체 소스코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int NOT = 999999;
int number = 4; //정점의 개수
vector<vector<pair<int, int>>>map(number); //간선 정보 => map[출발점] = {도착점, 비용}
int result[4]; //최소 비용 전광판
void dijkstra(int start)
{
result[start] = 0;
priority_queue<pair<int, int>>pq;
//heap -> {도착노드, 비용}
//기본적으로 maxHeap이기 때문에 비용을 음수로 바꿔서 넣는다
pq.push({ start,0 });
while (!pq.empty())
{
int now = pq.top().first; //현재노드(경유지)
int dist = -pq.top().second; //짧은 것이 먼저 오도록 음수화
pq.pop();
if (result[now] < dist) continue; //최단거리가 아닌경우, 이미 계산된 경우
for (int i = 0; i < map[now].size(); i++)
{
int next = map[now][i].first; //도착지
//출발지(start)에서 경유지까지 + 경유지에서 도착지(next)까지
int a = dist + map[now][i].second;
//기존의 최소 비용(result) : 경유없이 출발지에서 도착지까지
int b = result[next];
if (a < b)
{
result[next] = a;
pq.push({ next,-a });
}
}
}
}
int main()
{
//기본적으로 연결되지 않은 무한값 NOT 세팅
for (int i = 0; i < number; i++)
result[i] = NOT;
//간선 정보 넣기
map[0].push_back({ 1,50 });
map[0].push_back({ 3,20 });
map[1].push_back({ 2,5 });
map[3].push_back({ 1,10 });
map[3].push_back({ 3,25 });
//다익스트라 알고리즘 실행
dijkstra(0);
for (int i = 0; i < number; i++)
cout << (char)(i + 'A') << " : " << result[i] << endl;
return 0;
}
출력 결과
A : 0
B : 30
C : 35
D : 20
Reference