InwooLeeme.dev

가중치 그래프의 최단 경로: 다익스트라

간선마다 가중치가 다른 그래프에서 최단 경로를 구하는 다익스트라 알고리즘 — 왜 BFS로는 안 되는지부터 우선순위 큐 구현까지.

6/9/2026 · 7 min read

BFS로는 왜 안 될까

지난 글에서 BFS가 무가중치 그래프의 최단 경로를 보장한다고 했다. 그런데 현실의 그래프는 보통 간선마다 비용이 다르다. 도로마다 길이가 다르고, 네트워크마다 지연이 다르다.

이때 BFS를 그대로 쓰면 틀린다. BFS는 "간선을 몇 개 거쳤나"를 기준으로 가까운 정점부터 보는데, 가중치가 있으면 간선 1개짜리 경로가 간선 3개짜리 경로보다 길 수도 있기 때문이다.

그래서 기준을 "거친 간선 수"가 아니라 지금까지 쌓인 거리로 바꿔야 한다. 그게 다익스트라다.

핵심 아이디어

정의Dijkstra's Algorithm

모든 간선의 가중치가 음수가 아닐 때, 한 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘. 매 순간 아직 확정되지 않은 정점 중 가장 가까운 것을 골라 거리를 확정해 나간다.

핵심은 한 문장이다. "가장 가까운 정점은 더 이상 줄어들 수 없다."

생각해보면 당연하다. 가중치가 음수가 아니니까, 다른 정점을 거쳐서 돌아오는 경로는 어차피 지금 거리보다 짧아질 수 없다. 그러니 현재 후보 중 거리가 가장 작은 정점은 그 값으로 확정해도 안전하다. 이렇게 가장 가까운 것부터 하나씩 확정하는 그리디 전략이 다익스트라의 전부다.

그럼 "현재 가장 가까운 미확정 정점"을 매번 어떻게 빨리 찾을까? 그냥 매번 전부 뒤지면 느리니까 **우선순위 큐(최소 힙)**를 쓴다.

동작 과정

1

거리 배열 초기화

시작 정점 ss의 거리는 00, 나머지는 ∞\infty로 둔다. 우선순위 큐에 (0,s)(0, s)를 넣는다.

2

가장 가까운 정점 꺼내기

큐에서 거리가 가장 작은 (d,v)(d, v)를 꺼낸다. 이 vv가 이번에 거리를 확정할 정점이다.

3

이웃 거리 갱신 (완화)

vv의 이웃 uu에 대해 dist[v]+w<dist[u]dist[v] + w < dist[u]이면 더 짧은 길을 찾은 것이므로 dist[u]dist[u]를 갱신하고, (dist[u],u)(dist[u], u)를 큐에 넣는다.

4

큐가 빌 때까지 반복

큐가 비면 도달 가능한 모든 정점의 최단 거리가 확정돼 있다.

3번 과정, 즉 "더 짧은 경로를 찾으면 거리를 줄이는 것"을 **완화(relaxation)**라고 부른다. 다익스트라뿐 아니라 최단 경로 알고리즘 대부분의 공통 동작이다.

구현

const int INF = 1e9;
int N, M;                          // 정점 수, 간선 수
vector<pair<int,int>> G[20020];    // G[v] = {이웃, 가중치}
int dist[20020];
 
void dijkstra(int s){
    for(int i = 1; i <= N; i++) dist[i] = INF;
 
    // {거리, 정점} — 거리가 작은 것이 먼저 나오도록 최소 힙
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    dist[s] = 0;
    pq.push({0, s});
 
    while(!pq.empty()){
        auto [d, v] = pq.top(); pq.pop();
        if(d > dist[v]) continue;          // 이미 더 짧게 처리됨 → 무시
        for(auto [nxt, w] : G[v]){
            if(dist[v] + w < dist[nxt]){   // 완화: 더 짧은 길 발견
                dist[nxt] = dist[v] + w;
                pq.push({dist[nxt], nxt});
            }
        }
    }
}

큐에 {정점, 거리}가 아니라 {거리, 정점} 순으로 넣는 게 포인트다. pair는 첫 번째 원소로 먼저 비교하니까, 거리를 앞에 둬야 "가장 가까운 정점"이 먼저 나온다.

자주 하는 실수

if(d > dist[v]) continue; 한 줄을 빼먹지 말자. 다익스트라는 한 정점을 큐에 여러 번 넣는다(거리가 갱신될 때마다). 그래서 꺼냈을 때 이미 더 짧은 거리로 처리된 낡은 항목일 수 있는데, 이걸 걸러주는 게 저 줄이다. 없어도 답은 맞지만 쓸데없는 일을 반복해 느려진다.

BFS처럼 별도의 visited 배열을 두고 "한 번 방문하면 끝"으로 막는 방식도 있지만, 위처럼 거리 비교로 거르는 방식이 더 간결하고 많이 쓰인다. 둘을 섞어 쓰면 오히려 헷갈리니 하나만 확실히 하자.

음수 간선이 하나라도 있으면 다익스트라는 쓸 수 없다. "가장 가까운 정점은 더 줄어들 수 없다"는 전제가 음수 간선 앞에서 깨지기 때문이다. 이때는 벨만-포드(Bellman-Ford)나 SPFA를 써야 한다.

시간복잡도

TimeSpace
  • 각 간선마다 최대 한 번씩 큐에 넣고(EE번), 큐 연산이 O(log⁡V)O(\log V)이라 O(Elog⁡V)O(E \log V)
  • 거리 배열 O(V)O(V), 인접 리스트 O(V+E)O(V + E)

정점 기준으로 단순 배열을 뒤지는 O(V2)O(V^2) 버전도 있는데, 간선이 적은(희소) 그래프에선 우선순위 큐 버전이 훨씬 빠르다. PS에서 마주치는 그래프는 대부분 희소하니 위 구현을 기본으로 외워두면 된다.

정리

  • 언제: 가중치가 음수가 아닌 그래프의 한 정점 → 전체 최단 거리
  • 어떻게: 미확정 정점 중 가장 가까운 것을 우선순위 큐로 꺼내 거리 확정 + 이웃 완화
  • 실수 포인트: {거리, 정점} 순서, 낡은 항목 거르기, 음수 간선이면 금지
  • 복잡도: O(Elog⁡V)O(E \log V)

BFS가 "한 칸씩 균일하게 퍼지는 물결"이라면, 다익스트라는 "가까운 곳부터 욕심껏 확정하는 물결"이다. 기준만 거리로 바꿨을 뿐, 결국 가까운 것부터 본다는 직관은 그대로다.

Tags:algorithm

관련 글