"Dijkstra는 자라서 돈 세는 법을 배운 BFS라고 보면 돼. 평범한 큐 대신 우선순위 큐를 써서 언제나 지금까지 알려진 가장 싼 노드를 다음에 펼치지. 이 업그레이드 하나가 '가장 적게 거치기'를 '가장 싸게 가기'로 바꿔."
알고리즘
Dijkstra는 가중치가 0 이상인 그래프에서 출발지 하나로부터 나머지 모든 노드까지 가장 싼 경로를 찾아. 기계장치는 이래.
모든 노드까지의 잠정 거리를 들고 다녀. 출발지는 0, 나머지는 무한대로 시작해.
(0, source)를 최소 힙, 그러니까 우선순위 큐에 넣어.
잠정 거리가 가장 작은 노드를 꺼내서 확정해. 그 거리는 이제 최종이야.
그 이웃들을 완화(relax)해. 방금 확정한 노드를 거쳐 가는 게 지금 잠정 거리보다 싸면 값을 갱신하고 새 거리를 힙에 넣어.
힙이 빌 때까지 반복해.
BFS와 견줘 보면 경계를 펼쳐 나가는 모양은 똑같아. 다만 그 경계가 평범한 FIFO 큐가 아니라 총비용을 키로 삼는 우선순위 큐라는 게 달라. Dijkstra는 거의 말 그대로 힙을 단 BFS야. 힙 트랙과 그래프 트랙이 한 알고리즘 안에서 만나는 지점이지.
꺼내는 순간 확정해도 왜 안전할까
Dijkstra를 정확하게 만들어 주는 탐욕적 통찰이 있어. 아직 확정 안 된 노드 중 가장 가까운 걸 꺼내는 순간, 그 잠정 거리는 이미 진짜 최단 거리야. 왜냐면 거기로 가는 다른 모든 경로는 아직 힙에 남아 있는 어떤 노드를 거쳐야 하는데, 그 노드들은 전부 방금 꺼낸 것보다 멀리 있거든. 가중치가 0 이상이니까 더 먼 노드로 돌아가는 건 비용을 더하기만 해. 그래서 더 싼 경로가 나중에 나타날 수가 없어. 증명은 이걸로 끝이고, 동시에 Dijkstra가 가중치가 0 이상이어야 한다고 요구하는 이유이기도 해. 음수 간선이 있으면 '더 먼' 노드가 몰래 더 싼 경로를 내놓을 수 있고, 그 순간 보장이 깨지거든. 바로 다음 이야기로 이어지는 대목이야.
Dijkstra는 최소 힙을 단 BFS야. 지금까지 알려진 가장 싼 노드를 반복해서 꺼내고, 확정하고, 이웃을 완화해. 꺼내면서 확정해도 안전한 건 가중치가 0 이상이라 더 먼 노드가 더 싼 우회로를 내놓을 수 없기 때문이고. 힙을 쓰면 O((V+E) log V)야.
세상을 굴리는 곳
Dijkstra와, 휴리스틱으로 방향을 잡아주는 사촌 A*가 우리가 쓰는 GPS와 네트워크 라우팅 프로토콜(OSPF가 이걸로 라우터 사이 최소 비용 경로를 계산해), 게임 길찾기, 항공과 대중교통 플래너의 최단 경로 알고리즘이야. '비용이 0 이상인 가중 네트워크에서 가장 싼 경로'라면 거의 다 Dijkstra지. 그리고 이걸 효율적으로 만들어 주는 게 힙 트랙에서 배운 우선순위 큐야. 힙이 없으면 가장 싼 경계 노드를 매번 찾느라 O((V+E) log V)가 아니라 O(V²)가 들 테니까.
피파의 고백
Dijkstra는 '어려운 그래프 알고리즘'이라는 이름값으로 나를 겁줬어. 아빠가 한마디로 정리해 주기 전까지는. "힙 있는 BFS 야." 그 순간 새로운 게 아니게 됐어. 내가 이미 아는 두 개가 딱 맞물린 거였으니까. 큐가 우선순위 큐가 되고 '몇 번 거쳤나'가 '얼마나 들었나'로 바뀌는 것뿐, 나머지는 열두 번은 해본 그 경계 펼치기였어. 제일 무섭게 들리는 알고리즘이 알고 보면 이미 아는 조각 둘인데 아직 맞물리는 걸 못 본 것뿐인 경우가 많더라.
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가 힙에서 꺼내지는 순간에 왜 C로 가는 더 싼 경로가 앞으로 절대 안 나타날 거라고 확신할 수 있는지 한 문장으로 설명해.
Hint
거리는 A가 0, B가 1, C가 3(B를 거쳐서), D가 4(C를 거쳐서)야. 확정 순서는 거리가 작은 순으로 A(0), B(1), C(3), D(4)고. C가 거리 3에서 꺼내질 때, C로 가는 다른 모든 경로는 이미 3 이상 떨어진 힙 속 노드를 지나야 하는데 가중치가 0 이상이라 그걸 줄일 수가 없어. 그래서 3이 최종이야.
Progress
Progress is local-only — sign in to sync across devices.