다익스트라의 원리: 거리 완화와 오래된 후보 건너뛰기

다익스트라는 거리 후보를 어떻게 완화하고 확정하나요?

다익스트라는 아직 처리하지 않은 거리 후보 중 가장 작은 것을 골라 이웃의 거리를 줄입니다. 모든 간선의 가중치가 0 이상이면 꺼낸 최신 거리보다 더 짧은 경로가 나중에 나타나지 않습니다.

0→1의 비용이 7이어도 0→2가 2, 2→1이 1이면 1까지의 거리는 3으로 줄어듭니다. 먼저 발견한 7은 확정값이 아닙니다.

적용 조건·범위: 정점 번호는 0부터 시작하며 각 간선은 [도착 정점, 가중치]입니다. 그래프는 방향 그래프이고 가중치는 비음수 정수, 거리 합은 Number의 안전한 정수 범위 안으로 제한합니다. 아래 예제에는 실행에 필요한 최소 힙 함수도 포함되어 있습니다.

본문 근거: Competitive Programmer’s Handbook — Antti Laaksonen · Princeton Algorithms — Shortest Paths 강의 자료

이 글에서 할 일: 거리 완화와 확정을 구분하고 오래된 힙 후보를 건너뜁니다. 선수 지식: 그래프의 인접 리스트·최소 힙.

더 짧은 경로를 발견하면 거리를 갱신합니다

dist[v]는 지금까지 발견한 v까지의 가장 짧은 거리입니다. 시작점은 0, 나머지는 Infinity에서 시작합니다. u에서 v로 가는 가중치 w를 보았을 때 dist[u]+w < dist[v]이면 더 짧은 경로를 찾은 것입니다. 이 갱신을 완화라고 합니다.

표의 후보는 (거리,정점)입니다. 발견 시점에 방문 완료로 표시하면 7을 3으로 줄이는 경로를 놓칠 수 있습니다. 최소 힙에서 꺼낸 후보가 현재 dist와 같을 때 그 정점을 처리합니다.

최소 힙으로 실행하는 전체 예제

정점 번호는 0부터 시작하며 각 간선은 [도착 정점, 가중치]입니다. 그래프는 방향 그래프이고 가중치는 비음수 정수, 거리 합은 Number의 안전한 정수 범위 안으로 제한합니다. 아래 예제에는 실행에 필요한 최소 힙 함수도 포함되어 있습니다.

JavaScript 예제: 시작점 0에서 각 정점까지의 최단거리를 구합니다. 앞의 후보 처리 표와 아래 코드·실행 결과를 함께 보며, 더 짧은 경로로 거리를 갱신하고 오래된 후보를 건너뛰는 과정을 살펴보세요. 직접 실행하지 않아도 설명을 따라갈 수 있습니다.

function dijkstra(graph, start) {
  // 정점은 0부터, 간선은 [도착 정점, 비음수 정수 가중치]
  // 거리 합은 Number의 안전한 정수 범위 안이라고 가정합니다.
  const heap = [];
  function push(item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  }
  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length === 0) return top;
    heap[0] = last;
    let i = 0;
    while (2 * i + 1 < heap.length) {
      let child = 2 * i + 1;
      if (child + 1 < heap.length && heap[child + 1][0] < heap[child][0]) child++;
      if (heap[i][0] <= heap[child][0]) break;
      [heap[i], heap[child]] = [heap[child], heap[i]];
      i = child;
    }
    return top;
  }
  const dist = Array(graph.length).fill(Infinity);
  dist[start] = 0;
  push([0, start]);
  while (heap.length > 0) {
    const [cost, vertex] = pop();
    if (cost !== dist[vertex]) continue;
    for (const [next, weight] of graph[vertex]) {
      const candidate = cost + weight;
      if (candidate < dist[next]) {
        dist[next] = candidate;
        push([candidate, next]);
      }
    }
  }
  return dist;
}

const graph = [[[1, 7], [2, 2]], [[3, 1]], [[1, 1], [3, 6]], [], []];
console.log(dijkstra(graph, 0).join(','));

실행 결과

0,3,2,4,Infinity

정점 4는 시작점에서 도달할 수 없어 Infinity로 남습니다. cost !== dist[vertex]는 더 좋은 경로가 생긴 뒤 힙에 남아 있는 옛 후보를 건너뜁니다. 같은 거리에는 새 후보를 넣지 않으므로 0 가중치 순환에서도 같은 상태를 끝없이 추가하지 않습니다.

node --version

node dijkstra.js

비음수 조건이 거리 확정을 보장합니다

꺼낸 최신 거리 d보다 더 짧은 경로가 나중에 생긴다고 가정해 보겠습니다. 그 경로의 아직 처리하지 않은 첫 정점에는 앞선 완화로 d보다 작은 후보가 있어야 합니다. 최소 힙은 그 후보를 먼저 꺼냈어야 하므로 모순입니다. 이후 간선을 더 지나도 거리가 줄지 않는다는 비음수 조건이 이 논증의 핵심입니다.

음수 간선은 이 조건을 깨뜨립니다. 일부 입력에서 우연히 맞더라도 이 코드의 정당성과 비용을 보장하지 않으므로 Bellman–Ford 등 입력에 맞는 방법을 선택합니다. 가중치가 모두 같은 경우에는 BFS도 검토할 수 있습니다.

평행 간선은 각각 완화하며 더 작은 후보가 남습니다. 무방향 그래프라면 간선을 양쪽 인접 리스트에 넣어야 합니다. 시작점이 유효한 정점인지, 숫자 범위를 넘지 않는지는 입력 단계에서 확인합니다.

정점 V개, 간선 E개일 때 이 중복 후보 방식의 이진 힙 구현은 O(V + E log(E+1)) 시간, 입력을 제외하고 O(V+E) 공간을 사용합니다. 평행 간선이 없는 일반적인 그래프에서는 흔히 O((V+E) log V)로 씁니다. 힙의 기존 항목을 줄이는 구현과 중복 후보를 넣는 구현의 공간 상한을 혼동하지 마세요.

직접 확인하고 문제에 적용하기

0→1 비용이 0이고 1→0도 0이면 왜 무한 반복하지 않을까요? 0→1 비용 7과 2의 평행 간선이 있으면 무엇이 남을까요?

• 다익스트라 최단 경로 문제 풀이
• 최소 힙 구현 — push·pop의 원리
• 그래프 인접 리스트와 BFS

참고 자료

자료 확인일: 2026년 10월 19일.

• Competitive Programmer’s Handbook — Antti Laaksonen — 13.2절의 비음수 최단 경로와 우선순위 큐.
• Princeton Algorithms — Shortest Paths 강의 자료 — 거리 완화와 비음수 다익스트라의 원리.