[알고리즘] 다익스트라 알고리즘: 최단 거리와 C++ 구현

다익스트라는 언제 사용하는가

다익스트라 알고리즘은 가중치 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 단일 시작점 최단 경로 알고리즘입니다. 도로 비용, 게임 맵의 이동 비용, 네트워크 라우팅처럼 이동마다 비용이 다른 문제에 사용할 수 있습니다.

필수 조건: 모든 간선의 가중치가 0 이상이어야 합니다. 방향 그래프와 무방향 그래프 모두 가능하지만, 무방향 간선은 인접 리스트에 양방향으로 추가해야 합니다.

가중치가 모두 같다면 BFS가 더 단순하고 빠릅니다. 음수 간선이 있다면 벨만-포드를, 모든 정점 쌍의 최단 거리가 필요하다면 그래프 크기에 따라 플로이드-워셜 등을 검토합니다.

핵심 연산: 완화

distance[v]는 지금까지 발견한 시작점에서 v까지의 최단 거리 후보입니다. 현재 정점 u를 거쳐 v로 가는 편이 더 짧다면 값을 바꿉니다. 이 갱신을 완화(Relaxation)라고 합니다.

if (distance[next] > distance[current] + weight) {
    distance[next] = distance[current] + weight;
}

처음에는 시작점만 0, 나머지는 도달하지 못했다는 뜻의 INF로 둡니다. 이후 아직 처리하지 않은 후보 중 거리가 가장 짧은 정점을 고르고, 그 정점에서 나가는 모든 간선을 완화하는 과정을 반복합니다.

예제로 따라가기

A --2--> B
A --5--> C
B --1--> C
B --4--> D
C --1--> D

A에서 시작하면 초기 거리는 A=0, B=INF, C=INF, D=INF입니다.

처리 정점	완화 결과	A	B	C	D
초기	시작점 설정	0	INF	INF	INF
A	B=2, C=5	0	2	5	INF
B	C=min(5, 2+1), D=2+4	0	2	3	6
C	D=min(6, 3+1)	0	2	3	4
D	갱신 없음	0	2	3	4

 

최종 최단 거리는 A=0, B=2, C=3, D=4입니다. A에서 C로 직접 가는 비용 5보다 A → B → C의 비용 3이, B에서 D로 바로 가는 누적 비용 6보다 A → B → C → D의 비용 4가 더 작습니다.

가까운 정점을 먼저 고르는 이유

아직 확정하지 않은 정점 중 거리가 가장 짧은 current를 생각해 봅시다. 다른 미확정 정점을 우회해 current에 도달하려면 현재 알고 있는 거리 이상에서 출발해 0 이상의 간선 비용을 더해야 합니다. 따라서 더 짧은 경로가 나중에 나타날 수 없습니다.

이 때문에 최소 거리 후보를 꺼내는 순간 그 거리를 확정할 수 있습니다. 다익스트라는 이 그리디 선택과, 선택한 정점의 이웃을 완화하는 과정을 결합한 알고리즘입니다.

음수 간선에서는 왜 실패하는가

A --2--> B
A --5--> C
C ---10-> B

다익스트라는 A에서 가까운 B의 거리 2를 먼저 확정하려 합니다. 그러나 실제 최단 경로는 A → C → B이고 비용은 5 + (-10) = -5입니다. 음수 간선 때문에 먼 정점을 우회한 경로가 오히려 더 짧아져 앞의 논리가 깨집니다.

음수 간선이 하나라도 존재할 수 있다면 다익스트라를 사용하면 안 됩니다. 보통 벨만-포드로 전환하며, 음수 사이클이 있으면 최단 거리 자체가 정의되지 않을 수 있다는 점도 확인해야 합니다.

최소 힙과 오래된 항목

매 단계마다 모든 정점을 훑어 최솟값을 찾으면 O(V²)이 걸립니다. 인접 리스트와 최소 힙 기반 priority_queue를 사용하면 발견된 후보를 (거리, 정점)으로 넣고 가장 짧은 후보부터 꺼낼 수 있습니다.

C의 거리가 처음 10이었다가 더 짧은 경로를 발견해 4가 되면 큐에는 (10, C)와 (4, C)가 함께 남습니다. C를 찾아 기존 항목의 우선순위를 직접 낮추는 대신 새 후보를 추가하고, 나중에 꺼낸 값이 현재 최단 거리와 다르면 버리는 방식이 단순합니다.

if (currentDistance != distances[currentVertex]) {
    continue; // 이미 더 짧은 경로가 발견된 오래된 항목
}

C++ 구현

#include <functional>
#include <limits>
#include <queue>
#include <stdexcept>
#include <utility>
#include <vector>

struct Edge {
    int to;
    int weight;
};

using Graph = std::vector<std::vector<Edge>>;

std::vector<int> Dijkstra(const Graph& graph, int start) {
    if (start < 0 || start >= static_cast<int>(graph.size())) {
        throw std::out_of_range("Start vertex is out of range");
    }

    const int INF = std::numeric_limits<int>::max();
    std::vector<int> distances(graph.size(), INF);

    using State = std::pair<int, int>; // {거리, 정점}
    std::priority_queue<State, std::vector<State>, std::greater<State>> minQueue;

    distances[start] = 0;
    minQueue.push({0, start});

    while (!minQueue.empty()) {
        const auto [currentDistance, currentVertex] = minQueue.top();
        minQueue.pop();

        if (currentDistance != distances[currentVertex]) {
            continue;
        }

        for (const Edge& edge : graph[currentVertex]) {
            if (edge.to < 0 || edge.to >= static_cast<int>(graph.size())) {
                throw std::out_of_range("Edge vertex is out of range");
            }
            if (edge.weight < 0) {
                throw std::invalid_argument("Dijkstra requires non-negative weights");
            }
            if (currentDistance > INF - edge.weight) {
                continue; // int 덧셈 오버플로 방지
            }

            const int newDistance = currentDistance + edge.weight;
            if (newDistance < distances[edge.to]) {
                distances[edge.to] = newDistance;
                minQueue.push({newDistance, edge.to});
            }
        }
    }

    return distances;
}

이 함수는 인접 리스트로 방향 그래프를 표현합니다. 무방향 간선이라면 graph[from]과 graph[to]에 각각 반대 방향 간선을 넣습니다. 실제 비용 합이 int 범위를 넘을 수 있는 문제라면 거리와 가중치 타입을 long long로 바꾸고 충분히 안전한 INF를 사용해야 합니다.

거리뿐 아니라 최단 경로 복원하기

거리만 반환하면 비용은 알 수 있지만 어떤 정점을 거쳤는지는 알 수 없습니다. 완화에 성공할 때 직전 정점을 기록하면 도착점에서 시작점까지 역추적할 수 있습니다.

std::vector<int> previous(graph.size(), -1);

if (newDistance < distances[edge.to]) {
    distances[edge.to] = newDistance;
    previous[edge.to] = currentVertex;
    minQueue.push({newDistance, edge.to});
}

// target부터 previous를 따라가며 모은 뒤 순서를 뒤집는다.

distance[target] == INF라면 시작점에서 도착점으로 가는 경로가 없으므로 복원을 시도하지 않습니다. 최단 경로가 여러 개라면 이 기본 구현은 완화 과정에서 먼저 선택된 경로 하나를 기록합니다.

복잡도와 구현 선택 기준

구현	시간 복잡도	적합한 경우
인접 행렬 + 선형 탐색	O(V²)	정점이 적거나 간선이 매우 조밀한 그래프
인접 리스트 + 최소 힙	O((V+E) log V)	정점이 많고 간선이 비교적 적은 그래프

 

연결 그래프에서는 보통 E ≥ V-1이므로 최소 힙 구현을 간단히 O(E log V)라고도 표현합니다. 공간 복잡도는 그래프와 거리·큐 저장을 포함해 대체로 O(V+E)입니다.

실전 체크리스트

• 가중치가 모두 0 이상인지 확인한다
• 음수 간선이 가능하다면 다른 알고리즘을 선택합니다.
• 방향성을 입력에 정확히 반영한다
• 무방향 그래프는 두 방향 간선을 모두 추가합니다.
• 오래된 큐 항목을 건너뛴다
• 큐에서 꺼낸 거리와 현재 저장된 최단 거리가 다르면 처리하지 않습니다.
• 거리 타입과 INF를 안전하게 잡는다
• 최대 경로 비용을 계산해 필요하면 long long를 사용합니다.
• 도달 불가능한 정점을 구분한다
• 끝까지 INF인 정점은 경로가 없는 경우입니다.

다익스트라의 핵심은 최소 힙 자체가 아니라, 음수가 아닌 간선이라는 조건 아래 가장 가까운 정점을 확정하고 이웃을 완화한다는 흐름입니다. 이 전제를 먼저 확인하면 구현의 각 줄이 왜 필요한지도 자연스럽게 이해할 수 있습니다.