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

Dijkstra 알고리즘이란?

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

입력/출력

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

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

알고리즘 아이디어

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

예시: 동작 과정

그래프 (A=0, B=1, C=2, D=3, E=4):
A --2-- B --3-- D
|       |       |
5       1       1
|       |       |
+------ C --5-- E

간선: A-B(2), A-C(5), B-C(1), B-D(3), C-D(2), D-E(1), C-E(5)

단계	처리 정점	dist 배열
초기	-	[0, ∞, ∞, ∞, ∞]
1	A	[0, 2, 5, ∞, ∞]
2	B	[0, 2, 3, 5, ∞]
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 구현

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 구현

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 구현

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)로 효율적으로 구현할 수 있습니다.