다익스트라 우선순위 큐 구현을 보면 같은 노드가 여러 번 들어가는 코드가 자주 나옵니다. 처음 보면 visited로 막아야 하는 것 아닌가 싶습니다.
핵심은 큐에 들어가는 것은 노드 자체가 아니라 그 노드까지 가는 거리 후보라는 점입니다. 더 좋은 후보가 나오면 다시 넣고, 오래된 후보는 꺼낼 때 버립니다.
다익스트라 stale entry 처리 기준
우선순위 큐에는 후보가 들어간다
cp-algorithms의 Dijkstra 설명처럼 다익스트라는 현재까지 가장 짧아 보이는 정점을 골라 간선을 완화합니다.
더 짧은 경로를 찾으면 다시 넣는다
import heapq
dist[start] = 0
heap = [(0, start)]
while heap:
cost, now = heapq.heappop(heap)
if dist[now] < cost:
continue
for nxt, weight in graph[now]:
new_cost = cost + weight
if new_cost < dist[nxt]:
dist[nxt] = new_cost
heapq.heappush(heap, (new_cost, nxt))A까지 거리 10인 후보가 먼저 들어간 뒤 거리 4인 경로를 찾으면 A는 큐에 두 번 들어갑니다. 이것은 오류가 아니라 후보 갱신입니다.
오래된 후보는 dist 배열로 거른다
if dist[now] < cost: continue는 큐에서 꺼낸 후보가 이미 낡았는지 확인하는 줄입니다. dist 배열이 현재까지의 최선값이기 때문입니다.
정리
다익스트라에서 같은 노드가 우선순위 큐에 여러 번 들어가는 것은 자연스러운 구현입니다. 큐는 후보를 담고, dist 배열은 최선값을 담습니다. 오래된 후보를 건너뛰는 한 줄을 이해하면 구현이 훨씬 선명해집니다.
다익스트라 우선순위 큐에서 중복이 생기는 예
예를 들어 A에서 C로 가는 경로가 두 개 있다고 가정해 보겠습니다. 처음에는 A → C 비용 10을 발견해서 큐에 넣습니다. 나중에 A → B → C 비용 4를 발견하면 C에 대한 더 좋은 후보가 새로 생깁니다.
처음 발견: C까지 거리 10 -> queue에 (10, C)
나중 발견: C까지 거리 4 -> queue에 (4, C)
queue 안에는 C가 두 번 있을 수 있다.
하지만 dist[C]는 4로 갱신되어 있다.이때 기존의 (10, C)를 큐 안에서 찾아 지우는 대신, 그냥 놔둡니다. 그리고 나중에 꺼냈을 때 dist 배열과 비교해서 오래된 후보라면 버립니다.
stale entry를 버리는 조건이 핵심이다
while pq:
cost, node = heappop(pq)
if cost > dist[node]:
continue # 이미 더 짧은 경로가 발견된 오래된 후보
for next_node, weight in graph[node]:
next_cost = cost + weight
if next_cost < dist[next_node]:
dist[next_node] = next_cost
heappush(pq, (next_cost, next_node))이 continue 한 줄 때문에 같은 노드가 여러 번 들어가도 정답이 깨지지 않습니다. 큐는 후보를 보관하고, dist 배열은 현재까지 확인한 가장 좋은 답을 보관합니다.
visited를 무조건 쓰면 왜 헷갈릴까
다익스트라에서도 visited를 쓰는 구현이 있습니다. 다만 이때 visited는 BFS처럼 “큐에 넣었다”는 뜻이 아니라, 가장 짧은 거리로 확정했다는 뜻에 가깝습니다.
- BFS visited: 처음 발견한 순간 최단거리라는 성질을 이용한다
- 다익스트라 visited: 가장 작은 후보로 꺼낸 순간 확정한다
- 중복 큐 방식: visited 없이 stale entry를 continue로 버릴 수 있다
- 둘을 섞으면 더 짧은 후보를 보기 전에 막아버리는 실수가 생길 수 있다
왜 음수 가중치에서는 조심해야 할까
다익스트라는 “현재 가장 작은 후보는 더 이상 줄어들지 않는다”는 감각 위에서 동작합니다. 그런데 음수 가중치가 있으면 나중에 돌아오는 경로가 기존 거리보다 더 작아질 수 있습니다.
그래서 다익스트라 문제를 풀 때는 구현보다 먼저 간선 가중치 조건을 봐야 합니다. 음수 간선이 있으면 벨만-포드 같은 다른 알고리즘을 검토해야 합니다.
실전에서 자주 틀리는 포인트
- pq에서 꺼낸 cost가 dist[node]보다 큰데도 계속 이웃을 탐색한다
- dist를 갱신하지 않고 큐에만 새 후보를 넣는다
- visited를 enqueue 시점에 찍어서 더 짧은 후보를 막는다
- 무한대 초기값을 너무 작게 잡아 overflow나 비교 오류가 난다
관련해서 같이 보면 좋은 글
다익스트라 알고리즘 입문도 함께 보면 이 글의 기준을 더 쉽게 연결할 수 있습니다.
BFS 문제 풀이 패턴 정리도 함께 보면 이 글의 기준을 더 쉽게 연결할 수 있습니다.
