다익스트라

다익스트라 핵심 개념

언제 쓰는가?

• 단일 시작점 최단거리(Single-Source Shortest Path) 문제에서 사용합니다.
• 단, 모든 간선 가중치가 0 이상(음수 없음)이어야 합니다.

BFS와의 관계

• BFS는 "모든 간선 가중치가 1"인 특수 케이스의 최단거리 알고리즘입니다.
• 다익스트라는 가중치가 서로 달라도, 가장 싼 경로부터 확정해 나갑니다.

핵심 아이디어 (완화, Relaxation)

• 현재 정점 u를 통해 이웃 v로 가는 더 짧은 경로를 찾으면 갱신합니다.
• 공식: dist[v] > dist[u] + w(u,v) 이면
  • dist[v] = dist[u] + w(u,v)
  • parent[v] = u

---

전제 조건과 모델링

반드시 확인할 전제

• 음수 간선이 있으면 다익스트라는 안전하지 않습니다.
• 음수 간선이 있으면 벨만-포드(또는 SPFA 등)를 고려해야 합니다.

권장 그래프 표현

• 희소 그래프(실무 대부분): 인접 리스트
  • vector<vector<pair<int,int>>> adj; ({to, weight})
• 밀집 그래프에서 정점 수가 작으면 행렬도 가능하지만, 보통 인접 리스트 + PQ 조합이 표준입니다.

자료구조 준비

• dist[v]: 시작점에서 v까지 현재까지 알려진 최소 비용
• parent[v]: 최단 경로에서 v의 직전 정점
• 우선순위 큐(min-heap): (비용, 정점) 기준으로 비용이 작은 것 먼저

---

다익스트라 템플릿 (실전형)

코드

struct Node {
    int dist;
    int v;
    bool operator>(const Node& other) const {
        return dist > other.dist;
    }
};

void Dijkstra(
    int start,
    const vector<vector<pair<int,int>>>& adj,
    vector<int>& dist,
    vector<int>& parent
) {
    int V = static_cast<int>(adj.size());
    const int INF = numeric_limits<int>::max() / 4; // overflow 여유

    dist.assign(V, INF);
    parent.assign(V, -1);

    priority_queue<Node, vector<Node>, greater<Node>> pq;
    dist[start] = 0;
    parent[start] = start;
    pq.push({0, start});

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();

        int here = cur.v;
        int cost = cur.dist;

        // 지연 삭제(lazy deletion): 더 나쁜 오래된 후보 버리기
        if (cost != dist[here]) continue;

        for (const auto& edge : adj[here]) {
            int there = edge.first;
            int w = edge.second;

            int nextCost = cost + w;
            if (nextCost >= dist[there]) continue;

            dist[there] = nextCost;
            parent[there] = here;
            pq.push({nextCost, there});
        }
    }
}

구현 포인트

• C++ priority_queue는 decrease-key를 직접 지원하지 않으므로, 더 좋은 비용을 발견하면 그냥 다시 push합니다.
• pop 시점에 if (cost != dist[here]) continue;로 오래된 항목을 버리는 패턴이 실무 표준입니다.

---

경로 복원

vector<int> BuildPath(int start, int target, const vector<int>& parent, const vector<int>& dist) {
    vector<int> path;
    if (target < 0 || target >= static_cast<int>(parent.size())) return path;
    if (dist[target] >= numeric_limits<int>::max() / 8) return path; // 도달 불가

    int cur = target;
    while (cur != start) {
        path.push_back(cur);
        cur = parent[cur];
        if (cur == -1) { // 안전 장치
            path.clear();
            return path;
        }
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    return path;
}

• dist[target]가 INF이면 도달 불가입니다.
• parent 역추적으로 실제 최단 경로를 얻을 수 있습니다.

---

시간/공간 복잡도

경우	시간 복잡도	비고
인접 리스트 + 우선순위 큐	O((V + E) log V)	일반적인 구현
인접 행렬 + 선형 선택	O(V^2)	정점 수가 작거나 밀집 그래프에서 사용 가능

공간 복잡도:

• 인접 리스트: O(V + E)
• dist, parent, PQ 등 추가 메모리: O(V) ~ O(E)

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
음수 간선에서 다익스트라 사용	최단거리 보장 깨짐
오래된 PQ 항목 미스킵	불필요 연산 폭증
INF + w 오버플로우 무시	음수/쓰레기 값 발생 가능
parent 초기화 누락	경로 복원 오류
무방향 그래프에서 역간선 미추가	실제 그래프와 다른 결과

체크 질문 (스스로 답해보기)

• 다익스트라가 음수 간선에서 실패하는 핵심 이유는?
• if (cost != dist[here]) continue;가 필요한 이유는?
• BFS와 다익스트라의 경계(언제 BFS로 충분한지)는?
• 경로만 필요할 때도 parent를 왜 저장해야 할까?

---

다익스트라 한계 (다음 파트 연결)

• 최단 비용은 구하지만, 기본 다익스트라는 목적지 정보를 직접 사용하지 않아 탐색 범위가 넓어질 수 있습니다.
• 목표가 명확한 길찾기에서는 휴리스틱으로 탐색 방향을 유도하는 A*가 더 빠를 수 있습니다.

---