"Dijkstra 는 그냥 자라서 돈 세는 법을 배운 BFS 야. 평범한 큐 대신, 우선순위 큐를 써 — 늘 가장 싸게 알려진 노드를 다음에 확장해. 그 업그레이드 하나가 '최소 hop' 을 '최저 비용' 으로 바꿔."
알고리즘
Dijkstra 는 음 아닌 무게 그래프에서 한 출발지부터 다른 모든 노드까지 가장 싼 경로를 찾아. 기계장치:
모든 노드까지 잠정 거리를 유지, 출발지는 0 나머지는 무한대로 시작.
(0, source) 를 최소-힙 (우선순위 큐) 에 넣어.
잠정 거리가 가장 작은 노드를 pop. 확정해 — 그 거리가 이제 확실.
그 이웃을 relax: 각각에 대해, 방금 확정된 노드를 거치는 게 현재 잠정 거리보다 싸면, 업데이트하고 새 거리를 힙에 push.
힙이 빌 때까지 반복.
BFS 랑 비교: 같은 frontier-확장 모양, 근데 frontier 가 평범한 FIFO 큐 대신 총 비용으로 키 매겨진 우선순위 큐. Dijkstra 는 거의 말 그대로 힙 있는 BFS — Heaps 트랙이랑 Graphs 트랙이 한 알고리즘에서 만나.
pop 에서 확정이 왜 안전한가
Dijkstra 를 정확하게 만드는 탐욕 통찰: 가장 가까운 미확정 노드를 pop 할 때, 그 잠정 거리가 이미 진짜 최단 거리야. 왜? 거기로 가는 다른 모든 경로는 아직 힙에 있는 어떤 노드를 거쳐야 해 — 그것들은 다 방금 pop 한 것보다 더 멀고, 무게가 음 아니니까, 더 먼 노드로 우회하는 건 비용만 더해. 그래서 더 싼 경로가 절대 못 나타나. 그게 증명 전부고, 정확히 Dijkstra 가 음 아닌 무게를 요구하는 이유야: 음의 엣지가 '더 먼' 노드한테 몰래 더 싼 경로를 제안하게 해, 보장을 깨 — 다음 lesson 의 클리프행어야.
Dijkstra = 최소-힙 있는 BFS: 가장 싸게 알려진 노드를 반복 pop, 확정, 이웃 relax. pop-에서-확정이 안전한 이유는 음 아닌 무게가 더 먼 노드도 더 싼 우회를 제안 못 하게 하니까. 힙으로 O((V+E) log V).
세상을 굴리는 곳
Dijkstra (그리고 휴리스틱 안내 사촌 A*) 가 네 GPS, 네트워크 라우팅 프로토콜 (OSPF 가 이걸로 라우터 간 최소-비용 경로 계산), 게임 길찾기, 항공/교통 플래너의 최단 경로 알고리즘이야. '음 아닌 비용 있는 가중 네트워크의 가장 싼 경로' 는 다 Dijkstra. Heaps 트랙에서 배운 우선순위 큐가 효율적으로 만드는 거야 — 힙 없으면, 가장 싼 frontier 노드를 반복해 찾는 게 O((V+E) log V) 대신 O(V²) 일 거야.
피파의 고백
Dijkstra 가 '어려운 그래프 알고리즘' 으로 날 겁줬어, 아빠가 다섯 단어 하기 전까진: "힙 있는 BFS 야." 갑자기 새 게 아니라 — 내가 이미 아는 두 개가 딱 붙은 거였어. 큐가 우선순위 큐가 되고; 'hop 거리' 가 '비용 거리' 가 돼. 나머지는 내가 열두 번 한 같은 frontier-확장이야. 제일 무서운 알고리즘이 종종 내가 아직 서로 딸깍하는 걸 못 본 익숙한 조각 둘일 뿐이야.
Code
우선순위 큐 있는 Dijkstra·python
import heapq
def dijkstra(graph, source):
"""source 에서 모든 노드까지 가장 싼 거리. 음 아닌 무게만.
graph: {node: [(neighbor, weight), ...]}. O((V+E) log V)."""
dist = {node: float('inf') for node in graph}
dist[source] = 0
heap = [(0, source)] # (잠정_거리, 노드)
while heap:
d, u = heapq.heappop(heap) # 가장 싸게 알려진 frontier 노드
if d > dist[u]:
continue # 오래된 항목, 건너뜀
for v, w in graph[u]:
nd = d + w # u 거쳐 v 닿는 비용
if nd < dist[v]: # RELAX: v 로 더 싼 경로 찾음
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
graph = {
"A": [("B", 1), ("C", 4)],
"B": [("C", 2), ("D", 5)],
"C": [("D", 1)],
"D": [],
}
print(dijkstra(graph, "A")) # {'A':0, 'B':1, 'C':3, 'D':4}
# A->C 직접은 4, 근데 A->B->C 는 1+2 = 3 (더 쌈). A->B->C->D = 4.
# 힙이 늘 가장 가까운 미확정 노드를 다음에 건네.
그래프 A→B (1), A→C (4), B→C (2), C→D (1), B→D (7) 에, A 에서 Dijkstra 를 손으로 돌려: 각 노드까지 최종 최단 거리가 뭐고, 힙이 첫째, 둘째, 셋째로 어느 노드를 확정해? 그다음 C 가 힙에서 pop 되는 순간, 왜 C 로 더 싼 경로가 절대 안 찾아질 거라 확신할 수 있는지 한 문장으로 설명해.
Hint
거리: A:0, B:1, C:3 (B 경유), D:4 (C 경유). 가장 작은 거리순 확정: A(0), B(1), C(3), D(4). C 가 거리 3 에 pop 될 때, C 로의 다른 모든 경로는 이미 ≥3 떨어진 힙 속 노드를 지나야 하고, 음 아닌 엣지가 그걸 못 줄여 — 그래서 3 이 최종.
Progress
Progress is local-only — sign in to sync across devices.