안녕하세요. 자바파커입니다.

지도에서 목적지 방향으로 곧게 뻗은 길을 골랐습니다. 눈으로는 가장 가까워 보이지만 도로별 이동 시간을 더하니 19분입니다. 옆으로 돌아간 경로는 10분밖에 걸리지 않습니다.

왜 이런 차이가 생길까요?

최단 경로는 선의 길이가 아니라, 지나온 간선 가중치의 합으로 결정됩니다.

노드가 거리 순서대로 확정되고 마지막에 최단 경로가 되짚어지는 과정은 56초 영상으로도 정리했습니다. 눈으로 고른 19짜리 길과 알고리즘이 찾은 10짜리 길을 비교해 보세요.

지도를 그래프로 바꾼다

다익스트라 알고리즘을 적용하려면 먼저 지도를 그래프로 표현합니다.

• 교차로·역·장소 → 노드(Vertex)
• 두 장소를 잇는 도로 → 간선(Edge)
• 거리·시간·요금 → 가중치(Weight)

지도 앱이 찾는 최단 경로는 반드시 물리적으로 가장 짧은 길일 필요가 없습니다. 가중치를 이동 시간으로 두면 막히지 않는 우회로가 선택되고, 비용으로 두면 통행료가 적은 경로가 선택됩니다.

핵심은 현재까지 가장 싼 노드다

출발점 S의 거리를 0, 나머지는 무한대로 시작합니다.

1. 아직 확정하지 않은 노드 중 누적 거리가 가장 작은 노드를 고릅니다.
2. 그 노드와 연결된 이웃까지의 새 거리를 계산합니다.
3. 기존 거리보다 작으면 거리와 이전 노드를 갱신합니다.
4. 목적지가 확정될 때까지 반복합니다.

이웃 거리 갱신을 완화(Relaxation) 라고 부릅니다.

새 거리 = 현재 노드까지의 거리 + 간선 가중치

새 거리 < 기록된 거리라면
  거리와 이전 노드를 교체

왜 한 번 확정하면 다시 보지 않아도 될까

다익스트라는 탐욕 알고리즘입니다. 매번 지금 가장 작은 누적 거리를 선택합니다.

이 선택이 안전하려면 모든 간선 가중치가 0 이상이어야 합니다. 아직 방문하지 않은 경로를 돌아오더라도 비용이 음수가 아니므로 이미 가장 작았던 거리를 더 줄일 수 없기 때문입니다.

음수 가중치가 있으면 나중에 발견한 경로가 확정 거리를 낮출 수 있습니다. 이 경우에는 Bellman–Ford처럼 음수 간선을 처리하는 알고리즘이 필요합니다.

예제로 따라가기

아래 지도에서 최종 경로는 S → B → D → G → T이고 비용은 10입니다.

목적지 T가 확정되면 각 노드가 기억한 이전 노드를 역순으로 따라갑니다.

T ← G ← D ← B ← S

역순을 뒤집으면 실제 최단 경로가 됩니다.

JavaScript 구현

아래 코드는 이해를 위해 우선순위 큐를 배열로 단순화했습니다. 큰 그래프에서는 이진 힙을 사용해야 합니다.

function dijkstra(graph, start, target) {
  const dist = Object.fromEntries(Object.keys(graph).map(v => [v, Infinity]))
  const prev = {}
  const queue = [[0, start]]

  dist[start] = 0

  while (queue.length) {
    queue.sort((a, b) => a[0] - b[0])
    const [cost, node] = queue.shift()

    if (cost !== dist[node]) continue
    if (node === target) break

    for (const [next, weight] of graph[node]) {
      const nextCost = cost + weight

      if (nextCost < dist[next]) {
        dist[next] = nextCost
        prev[next] = node
        queue.push([nextCost, next])
      }
    }
  }

  if (dist[target] === Infinity) return null

  const path = []
  for (let at = target; at; at = prev[at]) path.push(at)

  return { distance: dist[target], path: path.reverse() }
}

배열을 정렬하는 위 구현은 교육용입니다. 이진 힙 기반 우선순위 큐를 사용하면 인접 리스트 그래프에서 일반적으로 O((V + E) log V)에 동작합니다.

BFS·A*·Bellman–Ford와 어떻게 다를까

A*는 목적지까지 남은 거리를 추정하는 휴리스틱을 더해 탐색 방향을 목적지 쪽으로 좁힙니다. 다익스트라는 휴리스틱 없이 누적 비용만 보기 때문에 더 넓게 탐색하지만 기준이 단순하고 확실합니다.

실제 지도 앱은 무엇을 더 고려할까

실제 경로 탐색의 가중치는 단순 거리 하나가 아닙니다.

• 현재·예상 교통량
• 제한 속도와 신호 대기
• 좌회전·유턴 비용
• 통행료와 도로 등급
• 일방통행과 시간대별 통제

또한 도시 전체 그래프는 매우 크므로 양방향 탐색, A*, 계층형 전처리 같은 최적화를 함께 사용합니다. 다익스트라는 그 최단 경로 문제를 이해하는 출발점입니다.

정리

1. 지도를 노드·간선·가중치로 바꿉니다.
2. 출발점부터 누적 비용이 가장 작은 미확정 노드를 고릅니다.
3. 이웃 노드의 거리를 완화하고 이전 노드를 기록합니다.
4. 목적지가 확정되면 이전 노드를 역추적해 경로를 복원합니다.

가까워 보이는 길을 고르는 것이 아니라, 지금까지의 총비용이 가장 작은 노드를 확정하는 알고리즘입니다.

자주 묻는 질문 (FAQ)

다익스트라는 목적지를 발견하면 바로 끝내도 되나요?

아닙니다. 목적지가 우선순위 큐에 들어온 순간에는 더 짧은 경로가 나중에 발견될 수 있습니다. 목적지가 최소 거리 노드로 큐에서 꺼내져 확정됐을 때 종료해야 합니다.

도달할 수 없는 목적지는 어떻게 알 수 있나요?

우선순위 큐가 비었는데 목적지 거리가 무한대라면 출발점에서 목적지로 가는 경로가 없는 것입니다.

간선 가중치가 모두 1이면 다익스트라를 써도 되나요?

정답은 구할 수 있지만 BFS가 더 단순하고 빠릅니다. 모든 간선 비용이 같다면 최소 비용은 최소 간선 수와 같기 때문입니다.

참고 자료

• E. W. Dijkstra — A Note on Two Problems in Connexion with Graphs (1959)
• NetworkX — Dijkstra’s Algorithm
• Boost.Graph — Shortest Paths