다익스트라(Dijkstra) 알고리즘은 가중치가 있는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 대표적인 알고리즘으로, 1956년 네덜란드의 컴퓨터 과학자 Edsger Wybe Dijkstra가 발명하여 현재까지 네트워크 라우팅, GPS 내비게이션, 게임 AI 등 수많은 분야에서 핵심적으로 활용되고 있다. 탐욕 알고리즘(Greedy Algorithm) 접근 방식을 사용하여 매 단계에서 최적의 선택을 하며, 우선순위 큐를 활용한 구현으로 O(E log V)의 효율적인 시간 복잡도를 달성하여 대규모 그래프에서도 실용적으로 사용할 수 있다.

다익스트라 알고리즘의 역사

다익스트라 알고리즘이란?

가중치가 있는 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘으로, 모든 간선의 가중치가 0 이상이어야 한다는 제약 조건을 가진다.

다익스트라 알고리즘은 1956년 네덜란드 암스테르담에서 탄생했으며, 당시 26세였던 Edsger W. Dijkstra가 약혼녀와 함께 암스테르담의 한 카페에서 휴식을 취하던 중 약 20분 만에 이 알고리즘을 고안했다고 알려져 있다. Dijkstra는 당시 수학 센터(Mathematisch Centrum)에서 ARMAC이라는 초기 컴퓨터의 프로그래머로 일하고 있었으며, 새로운 컴퓨터의 시연을 위해 비전문가 청중도 이해할 수 있는 문제를 찾던 중 두 도시 간의 최단 경로를 찾는 문제를 선택했다.

흥미롭게도 Dijkstra는 이 알고리즘을 고안할 때 펜과 종이를 전혀 사용하지 않고 오직 머릿속으로만 설계했다고 후에 인터뷰에서 밝혔으며, 그는 “펜과 종이를 사용하지 않는 것의 장점 중 하나는 피할 수 있는 복잡성을 거의 강제적으로 피하게 된다는 것"이라고 설명했다. 이 알고리즘은 1959년에 “A Note on Two Problems in Connexion with Graphs"라는 제목의 논문으로 Numerische Mathematik 저널에 발표되었으며, 이 논문은 단 3페이지에 불과했지만 컴퓨터 과학 역사상 가장 영향력 있는 논문 중 하나로 평가받고 있다.

Dijkstra는 이후 구조적 프로그래밍, THE 운영체제, 세마포어 개념 등 컴퓨터 과학의 여러 분야에서 선구적인 업적을 남겼으며, 1972년에는 “프로그래밍 언어의 기초적인 기여"로 튜링 상을 수상했고, 2002년 세상을 떠날 때까지 컴퓨터 과학의 발전에 지대한 공헌을 했다.

알고리즘의 동작 원리

다익스트라 알고리즘은 탐욕 알고리즘(Greedy Algorithm) 접근 방식을 사용하며, 매 단계에서 현재까지 발견된 정점 중 시작 정점으로부터의 거리가 가장 짧은 정점을 선택하고, 이 정점을 통해 다른 정점들로 가는 경로를 갱신하는 과정을 반복한다.

핵심 원리: 최적 부분 구조

다익스트라 알고리즘의 정확성은 최단 경로 문제의 최적 부분 구조(Optimal Substructure) 성질에 기반하며, 이는 “A에서 C까지의 최단 경로가 B를 거친다면, A에서 B까지의 부분 경로도 A에서 B까지의 최단 경로여야 한다"는 원리이다. 또한 모든 간선의 가중치가 0 이상이라는 전제 조건 하에서, 한 번 확정된 정점의 최단 거리는 절대 변하지 않는다는 성질이 수학적으로 증명되어 있으며, 이 성질이 알고리즘의 탐욕적 접근을 정당화한다.

알고리즘 수행 단계

1단계: 초기화

시작 정점에서 각 정점까지의 거리를 저장하는 배열을 생성하고 모든 값을 무한대(INF)로 초기화하며, 시작 정점의 거리만 0으로 설정하고, 우선순위 큐에 시작 정점을 (거리 0, 시작 정점) 형태로 삽입한다.

2단계: 최소 거리 정점 선택

우선순위 큐에서 거리가 가장 짧은 정점을 꺼내며, 이 정점이 이미 처리된 정점이라면(현재 기록된 거리보다 큐에서 꺼낸 거리가 더 크다면) 무시하고 다음 정점을 선택한다.

3단계: 인접 정점 거리 갱신 (Relaxation)

선택된 정점과 연결된 모든 인접 정점에 대해 “시작 정점 → 현재 정점 → 인접 정점” 경로의 거리를 계산하고, 이 값이 기존에 기록된 인접 정점까지의 거리보다 작다면 거리를 갱신하고 우선순위 큐에 해당 정점을 삽입한다.

4단계: 반복

우선순위 큐가 빌 때까지 2단계와 3단계를 반복하며, 모든 정점이 처리되면 시작 정점에서 각 정점까지의 최단 거리가 배열에 저장된다.

동작 예시

다음과 같은 그래프가 있다고 가정한다. 정점 1에서 시작하여 모든 정점까지의 최단 거리를 구한다.

정점: 1, 2, 3, 4
간선: 1→2(가중치 4), 1→3(가중치 1), 2→3(가중치 2), 2→4(가중치 5), 3→4(가중치 8)
  1. 초기화: dist = [0, INF, INF, INF], 큐 = [(0, 1)]
  2. 정점 1 선택: dist[2] = 4, dist[3] = 1로 갱신, 큐 = [(1, 3), (4, 2)]
  3. 정점 3 선택(거리 1): dist[4] = 1+8=9로 갱신, 큐 = [(4, 2), (9, 4)]
  4. 정점 2 선택(거리 4): dist[4] = min(9, 4+5=9) = 9 (변화 없음)
  5. 정점 4 선택(거리 9): 인접 정점 없음
  6. 결과: dist = [0, 4, 1, 9]

우선순위 큐와 시간 복잡도

다익스트라 알고리즘의 효율성은 우선순위 큐의 사용 여부에 크게 좌우되며, 우선순위 큐를 사용하면 매번 최소 거리 정점을 O(log V)에 찾을 수 있어 전체 시간 복잡도가 크게 개선된다.

Min Heap 기반 우선순위 큐

우선순위 큐는 내부적으로 Min Heap(최소 힙) 자료구조로 구현되며, 이는 부모 노드가 항상 자식 노드보다 작은 값을 가지는 완전 이진 트리 형태이다. 힙의 루트 노드에 항상 가장 작은 값이 위치하므로 최소값 확인은 O(1)에 가능하고, 삽입(push)과 최소값 추출(pop) 연산은 트리의 높이만큼인 O(log V)에 수행된다.

시간 복잡도 분석

우선순위 큐 사용 시: O((V + E) log V) 또는 O(E log V)

각 정점을 우선순위 큐에서 최대 한 번씩 꺼내므로 O(V log V)의 시간이 소요되고, 각 간선에 대해 최대 한 번씩 거리 갱신 및 큐 삽입 연산을 수행하므로 O(E log V)의 시간이 소요되어, 전체 시간 복잡도는 O((V + E) log V)이다. 연결된 그래프에서는 E ≥ V - 1이므로 일반적으로 O(E log V)로 표현한다.

우선순위 큐 미사용 시: O(V²)

배열로 구현하면 매 단계마다 O(V)의 시간을 들여 최소 거리 정점을 선형 탐색해야 하므로, V개의 정점에 대해 총 O(V²)의 시간 복잡도를 가진다. 구현이 간단하다는 장점이 있지만, 대부분의 경우 우선순위 큐 버전보다 느리다.

희소 그래프 vs 밀집 그래프

희소 그래프(Sparse Graph, E ≈ V)에서는 우선순위 큐 버전이 O(V log V)로 배열 버전의 O(V²)보다 훨씬 빠르며, 밀집 그래프(Dense Graph, E ≈ V²)에서는 우선순위 큐 버전이 O(V² log V)가 되어 배열 버전의 O(V²)보다 오히려 느릴 수 있다. 실제 응용에서는 희소 그래프가 더 흔하므로 일반적으로 우선순위 큐를 사용한 구현이 선호된다.

구현 예제

우선순위 큐를 사용한 다익스트라 알고리즘의 C++ 구현이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define INF 1e9

int main() {
    int n, m; // n: 정점 수, m: 간선 수
    cin >> n >> m;

    vector<vector<pair<int, int>>> graph(n + 1); // 인접 리스트
    vector<int> dist(n + 1, INF); // 최단 거리 배열

    // 그래프 입력
    for (int i = 0; i < m; i++) {
        int a, b, c; // a에서 b로 가는 가중치 c인 간선
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
    }

    int start, end;
    cin >> start >> end;

    // 우선순위 큐: (거리, 정점) - 거리 기준 최소 힙
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        // 이미 처리된 정점이면 스킵
        if (dist[cur] < cost) continue;

        // 인접 정점 탐색 및 거리 갱신
        for (auto& edge : graph[cur]) {
            int next = edge.first;
            int nextCost = edge.second;

            if (dist[next] > cost + nextCost) {
                dist[next] = cost + nextCost;
                pq.push({dist[next], next});
            }
        }
    }

    if (dist[end] == INF) {
        cout << "경로 없음" << '\n';
    } else {
        cout << dist[end] << '\n';
    }

    return 0;
}

코드 설명

  • graph: 인접 리스트 형태로 그래프를 저장하며, graph[a]는 정점 a에서 출발하는 간선들의 (도착 정점, 가중치) 쌍을 저장한다.
  • dist: 시작 정점에서 각 정점까지의 최단 거리를 저장하는 배열로, 초기값은 무한대이다.
  • pq: 최소 힙으로 구현된 우선순위 큐로, (거리, 정점) 쌍을 저장하며 거리가 작은 것이 먼저 나온다.
  • if (dist[cur] < cost) continue: 이미 더 짧은 경로로 처리된 정점이면 스킵하는 최적화 조건이다.

음수 가중치의 문제

다익스트라 알고리즘은 모든 간선의 가중치가 0 이상이어야 한다는 중요한 제약 조건을 가지며, 음수 가중치가 있는 그래프에서는 올바른 결과를 보장할 수 없다.

음수 가중치에서 실패하는 이유

다익스트라 알고리즘의 핵심 가정은 “한 번 확정된 정점의 최단 거리는 변하지 않는다"는 것인데, 음수 가중치가 존재하면 이미 확정된 정점을 거쳐 가는 경로가 나중에 더 짧은 경로로 발견될 수 있어 이 가정이 깨진다.

반례 예시

정점: 1, 2, 3
간선: 1→2(가중치 5), 1→3(가중치 2), 2→3(가중치 -4)
시작 정점: 1, 목표 정점: 3

다익스트라 알고리즘의 진행:

  1. 정점 1에서 시작, dist = [0, INF, INF]
  2. 정점 3을 거리 2로 확정 (1→3 경로)
  3. 정점 2를 거리 5로 확정 (1→2 경로)
  4. 결과: 정점 3까지 최단 거리 = 2

실제 최단 경로:

  • 1→2→3 경로: 5 + (-4) = 1
  • 정답: 1

다익스트라는 정점 3을 너무 일찍 확정했기 때문에 1→2→3 경로를 고려하지 못하고 잘못된 결과를 산출한다.

음수 가중치 해결 방법

음수 가중치가 있는 그래프에서 최단 경로를 찾아야 한다면 Bellman-Ford 알고리즘을 사용해야 하며, 이 알고리즘은 O(VE)의 시간 복잡도로 다익스트라보다 느리지만 음수 가중치를 올바르게 처리하고 음수 사이클의 존재 여부도 감지할 수 있다.

실제 응용 사례

다익스트라 알고리즘은 이론적 가치뿐만 아니라 실제 세계에서 광범위하게 활용되고 있으며, 우리가 일상적으로 사용하는 많은 서비스의 핵심 기술이다.

네트워크 라우팅 프로토콜 (OSPF)

인터넷의 대표적인 내부 라우팅 프로토콜인 OSPF(Open Shortest Path First)는 다익스트라 알고리즘을 사용하여 네트워크 상에서 데이터 패킷이 전송될 최적의 경로를 계산하며, 1989년 RFC 1131로 처음 표준화된 이후 현재까지 대규모 기업 네트워크와 인터넷 서비스 제공자(ISP) 네트워크에서 핵심적으로 사용되고 있다. 각 라우터는 Link State Advertisement(LSA)를 통해 네트워크 토폴로지 정보를 수집하고, 이를 바탕으로 다익스트라 알고리즘을 실행하여 자신으로부터 다른 모든 라우터까지의 최단 경로를 계산한다.

GPS 내비게이션 시스템

자동차 내비게이션과 Google Maps, 카카오맵 등의 지도 애플리케이션은 다익스트라 알고리즘 또는 그 변형(A* 알고리즘)을 사용하여 출발지에서 목적지까지의 최단 경로를 계산하며, 도로 네트워크를 그래프로 모델링하여 교차로는 정점으로, 도로는 간선으로 표현한다. 간선의 가중치는 단순 거리뿐만 아니라 예상 소요 시간, 통행료, 도로 등급 등 다양한 요소를 복합적으로 고려하여 설정되며, 실시간 교통 정보를 반영하여 동적으로 경로를 재계산하는 기능도 이 알고리즘을 기반으로 한다.

게임 AI 경로 탐색

게임에서 NPC(Non-Player Character)나 적 캐릭터가 플레이어를 추적하거나 목표 지점으로 이동할 때 다익스트라의 변형인 A* 알고리즘을 주로 사용하며, A*는 목표 지점까지의 예상 거리(휴리스틱)를 추가로 고려하여 탐색 방향을 목표 쪽으로 유도함으로써 다익스트라보다 더 빠르게 경로를 찾을 수 있다. StarCraft, Age of Empires 같은 실시간 전략 게임(RTS)에서 수백 개의 유닛이 동시에 이동할 때도 이 알고리즘의 최적화된 버전이 사용된다.

소셜 네트워크 분석

LinkedIn의 “당신은 어떻게 연결되어 있습니까” 기능이나 Facebook의 친구 추천 시스템은 다익스트라 알고리즘을 활용하여 두 사용자 간의 최단 연결 경로를 찾으며, 사용자를 정점으로, 친구 관계를 간선으로 모델링하고 모든 간선의 가중치를 1로 설정하면 최단 경로가 곧 최소 단계의 연결을 의미한다.

다른 최단 경로 알고리즘과의 비교

최단 경로 문제를 해결하는 알고리즘은 다익스트라 외에도 여러 가지가 있으며, 각각의 특성과 적용 상황이 다르다.

알고리즘시간 복잡도음수 가중치음수 사이클 감지특징
다익스트라O(E log V)불가불가단일 출발점, 가장 빠름
Bellman-FordO(VE)가능가능단일 출발점, 음수 가중치 처리
Floyd-WarshallO(V³)가능감지만 가능모든 쌍 최단 경로
A*O(E log V)*불가불가목표 지향적 탐색, 휴리스틱 필요

A 알고리즘의 시간 복잡도는 휴리스틱의 품질에 따라 달라지며, 이상적인 휴리스틱에서는 다익스트라보다 훨씬 빠를 수 있다.

알고리즘 선택 가이드

  • 양수 가중치, 단일 출발점: 다익스트라 알고리즘
  • 음수 가중치 존재, 단일 출발점: Bellman-Ford 알고리즘
  • 모든 정점 쌍의 최단 경로 필요: Floyd-Warshall 알고리즘
  • 목표 지점이 명확하고 휴리스틱 사용 가능: A* 알고리즘

결론

다익스트라 알고리즘은 1956년 Edsger W. Dijkstra가 암스테르담의 카페에서 20분 만에 고안한 알고리즘으로, 탐욕 알고리즘 접근 방식을 사용하여 가중치가 있는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 효율적으로 찾는다. 우선순위 큐(Min Heap)를 활용하면 O(E log V)의 시간 복잡도를 달성할 수 있으며, 희소 그래프에서 특히 효율적이다. 모든 간선의 가중치가 0 이상이어야 한다는 제약이 있어 음수 가중치가 있는 경우에는 Bellman-Ford 알고리즘을 사용해야 하지만, 대부분의 실제 응용 상황에서는 양수 가중치만 존재하므로 다익스트라 알고리즘이 적합하다. OSPF 라우팅 프로토콜, GPS 내비게이션, 게임 AI 경로 탐색, 소셜 네트워크 분석 등 현대 컴퓨팅의 수많은 분야에서 핵심적으로 활용되고 있으며, 컴퓨터 과학 역사상 가장 영향력 있는 알고리즘 중 하나로 평가받고 있다.