단원 24: 다익스트라 (Dijkstra's Algorithm)

단일 시작 최단 경로의 표준 알고리즘. heapq 기반 정형 구현을 익힙니다.

다익스트라최단 경로heapq

소요 시간

⏱ 약 1시간

난이도

📊 고급

선수 조건

🎯 BFS·heap

결과물

단일 시작 최단 경로의 표준 알고리즘. heapq 기반 정형 구현을 익힙니다.

이 강의에서 배우는 것

1다익스트라 알고리즘의 원리(그리디 + 우선순위 큐)를 이해하고 직접 구현한다.
2경로 복원(path reconstruction)을 추가하여 실제 경로를 출력할 수 있다.
3음수 가중치가 있을 때 왜 실패하는지 이해하고, 벨만-포드 알고리즘을 대안으로 적용한다.

개요

💡

**Part 07 — 고급 그래프** | 이전: [23_유니온_파인드](../23_유니온_파인드/) | 다음: [25_플로이드_워셜](../25_플로이드_워셜/)

소개

다익스트라 알고리즘은 **단일 출발점(Single-Source) 최단 경로** 문제를 해결하는 대표적인 그리디 알고리즘입니다. 가중치가 있는 방향/무방향 그래프에서, 출발 노드로부터 나머지 모든 노드까지의 최단 거리를 구합니다.

**조건**: 모든 간선 가중치 ≥ 0
**시간 복잡도**: O((V + E) log V) — 우선순위 큐(힙) 사용
**공간 복잡도**: O(V + E)

코딩 테스트에서 가장 자주 등장하는 최단 경로 알고리즘이므로 완벽히 익혀야 합니다.

핵심 개념

알고리즘 동작 원리

text

1. dist[src] = 0, 나머지 dist[v] = INF 로 초기화
2. 최소 힙(min-heap)에 (0, src) 삽입
3. 힙이 빌 때까지:
   a. (d, u) = heappop(heap)
   b. d > dist[u] 이면 스킵 (lazy deletion)
   c. u의 인접 노드 v에 대해:
      new_dist = d + weight(u, v)
      if new_dist < dist[v]:
          dist[v] = new_dist
          heappush(heap, (new_dist, v))

**핵심 불변식**: 힙에서 꺼낸 노드의 최단 거리는 확정됩니다. 이는 모든 간선 가중치가 0 이상일 때만 보장됩니다.

복잡도 비교

구현 방식	시간 복잡도	공간 복잡도	비고
배열 (naive)	O(V²)	O(V)	밀집 그래프에 유리
이진 힙 (heapq)	O((V+E) log V)	O(V+E)	희소 그래프 표준
피보나치 힙	O(E + V log V)	O(V+E)	이론적 최적, 구현 복잡

예제 그래프 (단계별 추적)

text

        2         5
   (1)------(2)------(4)
    |      / |        |
   1|    3/  |4       |6
    |  /     |        |
   (3)------(5)------(6)
        1         2

출발: 노드 1

단계	확정 노드	dist[2]	dist[3]	dist[4]	dist[5]	dist[6]
초기	—	INF	INF	INF	INF	INF
1	1	2	1	INF	INF	INF
2	3	2	1	INF	2	INF
3	2	2	1	7	2	INF
4	5	2	1	7	2	4
5	6	2	1	7	2	4
6	4	2	1	7	2	4

**최종 최단 거리**: 1→1=0, 1→2=2, 1→3=1, 1→4=7, 1→5=2, 1→6=4

Relaxation (완화) 연산

python

# 핵심 연산: dist[v]를 더 작은 값으로 갱신
if dist[u] + weight(u, v) < dist[v]:
    dist[v] = dist[u] + weight(u, v)
    heappush(heap, (dist[v], v))

Lazy Deletion (지연 삭제)

파이썬 heapq는 원소 삭제가 불가능합니다. 따라서 힙에서 꺼냈을 때 `d > dist[u]`이면 이미 처리된 노드이므로 스킵합니다.

python

d, u = heapq.heappop(heap)
if d > dist[u]:   # 이미 더 짧은 경로로 처리됨
    continue

예제로 보기

파일	설명	핵심 개념
[src/01_dijkstra_basic.py](src/01_dijkstra_basic.py)	기본 다익스트라 구현	heapq, dist 배열
[src/02_dijkstra_path.py](src/02_dijkstra_path.py)	경로 복원 포함	prev 배열, 역추적
[src/03_dijkstra_negative.py](src/03_dijkstra_negative.py)	음수 가중치 실패 증명 + 벨만-포드	벨만-포드 O(VE)
[src/04_dijkstra_applications.py](src/04_dijkstra_applications.py)	K번째 최단 경로, 상태 그래프	변형 다익스트라

자주 하는 실수

**음수 가중치 사용**: 다익스트라는 음수 간선에서 오답을 냅니다. 음수가 있으면 벨만-포드(O(VE)) 또는 SPFA를 사용하세요.
**Lazy deletion 누락**: 힙에서 꺼낸 후 `if d > dist[u]: continue` 체크를 빠뜨리면 중복 처리로 오류가 발생합니다.
**0-indexed vs 1-indexed 혼동**: 백준 문제는 보통 1-indexed입니다. `dist = [INF] * (V + 1)`로 선언하세요.
**INF 값 설정 오류**: `float('inf')` 또는 `10**18`을 사용합니다. `10**9`는 가중치 × 노드 수에서 오버플로(Python에서는 문제 없지만 로직 오류 가능)가 날 수 있습니다.
**무방향 그래프에서 단방향 입력**: 무방향 그래프는 `graph[u].append((v, w))`와 `graph[v].append((u, w))`를 **모두** 추가해야 합니다.

정리

text

다익스트라 알고리즘 요약
━━━━━━━━━━━━━━━━━━━━━
적용 조건  : 비음수 가중치 그래프
시간 복잡도 : O((V + E) log V)
공간 복잡도 : O(V + E)
핵심 자료구조 : 최소 힙 (heapq)
핵심 연산   : Relaxation + Lazy Deletion
경로 복원   : prev[] 배열로 역추적
음수 간선   : 벨만-포드 사용

직접 해 보기

아래 그래프에서 노드 1을 출발점으로 다익스트라를 손으로 추적하세요. ``` 1 --3-- 2 --1-- 3 | | 5 2 | | 4 ------4------ 5 ```
`src/01_dijkstra_basic.py`를 수정하여 **역방향 그래프**에서도 다익스트라가 동작하도록 만드세요.
`src/02_dijkstra_path.py`를 활용하여 백준 1753번을 풀어 보세요.

과제

→ [homework/README.md](homework/README.md)

예제 코드 / 강의 자료

전체 강의 자료와 예제 코드는 GitHub에서 자유롭게 받아볼 수 있습니다.

GitHub에서 보기 ↗