다익스트라

어떤 문제를 푸는가

가중치가 음이 아닌 방향/무방향 그래프에서, 한 시작점 \(s\)로부터 모든
정점까지의 최단 거리를 구합니다. 간선 가중치가 모두 1이면 BFS로 충분하지만,
가중치가 제각각이면 "가까운 칸부터 차례로"라는 BFS의 전제가 깨집니다.
다익스트라는 이 일반화를 다룹니다.

핵심 아이디어

거리 배열 dist[v]를 모두 \(\infty\)로 두고 dist[s] = 0에서 시작합니다.
아직 확정되지 않은 정점 중 dist가 가장 작은 정점 \(u\)를 고르고, 그
정점을 통한 이완(relaxation)을 합니다.

$$ \text{dist}[v] \leftarrow \min(\text{dist}[v],\ \text{dist}[u] + w(u, v)) $$

한 번 "가장 작은 값으로 뽑힌" 정점은 다시 갱신되지 않습니다. 이 정점을
확정(finalize) 했다고 부릅니다.

왜 옳은가 (정당성 스케치)

귀류법으로 봅니다. 어떤 정점 \(u\)를 확정하는 순간 dist[u]가 실제 최단 거리가
아니라고 가정합시다. 그러면 더 짧은 경로 \(P\)가 존재합니다. \(P\)를 따라가다 보면
아직 확정되지 않은 첫 정점 \(x\) 가 있습니다. \(x\)의 직전 정점은 이미
확정되었으므로 dist[x]는 그 시점에 이완되어 있고, 가중치가 음이 아니므로

$$ \text{dist}[x] \le (\text{경로 } P \text{에서 } x \text{까지의 거리}) \le \text{dist}[u] $$

가 됩니다. 그렇다면 우리는 \(u\) 대신 \(x\)를 먼저 뽑았어야 하므로 모순입니다.
음이 아닌 가중치 가정이 바로 두 번째 부등식을 보장하는 열쇠입니다. 음수
간선이 있으면 이 논증이 무너지고, 그때는 벨만-포드를 써야 합니다.

자료구조와 복잡도

매번 "가장 작은 dist"를 찾는 일을 최소 힙(우선순위 큐) 으로 합니다.
각 간선은 최대 한 번 큐에 (key, 정점) 쌍을 넣으므로 큐 연산은 \(O(E)\)번,
각 연산이 \(O(\log E) = O(\log V)\) 이므로 전체는

$$ O(E \log V) $$

입니다. 정점 수가 적고 간선이 빽빽하면(\(E \approx V^2\)) 힙 없이 매번 선형
탐색하는 \(O(V^2)\) 구현이 오히려 빠를 수 있습니다.

흐름 한눈에 보기

여기서 게으른 삭제(lazy deletion) 가 중요합니다. 우선순위 큐는 임의 원소의
값을 직접 줄이기 어렵기 때문에, 갱신할 때마다 새 쌍을 그냥 넣고 꺼낼 때
"이미 더 좋은 값으로 확정된 정점"이면 무시합니다.

정리

• 음이 아닌 가중치 단일 시작점 최단 경로의 표준 해법.
• 정당성의 핵심은 "음이 아닌 가중치 → 먼저 뽑힌 정점이 최단 확정".
• 힙 기반 \(O(E \log V)\), 조밀 그래프는 \(O(V^2)\)도 고려.
• 다음 강의에서 실제 구현과 흔한 함정을 다룹니다.

우선순위 큐 기반 표준 구현 (C++)

거리 배열은 큰 값으로 초기화하고, 최소 힙을 만들기 위해 greater를 씁니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int main() {
    int n, m, s;
    cin >> n >> m >> s;            // 정점 수, 간선 수, 시작점
    vector<vector<pair<int, int>>> adj(n + 1);  // (이웃, 가중치)
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});  // 무방향이면 반대 방향도 추가
    }

    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>,
                   greater<>> pq;   // (거리, 정점) 최소 힙
    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // 게으른 삭제: 낡은 항목은 버린다
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int v = 1; v <= n; v++)
        cout << (dist[v] == INF ? -1 : dist[v]) << '\n';
}

파이썬 구현

import sys, heapq
input = sys.stdin.readline
INF = float('inf')

def dijkstra(n, adj, s):
    dist = [INF] * (n + 1)
    dist[s] = 0
    pq = [(0, s)]                    # (거리, 정점)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:             # 게으른 삭제
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

흔한 함정

• 거리 자료형 — 간선 가중치 합이 21억을 넘으면 int가 넘칩니다. C++은
  long long, INF도 덧셈 후 넘치지 않게 1e18 정도로 잡습니다.
• 게으른 삭제 누락 — if (d > dist[u]) continue;를 빼면 같은 정점을 여러
  번 펼쳐 사실상 \(O(VE)\)로 느려집니다. 정답은 나와도 시간 초과가 납니다.
• 음수 간선 — 단 하나라도 음수면 다익스트라는 틀립니다. 음수가 있으면
  벨만-포드/SPFA로 바꾸세요.
• 무방향 그래프 — 양쪽 방향을 모두 인접 리스트에 넣어야 합니다.
• visited 배열로 막기 — dist 비교로 충분합니다. 별도 visited를 두면
  같은 효과지만, 잘못 두면 더 짧은 갱신을 막을 수 있어 주의합니다.

경로 복원

최단 거리뿐 아니라 실제 경로가 필요하면 이완할 때 직전 정점을 기록합니다.

if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
    par[v] = u;            // 어디서 왔는지 기억
    pq.push({dist[v], v});
}
// 복원: t에서 par를 따라 s까지 올라가 뒤집는다

응용 패턴

• K번째 최단 경로 / 특정 정점 경유 — 상태에 추가 정보를 붙여 정점을 확장.
• 0-1 BFS — 가중치가 0과 1뿐이면 덱으로 \(O(V+E)\).
• 간선이 조건부 — "기름통 용량" 같은 제약을 정점에 곱해 상태 그래프를 만든 뒤
  다익스트라. 즉 "현재 상태"를 정점으로 보는 모델링이 핵심입니다.

거리가 단조 증가한다는 성질(음이 아닌 가중치) 위에서 작동한다는 점만 늘
의식하면 변형 문제도 어렵지 않게 적용할 수 있습니다.

출제 신호

다음 조합이 보이면 다익스트라가 1순위 후보입니다.

• "한 정점에서 다른 정점(들)까지의 최단 거리/최소 비용"
• 간선 가중치가 모두 음이 아님 (1 이상, 0 이상 등) — 문제에 명시되거나
  비용의 의미상(시간, 요금, 거리) 음수가 불가능한 경우
• \(V \le 10^5\), \(E \le 3 \times 10^5\) 규모 — \(O(E \log V)\)를 요구하는 전형적 크기

반대 신호도 같이 외워 두세요. 가중치가 전부 1이면 그냥 BFS,
0과 1뿐이면 0-1 BFS, 음수 간선이 있으면 벨만-포드,
모든 쌍이 필요하고 \(V \le 500\)이면 플로이드-워셜입니다.
"경유지 제약", "도로를 \(k\)개까지 공짜로" 같은 조건은 정점을
(위치, 사용한 혜택 수)로 확장한 상태 그래프 다익스트라의 신호입니다.

풀이 결정 절차

1. 시작점이 하나인가? (여러 개면 가상 시작점 또는 멀티 소스로 초기 큐에 전부 투입)
2. 음수 간선이 없는가? — 없다는 근거를 제약에서 직접 확인합니다.
3. \(E \log V\)를 계산해 시간 안에 드는지 검산합니다. \(E \approx V^2\)의 조밀
   그래프면 힙 없는 \(O(V^2)\) 구현이 더 빠를 수 있습니다.
4. 거리의 최대값을 추정합니다 — \(V \times w_{\max}\)가 int 범위를 넘으면 long long.
5. 상태 확장이 필요한지(남은 연료, 사용한 쿠폰 수 등) 판단하고, 필요하면
   dist[v][상태] 2차원으로 키웁니다.

자주 하는 실수

가장 흔한 버그는 게으른 삭제 스킵 조건 누락입니다. 같은 정점이 낡은
거리로 큐에 여러 번 들어 있는데 전부 처리하면 최악에 시간 초과가 납니다.

while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]:      # 이 한 줄이 없으면 낡은 항목을 전부 확장 → TLE
        continue
    ...

visited 배열로 처리한다면 꺼낼 때(pop) 확정해야 합니다. 큐에 넣을 때
방문 표시를 하면 더 짧은 경로로의 갱신이 막혀 오답이 됩니다 — 이건 BFS의
습관이 그대로 옮아온 전형적인 버그입니다.

// 잘못: push 시점에 방문 처리 (가중치 그래프에서 오답)
if (!visited[v]) { visited[v] = true; pq.push({nd, v}); }

// 올바름: pop 시점에 확정
auto [d, u] = pq.top(); pq.pop();
if (visited[u]) continue;
visited[u] = true;

• 거리 오버플로 — 간선 가중치 \(10^9\) \(\times\) 경로 길이면 int가 터집니다.
  dist는 long long, INF는 1e18 수준으로.
• 최소 힙 설정 실수 — C++ priority_queue는 기본이 최대 힙입니다.
  greater<>를 빼먹으면 가장 먼 정점부터 확정해 오답이 납니다.
• 무방향 간선을 한쪽만 추가 — 입력이 양방향 도로인지 꼭 확인하세요.

연습 방법

사이드바 연습 목록의 기본 최단 경로 문제로 표준 구현을 한 번 "보지 않고"
써 보세요. 그다음 경로 복원(직전 정점 기록), 상태 확장형(예: 간선 \(k\)개
무료) 순서로 난도를 올립니다. 제출 전 자가 점검 세 가지 — 스킵 조건,
long long, 최소 힙 — 를 루틴으로 만들면 다익스트라에서 틀릴 일이 거의
없어집니다. 태그된 문제 3문제 이상 해결 시 마스터 처리되어 레이팅의
CLASS 보너스에 반영됩니다.