---
title: "다익스트라 알고리즘: 가장 가까운 후보를 확정할 수 있는 조건"
author: "Lee"
published_at: "2026-10-22T11:17:00.872Z"
updated_at: "2026-09-30T09:29:33.824Z"
tags: ["컴퓨터공학","알고리즘"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%80%EC%9E%A5-%EA%B0%80%EA%B9%8C%EC%9A%B4-%ED%9B%84%EB%B3%B4%EB%A5%BC-%ED%99%95%EC%A0%95%ED%95%A0-%EC%88%98-%EC%9E%88%EB%8A%94-%EC%A1%B0%EA%B1%B4"
ai_assisted: false
---

# 다익스트라 알고리즘: 가장 가까운 후보를 확정할 수 있는 조건

[원문](https://ariser.io/@writer_a1cd615ab19e/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%80%EC%9E%A5-%EA%B0%80%EA%B9%8C%EC%9A%B4-%ED%9B%84%EB%B3%B4%EB%A5%BC-%ED%99%95%EC%A0%95%ED%95%A0-%EC%88%98-%EC%9E%88%EB%8A%94-%EC%A1%B0%EA%B1%B4)

다익스트라 알고리즘은 한 출발점에서 다른 정점까지의 최단 거리를 구한다. 아직 확정하지 않은 후보 중 현재 거리가 가장 작은 정점을 선택한다. 이 선택이 안전하려면 간선 가중치가 음수가 아니어야 한다.

![가중치 5의 직접 경로보다 가중치 1과 2의 경유 경로가 짧은 다익스트라 예시](/api/v1/media/cf46961d-a790-455f-a319-6e62a138d288)

*음수가 없는 이 그래프에서 A에서 B까지의 최단 거리는 3이다.*

### 거리 완화와 확정

출발점 거리는 0, 나머지는 무한대로 시작한다. u를 통해 v로 가는 후보 거리 dist[u]+w가 기존 dist[v]보다 작으면 갱신한다. 이를 완화라고 한다. 우선순위 큐는 현재 가장 작은 후보를 효율적으로 꺼내 준다.

아래 예는 인접 리스트에 (이웃, 비음수 비용)을 저장하고 갱신할 때 새 후보를 넣는 방식이다. 같은 정점의 오래된 항목은 꺼낼 때 무시한다.

```python
import heapq

def dijkstra(graph, source):
    distance = {vertex: float("inf") for vertex in graph}
    distance[source] = 0
    pending = [(0, source)]
    while pending:
        candidate_distance, vertex = heapq.heappop(pending)
        if candidate_distance != distance[vertex]:
            continue
        for neighbor, edge_cost in graph[vertex]:
            improved = candidate_distance + edge_cost
            if improved < distance[neighbor]:
                distance[neighbor] = improved
                heapq.heappush(pending, (improved, neighbor))
    return distance
```

동률에서 정점 비교가 가능한 자료형이라는 코드상 가정도 있다. 그렇지 않으면 별도 순번을 넣는다. 가중치 조건은 호출 전에 보장해야 하며, 이 코드 자체가 음수 간선을 검사하는 것은 아니다.

### 왜 더 작은 경로가 나중에 오지 않을까

현재 최솟값 u보다 아직 처리하지 않은 정점의 거리는 작지 않다. 그 정점을 거쳐 u로 오는 경로는 비음수 간선을 더하므로 더 짧아질 수 없다. 따라서 최소 후보는 최단 거리로 확정할 수 있다. 이 논리는 음수 비용이 들어가면 무너진다.

A→B 비용 4, A→C 비용 1, C→B 비용 2라면 C를 먼저 처리하며 B를 4에서 3으로 줄인다. 이전 후보 (4,B)는 남아 있어도 현재 거리 3과 다르므로 버린다. 경로를 원하면 갱신 때 부모 정점을 함께 기록한다.

인덱스가 있는 이진 힙 구현은 O((V+E)log V)로 설명한다. 위의 중복 삽입 구현은 큐 항목이 E에 비례할 수 있어 O((V+E)log(V+E)) 같은 표현이 더 직접적이다. 단순 그래프에서는 흔히 O((V+E)log V)로 정리할 수 있다.

도달하지 못한 정점은 무한대로 남는다. 최단 경로가 여러 개면 이웃 순서에 따라 하나가 선택될 수 있다. 거리의 정확성과 경로의 동률 정책, 가중치 조건을 각각 구분하여 사용하는 것이 중요하다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)
- [Princeton · Algorithms, 4th edition · Shortest Paths](https://algs4.cs.princeton.edu/44sp/)