다익스트라 알고리즘

Q: 다익스트라 알고리즘의 시간 복잡도는 얼마인가요?

이진 힙 우선순위 큐를 사용하면 `O((V + E) log V)` 로 실행됩니다. 매 단계 배열을 순회하며 최솟값을 찾는 단순한 버전은 `O(V²)` 이며, 밀집 그래프에서는 오히려 더 빠를 수 있습니다. 둘 다 `O(V)` 공간을 사용합니다.

Q: 벨만-포드 대신 다익스트라를 언제 사용해야 하나요?

모든 간선 가중치가 음이 아닐 때는 언제나 다익스트라를 사용하세요. 벨만-포드의 `O(V·E)` 에 비해 `O((V + E) log V)` 로 더 빠릅니다. 벨만-포드는 간선이 음수일 수 있거나 음수 사이클을 감지해야 할 때만 선택하세요. 음이 아닌 그래프에서는 다익스트라가 거의 항상 더 나은 선택입니다.

마지막 업데이트 2026년 7월 1일

다익스트라 알고리즘은 음이 아닌 간선 가중치를 가진 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾습니다. 각 노드에 잠정 거리를 유지하고, 잠정 거리가 가장 작은 미확정 노드를 반복적으로 확정하며 그 간선을 완화합니다. 현재 노드를 거치는 더 짧은 경로가 발견될 때마다 이웃 노드의 거리를 갱신합니다. 위의 재생 버튼을 눌러 각 노드가 확정될 때 거리가 낮아지는 모습을 확인하세요.

핵심 아이디어는 탐욕적입니다. 가장 가까운 미확정 노드가 선택되면 그 거리는 최종적입니다. 그 노드로 가는 다른 모든 경로는 이미 더 멀리 있는 노드를 거쳐야 하기 때문입니다. 이진 힙 우선순위 큐를 사용하면 다익스트라는 O((V + E) log V) 시간에 실행됩니다. 음이 아닌 가중치가 필요하며, 간선이 음수일 수 있으면 벨만-포드를 사용하세요.

시간 및 공간 복잡도

구현	복잡도	비고
이진 힙	O((V + E) log V)	일반적이고 실용적인 선택
배열 순회	O(V²)	더 단순함; 밀집 그래프에 적합
공간	O(V)	거리 + 우선순위 큐
요구 사항	음이 아닌 가중치	음수 간선은 탐욕적 선택을 깨뜨림

단계별 과정

단계	무엇이 일어나는가
1	시작 노드의 거리를 0으로, 나머지는 모두 무한대로 설정한다.
2	잠정 거리가 가장 작은 미확정 노드를 선택한다.
3	그것을 확정으로 표시한다 — 최단 거리가 이제 최종이다.
4	각 이웃에 대해 현재-경유-거리 + 간선 가중치를 계산한다.
5	그 값이 이웃의 현재 거리보다 작으면 완화한다.
6	도달 가능한 모든 노드가 확정될 때까지 반복한다.

풀이 예제

간선 A-B=4, A-C=1, C-B=2, C-D=5, B-D=1 을 가진 그래프에서 시작 노드 A 로부터의 최단 경로:

단계	확정	거리	동작
0	-	`A=0, B=∞, C=∞, D=∞`	초기화: 시작 노드 `A=0`, 나머지는 모두 무한대.
1	`A` (0)	`B=4, C=1, D=∞`	`A` 에서 간선 완화: `B=4`, `C=1` 로 설정.
2	`C` (1)	`B=3, D=6`	`C` 를 거쳐: `B=1+2=3` 이 4를 갱신; `D=1+5=6`.
3	`B` (3)	`D=4`	`B` 를 거쳐: `D=3+1=4` 가 6을 갱신.
4	`D` (4)	`A=0, C=1, B=3, D=4`	`D` 확정; 완화할 것이 더 없음. 완료.

다익스트라 알고리즘을 사용할 때

사용할 때	피해야 할 때
모든 간선 가중치가 음이 아닐 때	어떤 간선이든 음수일 수 있을 때: 벨만-포드를 사용
하나의 시작 노드에서 모든 노드까지의 최단 경로가 필요할 때	모든 쌍 간 최단 경로가 필요할 때: 플로이드-워셜이 더 단순
그래프가 가중이고 정확한 거리가 필요할 때	그래프가 비가중일 때: 단순한 BFS가 더 빠르고 단순
좋은 힙이나 우선순위 큐를 사용할 수 있을 때	휴리스틱으로 단일 목적지에 빠르게 도달하고 싶을 때: A* 를 사용

Dijkstra's Algorithm 코드

Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Dijkstra's Algorithm 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.

Python로 구현한 Dijkstra's Algorithm 코드Python
1import heapq2
3
4def dijkstra(graph, start):5    dist = {node: float("inf") for node in graph}6    dist[start] = 07    pq = [(0, start)]8    while pq:9        d, node = heapq.heappop(pq)10        if d > dist[node]:11            continue  # stale entry, a shorter path was already found12        for neighbor, weight in graph[node]:13            new_dist = d + weight14            if new_dist < dist[neighbor]:15                dist[neighbor] = new_dist16                heapq.heappush(pq, (new_dist, neighbor))17    return dist18
19
20graph = {21    "A": [("B", 4), ("C", 1)],22    "B": [("D", 1)],23    "C": [("B", 2), ("D", 5)],24    "D": [("E", 3)],25    "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29    print(f"A -> {node}: {d}")
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Dijkstra's Algorithm 코드JavaScript
1const graph = {2    A: { B: 4, C: 2 },3    B: { C: 5, D: 10 },4    C: { E: 3 },5    D: { F: 11 },6    E: { D: 4 },7    F: {},8};9
10function dijkstra(source) {11    const dist = {};12    const visited = new Set();13    for (const node in graph) dist[node] = Infinity;14    dist[source] = 0;15    while (visited.size < Object.keys(graph).length) {16        // JS has no built-in heap: linear scan for the closest node (O(V^2))17        let u = null;18        for (const node in dist) {19            if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20                u = node;21            }22        }23        if (dist[u] === Infinity) break;24        visited.add(u);25        for (const [v, w] of Object.entries(graph[u])) {26            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27        }28    }29    return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Dijkstra's Algorithm 코드Java
1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7    public static void main(String[] args) {8        int n = 6;9        List<List<int[]>> adj = new ArrayList<>();10        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11        int[][] edges = {12            {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13            {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14        };15        for (int[] e : edges) {16            adj.get(e[0]).add(new int[]{e[1], e[2]});17            adj.get(e[1]).add(new int[]{e[0], e[2]});18        }19
20        int[] dist = new int[n];21        Arrays.fill(dist, Integer.MAX_VALUE);22        dist[0] = 0;23        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24        pq.add(new int[]{0, 0}); // {node, distance}25        while (!pq.isEmpty()) {26            int[] cur = pq.poll();27            int node = cur[0], d = cur[1];28            if (d > dist[node]) continue; // stale queue entry29            for (int[] edge : adj.get(node)) {30                int next = edge[0], nd = d + edge[1];31                if (nd < dist[next]) {32                    dist[next] = nd;33                    pq.add(new int[]{next, nd});34                }35            }36        }37        System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38    }39}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Dijkstra's Algorithm 코드C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6    const int INF = 1000000000;7    // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8    std::vector<std::vector<std::pair<int, int>>> adj = {9        {{1, 4}, {2, 1}},  // 010        {{3, 1}},          // 111        {{1, 2}, {3, 5}},  // 212        {{4, 3}},          // 313        {},                // 414    };15    int n = static_cast<int>(adj.size());16    std::vector<int> dist(n, INF);17    dist[0] = 0;18    using State = std::pair<int, int>;  // (distance, node)19    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20    pq.push({0, 0});21    while (!pq.empty()) {22        auto [d, u] = pq.top();23        pq.pop();24        if (d > dist[u]) continue;  // stale queue entry25        for (auto [v, w] : adj[u]) {26            if (d + w < dist[v]) {27                dist[v] = d + w;28                pq.push({dist[v], v});29            }30        }31    }32    for (int v = 0; v < n; ++v) {33        std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34    }35    return 0;36}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Dijkstra's Algorithm 코드C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8    // Weighted directed graph: w[u][v] = 0 means no edge9    int w[N][N] = {10        {0, 4, 1, 0, 0},11        {0, 0, 0, 1, 0},12        {0, 2, 0, 5, 0},13        {0, 0, 0, 0, 3},14        {0, 0, 0, 0, 0},15    };16    int dist[N];17    bool done[N] = {false};18    for (int v = 0; v < N; v++) dist[v] = INF;19    dist[0] = 0;20    // O(V^2) scan for the closest unfinished node (no heap needed here)21    for (int iter = 0; iter < N; iter++) {22        int u = -1;23        for (int v = 0; v < N; v++) {24            if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25        }26        if (dist[u] == INF) break;  // remaining nodes are unreachable27        done[u] = true;28        for (int v = 0; v < N; v++) {29            if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30                dist[v] = dist[u] + w[u][v];31            }32        }33    }34    for (int v = 0; v < N; v++) {35        printf("Distance 0 -> %d: %d\n", v, dist[v]);36    }37    return 0;38}
이 코드를 C 플레이그라운드에서 실행하기

다익스트라 알고리즘 자주 묻는 질문

다익스트라 알고리즘의 시간 복잡도는 얼마인가요?

이진 힙 우선순위 큐를 사용하면 O((V + E) log V) 로 실행됩니다. 매 단계 배열을 순회하며 최솟값을 찾는 단순한 버전은 O(V²) 이며, 밀집 그래프에서는 오히려 더 빠를 수 있습니다. 둘 다 O(V) 공간을 사용합니다.

다익스트라는 왜 음수 간선 가중치에서 작동하지 않나요?

다익스트라는 가장 가까운 미확정 노드를 확정하면 그 거리가 최종이라고 가정합니다. 음수 간선은 나중에 이미 확정된 노드로 가는 더 짧은 경로를 만들어 이 가정을 깨뜨릴 수 있습니다. 음수 가중치가 있는 그래프에는 벨만-포드 알고리즘을 사용하세요.

다익스트라와 BFS의 차이는 무엇인가요?

BFS는 간선을 세어(각 간선 가중치가 사실상 1) 단순한 큐로 최단 경로를 찾습니다. 다익스트라는 이를 가중 그래프로 일반화하여 우선순위 큐를 사용해 항상 총거리가 가장 작은 노드를 확장합니다. 비가중 그래프에서는 둘이 같은 경로를 만듭니다.

다익스트라와 A* 탐색의 차이는 무엇인가요?

A* 는 목적지까지 남은 거리를 추정하는 휴리스틱을 더한 다익스트라로, 모든 방향으로 균일하게 퍼지는 대신 탐색을 그 목표로 유도합니다. 휴리스틱이 0이면 A* 는 정확히 다익스트라로 축소됩니다. 단일 목적지와 좋은 허용 휴리스틱이 있으면 A* 를, 모든 노드까지의 거리가 필요하면 다익스트라를 사용하세요.

벨만-포드 대신 다익스트라를 언제 사용해야 하나요?

모든 간선 가중치가 음이 아닐 때는 언제나 다익스트라를 사용하세요. 벨만-포드의 O(V·E) 에 비해 O((V + E) log V) 로 더 빠릅니다. 벨만-포드는 간선이 음수일 수 있거나 음수 사이클을 감지해야 할 때만 선택하세요. 음이 아닌 그래프에서는 다익스트라가 거의 항상 더 나은 선택입니다.

다익스트라는 노드를 확정한 후 다시 방문할 수 있나요?

아니요 — 노드가 일단 확정되면 그 거리는 최종이며 다시는 완화되지 않습니다. 힙 구현에서 흔한 함정은 노드의 거리가 개선된 후 우선순위 큐에 오래된 항목을 남겨두는 것입니다. 꺼낸 노드가 이미 확정되었다면(꺼낸 거리가 기록된 거리를 초과하면) 건너뛰어야 합니다. 이 검사를 잊어도 답은 여전히 정확하지만 불필요한 작업을 낭비합니다.