[알고리즘] 다익스트라 - heapq를 이용한 구현

[알고리즘] 다익스트라(Dijkstra)알고리즘 - 최단 경로와 동작 원리

다익스트라는 현재까지 발견한 거리 중 가장 짧은 정점을 선택하면서 최단 거리를 갱신하는 방식이다.
하지만 정점이 많아질 경우 매번 가장 가까운 정점을 찾는 과정에서 많은 시간이 필요하다.
이를 해결하기 위해 실제 구현에서는
우선순위 큐(Priority Queue)와 힙(Heap) 자료구조를 사용한다.

---

1. 우선순위 큐(Priority Queue)

우선순위 큐는 일반적인 큐와 다르게
먼저 들어온 데이터가 아니라 우선순위가 높은 데이터가 먼저 나오는 자료구조이다.

위 이미지처럼 일반 큐의 경우 먼저 들어온 데이터가 먼저 나오지만
우선순위 큐는 거리 값이 작은 순서대로 처리된다.

---

💡 다익스트라에선 왜 우선순위 큐를 사용할까?

다익스트라 알고리즘은 반복적으로 "현재 가장 거리가 짧은 정점"을 찾아야 한다.
일반 리스트를 사용하면 모든 정점을 확인하면서 가장 작은 값을 직접 찾아야 한다.
하지만 우선 순위 큐를 사용한다면 가장 작은 거리에 있는 정점을 빠르게 찾아낼 수 있기 때문에 우선순위 큐를 사용한다.

---

2. 힙(Heap)을 사용하는 이유

우선순위 큐는 보통 힙 자료구조를 이용해서 구현한다.
힙은 최솟값 또는 최댓값을 빠르게 찾기 위해 사용하는 자료구조이다.
다익스트라에서는 가장 짧은 거리를 가진 정점이 필요하기 때문에 최소 힙(Min Heap)을 사용한다

       (2, B)
       /    \
   (5, C)  (7, D)


꺼내기 → (2, B)

※ Python에서는 heapq 모듈을 이용하여 최소 힙 구조를 사용할 수 있다.

---

3. 다익스트라 시간복잡도

다익스트라는 구현 방법에 따라 시간복잡도가 달라진다.
이때 일반 방식은 가장 작은 값을 찾기 위해 정점을 계속 탐색해야 하지만,
heapq 방식은 힙 구조를 사용하여 탐색 시간을 줄일 수 있다.

구현 방식	시간 복잡도
일반 리스트	O(V²)
heapq 사용	O((V + E) log V)

※ V = 정점(Vertex) 개수
※ E = 간선(Edge) 개수

---

4. 다익스트라 파이썬으로 구현하기

4_1) heapq를 사용하지 않은 다익스트라 구현하기

# '정점': [('연결된 정점', 가중치)]
graph = {
    'A': [('B', 2), ('C', 5)],
    'B': [('D', 1)],
    'C': [('D', 3)],
    'D': []
}


def dijkstra(start):
    # 각 정점까지의 최단 거리 저장
    distance = {node: float('inf') for node in graph}

    # 각 정점까지의 이동 경로 저장
    path = {node: [] for node in graph}

    # 방문한 정점 저장
    visited = []

    # 시작 정점 초기화
    distance[start] = 0
    path[start] = [start]

    # 모든 정점을 확인할 때까지 반복
    while len(visited) < len(graph):
        min_node = None
        # 방문하지 않은 정점 중 거리가 가장 짧은 정점 찾기
        for node in graph:
            if node not in visited:
                if min_node is None:
                    min_node = node
                elif distance[node] < distance[min_node]:
                    min_node = node

        # 현재 정점을 방문했다 처리
        visited.append(min_node)

        # 현재 정점과 연결된 정점 확인
        for next_node, weight in graph[min_node]:
            # 현재 정점을 거쳐 이동했을 때 거리
            new_dist = distance[min_node] + weight
            # 기존 거리보다 짧으면 갱신
            if new_dist < distance[next_node]:
                distance[next_node] = new_dist
                # 이동 경로 갱신
                path[next_node] = path[min_node] + [next_node]
    return distance, path
    
    
distance, path = dijkstra('A')

for node in graph:
    print(f"{node} 거리: {distance[node]}, 경로: {' → '.join(path[node])}")

실행결과▶

---

4_2) heapq를 사용한 다익스트라 구현

import heapq

# '정점': [('연결된 정점', 가중치)]
graph = {
    'A': [('B', 2), ('C', 5)],
    'B': [('D', 1)],
    'C': [('D', 3)],
    'D': []
}

def dijkstra(start):
    # 각 정점까지의 최단 거리 저장
    distance = {node: float('inf') for node in graph}

    # 각 정점까지의 이동 경로 저장
    path = {node: [] for node in graph}

    # 시작 정점 초기화
    distance[start] = 0
    path[start] = [start]

    queue = []

    # 시작 정점을 큐에 추가
    heapq.heappush(queue, (0, start))

    # 큐가 빌 때까지 반복
    while queue:
        # 현재 가장 거리가 짧은 정점 꺼내기
        current_dist, current_node = heapq.heappop(queue)
        # 이미 더 짧은 거리로 처리된 정점이면 무시
        if current_dist > distance[current_node]:
            continue

        # 현재 정점과 연결된 정점 확인
        for next_node, weight in graph[current_node]:
            # 현재 정점을 거쳐 이동했을 때 거리
            new_dist = current_dist + weight
            # 기존 거리보다 짧으면 갱신
            if new_dist < distance[next_node]:
                distance[next_node] = new_dist
                # 이동 경로 갱신
                path[next_node] = path[current_node] + [next_node]

                # 갱신된 정점 우선순위 큐에 추가
                heapq.heappush(queue, (new_dist, next_node))
    return distance, path

distance, path = dijkstra('A')

for node in graph:
    print(f"{node} 거리: {distance[node]}, 경로: {' → '.join(path[node])}")

실행결과▶

---

💡 두가지 방식 비교

일반 리스트의 경우 정점이 적을땐 문제가 없지만 데이터가 많아질수록 속도가 느려진다.
그래서 실제 다익스트라 알고리즘을 구현할 땐 가장 작은 거리를 빠르게 선택하는 heapq방식을 대부분 사용한다.