다익스트라(Dijkstra) 최단 경로 알고리즘

비음수 가중치 그래프에서 한 정점부터 모든 정점까지의 최단 경로를 우선순위 큐로 $O(E \log V)$ 에 구한다.

가중 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 문제는 라우팅, 내비게이션, 네트워크 최적화 등 실무에서 빈번하게 등장한다. Dijkstra 알고리즘은 비음수 가중치 그래프에서 이 문제를 효율적으로 해결하는 대표적인 탐욕(Greedy) 알고리즘이다.

Dijkstra 알고리즘의 정의

Dijkstra 알고리즘은 그래프에서 음의 가중치가 없는 간선들이 있을 때, 특정 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.

입력/출력

입력: 정점 집합 V, 간선 집합 E (가중치 $\geq 0$ ), 시작 정점 s
출력: 시작 정점에서 모든 정점까지의 최단 거리

시간 복잡도: $O(E \log V)$ (우선순위 큐 사용)

알고리즘 아이디어

초기화: 시작 정점 거리 $= 0$ , 나머지 $= \infty$
반복:
- 우선순위 큐에서 거리가 가장 작은 정점 u를 꺼냄
- u의 인접 정점 v에 대해 dist[u] + weight(u,v) < dist[v]이면 갱신
종료: 모든 정점 처리 완료

예시: 동작 과정

단계	처리 정점	dist 배열
초기	-	$[0, \infty, \infty, \infty, \infty]$
1	A	$[0, 2, 5, \infty, \infty]$
2	B	$[0, 2, 3, 5, \infty]$
3	C	[0, 2, 3, 5, 8]
4	D	[0, 2, 3, 5, 6]
5	E	[0, 2, 3, 5, 6]

결과: A→E 최단 거리 = 6 (A→B→D→E)

Python 구현

Python 구현은 heapq 기반 우선순위 큐를 사용하여 최소 거리 정점을 탐욕적으로 선택한다.

python

import heapq
import sys
 
def dijkstra(start, graph, n):
    INF = sys.maxsize
    dist = [INF] * n
    dist[start] = 0
 
    pq = [(0, start)]  # (거리, 노드)
    visited = [False] * n
 
    while pq:
        current_dist, u = heapq.heappop(pq)
 
        if visited[u]:
            continue
        visited[u] = True
 
        for v, w in graph[u]:
            if current_dist + w < dist[v]:
                dist[v] = current_dist + w
                heapq.heappush(pq, (dist[v], v))
 
    return dist
 
 
# 그래프 구성 (인접 리스트)
n = 5
graph = [[] for _ in range(n)]
edges = [
    (0, 1, 2), (0, 2, 5), (1, 2, 1),
    (1, 3, 3), (2, 3, 2), (2, 4, 5), (3, 4, 1)
]
for u, v, w in edges:
    graph[u].append((v, w))
    graph[v].append((u, w))
 
distances = dijkstra(0, graph, n)
print(distances)  # [0, 2, 3, 5, 6]

Java 구현

로직은 Python과 동일하다. PriorityQueue의 비교자를 o[1](거리)로 지정해 최소 거리 정점을 먼저 꺼내고, visited 배열로 이미 확정된 정점을 건너뛴다.

java

import java.util.*;
 
public class Dijkstra {
    public static int[] dijkstra(int start, List<List<int[]>> graph) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
 
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            Comparator.comparingInt(o -> o[1])
        );
        pq.offer(new int[]{start, 0});
        boolean[] visited = new boolean[n];
 
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];
 
            if (visited[u]) continue;
            visited[u] = true;
 
            for (int[] edge : graph.get(u)) {
                int v = edge[0], w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }
        return dist;
    }
}

Go 구현

Go는 표준 라이브러리 container/heap을 쓰므로 PriorityQueue에 Len/Less/Swap과 Push/Pop을 직접 구현한다. Less가 dist 기준 최소 힙을 만들고, 나머지 갱신 로직은 Python·Java와 같다.

import (
    "container/heap"
    "math"
)
 
type Item struct {
    node, dist, idx int
}
 
type PriorityQueue []*Item
 
func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*Item)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[:n-1]
    return item
}
 
func Dijkstra(start int, graph [][]Edge) []int {
    dist := make([]int, len(graph))
    for i := range dist {
        dist[i] = math.MaxInt64
    }
    dist[start] = 0
 
    pq := &PriorityQueue{}
    heap.Push(pq, &Item{node: start, dist: 0})
    visited := make([]bool, len(graph))
 
    for pq.Len() > 0 {
        current := heap.Pop(pq).(*Item)
        u := current.node
 
        if visited[u] {
            continue
        }
        visited[u] = true
 
        for _, edge := range graph[u] {
            if dist[u]+edge.weight < dist[edge.node] {
                dist[edge.node] = dist[u] + edge.weight
                heap.Push(pq, &Item{node: edge.node, dist: dist[edge.node]})
            }
        }
    }
    return dist
}

주의사항

항목	설명
음수 가중치	Dijkstra 사용 불가 → 음수 간선을 허용하는 Bellman-Ford 사용
방문 체크	중복 연산 방지를 위해 필수
경로 역추적	parent 배열에 갱신 시점의 u 저장

응용 분야

GPS/지도 서비스 길찾기
네트워크 라우팅
게임 AI 경로 탐색
소셜 네트워크 최단 관계 분석

가중치가 비음수인 경로 비용 최소화 문제라면 대부분 그대로 대응한다.

정리

Dijkstra 알고리즘은 비음수 가중치 그래프에서 최단 경로를 구하는 대표적 알고리즘이다. 우선순위 큐를 사용하면 $O(E \log V)$ 로 구현할 수 있다. 음수 가중치 간선이 있으면 정확성이 깨지므로 이때는 Bellman-Ford를 쓴다. 거리뿐 아니라 경로 자체가 필요하면 갱신 시점의 정점을 parent 배열에 저장해 역추적한다. 구현 언어가 달라도 최소 거리 정점을 먼저 꺼내고 방문 정점을 건너뛰는 핵심 로직은 동일하다.