[알고리즘] 우선순위 큐를 이용한 다익스트라(Dijkstra), 최단 경로 찾기

가중치 그래프에서 단일 출발점의 최단 경로를 구하는 문제

 

조건

• 출발점에서 각 노드까지의 최단 경로를 구할 때 사용
• 음수 가중치를 포함하면 안됨 → 벨만-포드 알고리즘 사용

 

 

동작 과정

# 그래프 예시

   A --(5)-- B --(1)-- C
   |       / |         |
  (2)    (2) (5)      (1)
   |     /      \      |
   D --(3)-- E --(3)-- F

 

 

1. 초기화: 시작 노드의 거리는 0, 나머지 노드는 ∞로 초기화

노드	A	B	C	D	E	F
거리	0	∞	∞	∞	∞	∞

 

 

2. 노드 선택: 방문하지 않은 노드 중 최소 거리를 가지는 노드 선택  → `heapq.heappop`

노드	A	B	C	D	E	F
거리	0	5	∞	2	∞	∞

< A → D, A → B 거리 갱신>

 

 

3. 거리 갱신: 선택된 노드의 인접 노드들을 탐색해 현재 거리 + 간선의 가중치가 인접 노드의 기존 거리보다 작다면 더 짧은 경로가 발견된 것이므로 갱신 →  `heapq.heappush`

노드	A	B	C	D	E	F
거리	0	5	∞	2	5	∞

< 최소 거리인 D를 선택해 D → E 업데이트 >

 

 

4. 반복: 모든 노드를 방문하거나, 우선순위 큐가 빌 때까지 반복

노드	A	B	C	D	E	F
거리	0	5	6	2	5	∞

< 그 다음 최소 거리인 B를 선택해 B → C, B → E 업데이트 > 이 과정 반복

 

 

5. 최단 경로 추출

 

 

구현

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    pq = [(0, start)] # (현재까지의 거리, 노드)
    
    while pq:
        dist, node = heapq.heappop(pq)
        
        if dist > distances[node]:
            continue
        
        for neighbor, weight in graph[node]:
            distance = dist + weight
            
            if distance < distance[neighbor]:
                distance[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
                
    return distances

 

 

시간 복잡도

• O(ElogV) [E: 간선의 수, V: 노드의 수]