[Python] 우선순위 큐를 이용한 다익스트라 알고리즘 구현

다익스트라 알고리즘은 가중치 그래프에서 시작점과 도착점이 주어졌을 때, 

최단 경로(shortest path)를 찾아주는 알고리즘이다.

• 완전 탐색을 이용하면 많은 비용이 소모된다.
• 이를 효율적으로 해결하기 위해 다익스트라 알고리즘을 사용한다.
  • 방문 가능한 노드들 중에서 가장 비용이 작은 노드를 선택하여 방문한다.
  • 즉, 우선순위가 높은 곳을 먼저 방문한다.

---

우선순위 큐와의 관계

• 우선순위 큐를 사용하면 원하는 조건에 따라 (min 또는 max) 자동 정렬이 이루어진다.
• 이를 통해 다익스트라 알고리즘의 구현이 훨씬 간편해진다.
• 중요한 점: 우선순위가 높은 데이터가 항상 큐의 맨 앞에 위치한다.

 

# 간단한 수도 코드

1. 우선순위 큐에 시작노드 추가
    2. 우선순위가 가장 높은 노드 추출
    3. 방문여부 확인
        4. 비용 업데이트
        5. 현재 노드와 연결된 노드 우선순위 큐에 추가
6. 목적지에 기록된 비용 반환

 

 

---

실제 코드 구현

 

1. 인접 리스트를 이용하여 표현한 가중치 그래프

graph = {
    1: [(2, 2), (1, 4)],
    2: [(1, 3), (9, 5), (6, 6)],
    3: [(4, 6)],
    4: [(3, 3), (5, 7)],
    5: [(1, 8)],
    6: [(3, 5)],
    7: [(7, 6), (9, 8)],
    8: []
}

 

 

2. 다익스트라 알고리즘을 이용하여 최단 경로 구하기

import sys
import heapq

def dijkstra(graph, start_v, dest_v):
    inf = sys.maxsize
    distances = [inf] * (len(graph)+1)
    # 시작점 예약하기
    # 시작점: 1번노드 / 시작 비용: 0
    pq = []
    heapq.heappush(pq, (0, start_v))
    distances[start_v] = 0

    while pq:
        cur_d, cur_v = heapq.heappop(pq)
        for next_cost, next_v in graph[cur_v]:
            next_d = cur_d + next_cost
            if next_d < distances[next_v]:
                heapq.heappush(pq,(next_d, next_v))
                distances[next_v] = next_d
    return distances[dest_v]

dijkstra(graph, 1, 8)

 

템플릿처럼 알아두어야할 코드!

 

 

Ref. 개발남노씨 - 코딩테스트 [All IN ONE]