최단 경로에 음수 간선이 있습니다. Dijkstra에 같은 우선순위 큐를 쓰면 왜 보장이 깨지나요?

Dijkstra는 가장 작은 미확정 거리를 꺼냈을 때 그 거리가 더 낮아지지 않는다는 비음수 간선 전제에 의존합니다. 음수 간선이 있으면 나중에 우회해 이미 처리한 노드의 거리를 낮출 수 있습니다.

동작 원리와 전제

A에서 B까지 2, A에서 C까지 5, C에서 B까지 -4이면 B를 2로 확정한 뒤 실제 더 짧은 1 경로가 나타납니다. 구현에 따라 재처리할 수 있어도 표준 Dijkstra의 정확성·복잡도 보장과는 다릅니다.

선택과 실패 처리

음수 간선이 필요한 모델이면 Bellman-Ford나 그래프 구조에 맞는 알고리즘을 검토합니다. 음수 cycle이 도달 가능한 경로에 있으면 유한 최단값 자체가 없을 수 있습니다. 비용 모델을 바꿔 음수를 제거할 때도 경로 순서가 보존되는지 확인합니다.

구체적인 사례와 검증

음수 간선이 있어도 특정 입력에서는 Dijkstra 결과가 우연히 맞을 수 있습니다. 그 관찰을 일반 보장으로 삼으면 안 됩니다. 알고리즘이 pop한 노드를 영구 확정하는지, 더 작은 값이 오면 재삽입하는지에 따라 실패 양상과 시간 복잡도가 달라집니다. 음수 cycle은 단순히 느린 탐색이 아니라 최솟값이 계속 내려가 유한 해가 없는 경우일 수 있습니다. 출발점에서 도달 가능한지와 목표에 영향을 주는 cycle인지도 문제에 맞춰 봅니다. 비용을 상수만 더해 양수로 만들면 간선 수가 다른 경로의 상대 비용이 달라질 수 있으므로 무조건적인 변환은 하지 않습니다.

작은 반례·음수 cycle·도달 불가·0 비용을 시험합니다. 우선순위 큐 선택이 알고리즘 전제를 대체하지 않습니다. 최단 경로와 MST의 음수 가중치 허용은 다른 문제이므로 구분하겠습니다.