다익스트라 알고리즘은 어떤 조건에서 최단 경로를 구할 수 있나요?

다익스트라 알고리즘은 시작 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘입니다. 모든 간선 가중치가 음수가 아니어야 하며, 현재까지 거리가 가장 짧은 정점을 확정해 나가는 그리디 전략을 사용합니다.

핵심 개념

• 우선순위 큐에서 가장 짧은 거리 후보를 꺼냅니다.
• 그 정점을 거쳐 이웃 정점으로 가는 비용이 더 작으면 거리를 갱신합니다.
• 음수 간선이 없기 때문에 한 번 가장 짧게 확정된 정점은 나중에 더 짧아질 수 없습니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

// 개념 코드: pq는 [distance, node]를 작은 distance 순으로 꺼낸다고 가정
function dijkstra(graph, start) {
  const dist = new Map([[start, 0]]);
  const pq = new MinPriorityQueue();
  pq.push([0, start]);

  while (!pq.isEmpty()) {
    const [d, node] = pq.pop();
    if (d !== dist.get(node)) continue; // 오래된 후보 무시

    for (const [next, weight] of graph.get(node) ?? []) {
      const nd = d + weight;
      if (nd < (dist.get(next) ?? Infinity)) {
        dist.set(next, nd);
        pq.push([nd, next]);
      }
    }
  }
  return dist;
}

실무에서 주의할 점

• 음수 간선이 있으면 확정된 거리라는 가정이 깨집니다. 이 경우 Bellman-Ford 등을 사용해야 합니다.
• 우선순위 큐 없이 매번 최소 거리를 선형 탐색하면 큰 그래프에서 느립니다.
• 경로 자체가 필요하면 거리뿐 아니라 이전 정점(prev)도 저장해야 합니다.

실무 적용 가이드

• 도로망, 네트워크 라우팅, 비용이 모두 0 이상인 경로 문제에 적합합니다.
• 가중치가 모두 1이면 다익스트라보다 BFS가 더 단순합니다.
• 목표 정점 하나만 필요하면 그 정점이 pop되어 확정되는 순간 종료할 수 있습니다.

함께 연결해서 보면 좋은 키워드

Dijkstra, Shortest Path, Priority Queue, Non-negative Weight

정리

다익스트라 알고리즘은 시작 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.