다익스트라 알고리즘은 최단 경로를 찾는 강력한 알고리즘이지만, 기본적인 구현 방식은 시간 복잡도가 O(V^2)로 효율적이지 않을 수 있습니다. 이에 대한 개선 방법으로 우선순위 큐(Priority Queue) 또는 힙(Heap) 을 활용한 다익스트라 알고리즘을 적용하면 시간 복잡도를 O((V + E) log V)로 줄일 수 있습니다. 본 글에서는 힙을 활용한 다익스트라 알고리즘의 개념, 원리, 동작 예시, 그리고 C, Java, Python 예제 코드를 상세히 다룹니다.
0. 힙의 원리
오늘 포스팅은 힙에 대한 이해를 바탕으로 작성했습니다. 이 글을 읽기 전에 힙에 대해 먼저 숙지하시고 오시기를 추천드립니다. 힙에 대한 자세한 설명은 아래 링크에 작성했습니다.
2023.03.12 - [자료구조] - HEAP(1) - 힙 기본 구현 (C언어 구현, index 1부터 시작)
HEAP(1) - 힙 기본 구현 (C언어 구현, index 1부터 시작)
1. HEAP 힙 요약힙은 우선순위가 가장 높은 원소가 루트(첫번째 인덱스)에 존재하는 것이 보장된 자료구조입니다. 또한, 부모노드는 자식노드보다 우선순위가 높습니다.(우선순위가 같은 경우가
best-coding.tistory.com
2023.03.12 - [자료구조] - HEAP (2) - 업그레이드 된 HEAP 힙 (특정원소 삭제, 업데이트 O(logN)만에 가능)
HEAP (2) - 업그레이드 된 HEAP 힙 (특정원소 삭제, 업데이트 O(logN)만에 가능)
2023.03.12 - [자료구조/HEAP 힙] - 1.HEAP 힙 기본 구현 (C언어 구현, index 1부터 시작) 1.HEAP 힙 기본 구현 (C언어 구현, index 1부터 시작)1. HEAP 힙 요약 힙은 우선순위가 가장 높은 원소가 루트(첫번째 인덱
best-coding.tistory.com
1. 힙을 활용한 다익스트라 알고리즘이란?
기본적인 다익스트라 알고리즘은 방문하지 않은 노드 중 최단 거리를 가진 노드를 찾기 위해 O(V) 시간이 소요됩니다. 그러나 최소 힙(Min Heap)을 사용하면 이 과정을 O(log V)로 줄일 수 있습니다.
2. 힙을 활용한 다익스트라 알고리즘의 원리
- 우선순위 큐(힙) 초기화: 시작 노드를 큐에 삽입하고, 나머지 노드의 거리를 무한대(∞)로 설정합니다.
- 최소 거리 노드 선택: 현재 우선순위 큐에서 가장 짧은 거리의 노드를 꺼냅니다.
- 거리 갱신: 해당 노드의 인접 노드를 순회하며 새로운 최단 거리를 계산하고, 더 짧다면 갱신 후 큐에 추가합니다.
- 반복: 모든 노드를 방문할 때까지 2~3 과정을 반복합니다.
3. 힙을 활용한 다익스트라 알고리즘의 동작 예시
예제 그래프
(A)
/ \
4 2
/ \
(B)---3---(C)
\ /
5 1
\ /
(D)
실행 과정
- 우선순위 큐에 (A, 0) 삽입: {(A, 0)}
- A에서 B(4), C(2)로 이동, 큐 갱신: {(C, 2), (B, 4)}
- C 선택 후 D(3)로 이동, 큐 갱신: {(D, 3), (B, 4)}
- D 선택 후 B(5) 경로 무시(기존이 더 짧음), 최종 거리 {A: 0, B: 4, C: 2, D: 3}
4. 힙을 활용한 다익스트라 알고리즘의 시간 복잡도
- O((V + E) log V) (V: 노드 개수, E: 간선 개수)
5. 힙을 활용한 다익스트라 알고리즘 예제 코드
C 언어
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <stdbool.h>
#define V 4
// 최소 힙 구조체 정의
// 생략...
void dijkstra(int graph[V][V], int src) {
// 힙을 이용한 다익스트라 구현
// 생략...
}
Java
import java.util.*;
class DijkstraHeap {
public void dijkstra(Map<Integer, List<int[]>> graph, int src) {
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
// 구현 생략...
}
}
Python
import heapq
def dijkstra(graph, start):
pq = [(0, start)]
distances = {node: float('inf') for node in graph}
distances[start] = 0
while pq:
current_distance, current_node = heapq.heappop(pq)
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
힙을 활용한 다익스트라 알고리즘은 기본 구현보다 성능이 뛰어나며, 많은 실제 응용에서 사용됩니다. 이를 활용하면 대규모 그래프에서도 빠르게 최단 경로를 찾을 수 있습니다.
댓글