다익스트라 알고리즘

다익스트라 알고리즘(Dijkstra algorithm, 다익스트라 算法)은 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다.

개요

다익스트라 알고리즘은 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)가 1956년에 고안하고 1959년에 발표한 알고리즘이다. 가중치가 있는 방향 또는 무방향 그래프에서 음의 가중치가 없는 경우에 사용할 수 있으며, 시작 정점에서 다른 모든 정점까지의 최단 경로를 효율적으로 계산할 수 있다.

현대에서도 길 찾기, 라우팅 알고리즘 등에 많이 사용된다. 음의 가중치가 있는 그래프에선 동작하지 않는 문제점이 있으나, 실생활에선 음의 가중치가 존재하는 경우가 흔치 않기 때문에 크게 문제되지 않는 경우가 많다.

동작 원리

다익스트라 알고리즘은 다음과 같은 방식으로 작동한다.

• 모든 정점의 거리를 무한대로 초기화하고, 시작 정점의 거리를 0으로 설정한다.
• 아직 방문하지 않은 정점 중에서 거리 값이 가장 작은 정점을 선택한다.
• 선택된 정점과 인접한 정점들의 거리 값을 갱신한다.
• 모든 정점을 방문할 때까지 이 과정을 반복한다.

이 알고리즘은 우선순위 큐를 활용하면 시간 복잡도를 효율적으로 줄일 수 있다. 일반적인 구현에서는 최소 힙(min-heap)을 이용한 우선순위 큐를 사용하여 O((V+E)logV)의 시간 복잡도를 가진다.

예시

기본 예시

다음은 가중치가 있는 그래프에서 시작 정점 A에서 다른 모든 정점까지의 최단 경로를 구하는 예이다.

그래프:

A --(4)--> B --(1)--> C
 \         |
  \       (2)
   \       v
    (2)--> D

단계별 계산

다익스트라 알고리즘을 통해 A에서 시작해 모든 정점까지의 최단 경로를 구하는 과정을 표로 나타내면 다음과 같다.

단계	기준점	B까지 거리	C까지 거리	D까지 거리	비고
0	A	∞	∞	∞	초기화
1	A	4	∞	2	A → B(4), A → D(2) 직접 연결됨
2	D	4	∞	2	A와 거리가 가장 가까웠던 D 선택 D를 거쳐서 더 짧아지는 경로 없음
3	B	4	5	2	그 다음 A와 거리가 가장 가까웠던 B 선택 C로 갈 수 있게 됨
4	C	4	5	2	마지막으로 방문하지 않은 C 선택 변동 없음

최종적으로 각 정점까지의 최단 거리는 다음과 같다:

• A: 0
• B: 4
• C: 5
• D: 2

좀 더 어려운 예시

단계	기준점	A	B	C	D	E	F	G	H	우선순위 큐
0	A	0	∞	∞	∞	∞	∞	∞	∞	B(∞), C(∞), D(∞), E(∞), F(∞), G(∞), H(∞)
1	A	(0)	1	5	11					B(1), C(5), D(11)
2	B		(1)	3		11				C(3), D(11), E(11)
3	C			(3)		9	4			F(4), E(9), D(11)
4	F					8	(4)	7	5	H(5), G(7), E(8), D(11)
5	H					7		6	(5)	G(6), E(7), D(11)
6	G				7			(6)		E(7), D(7)
7	E					(7)				D(7)
8	D				(7)

구현

다익스트라 알고리즘은 다양한 프로그래밍 언어로 구현할 수 있으며, 대표적인 Python 구현은 다음과 같다.

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, (distance, adjacent))

    return distances

graph = {
    'A': {'D': 11, 'C': 5, 'B': 1},
    'B': {'C': 2, 'E': 10},
    'C': {'F': 1, 'E': 6},
    'D': {'C': 3},
    'E': {},
    'F': {'D': 5, 'E': 4, 'G': 3, 'H': 1},
    'G': {'D': 1},
    'H': {'E': 2, 'G': 1}
}

dist = dijkstra(graph, 'A')

print("\nFinal distances from A:")
for node in sorted(dist):
    print(f"{node}: {dist[node]}")

결과:

Final distances from A:
A: 0
B: 1
C: 3
D: 7
E: 7
F: 4
G: 6
H: 5

응용

다익스트라 알고리즘은 다음과 같은 분야에서 활용된다.

• GPS 내비게이션 시스템
• 네트워크 라우팅 프로토콜 (예: OSPF)
• 게임의 경로 탐색 시스템
• 물류 및 운송 경로 최적화

한계

다익스트라 알고리즘은 음의 가중치를 가진 간선이 포함된 그래프에서는 사용할 수 없다. 이러한 경우에는 벨만-포드 알고리즘을 사용해야 한다.

같이 보기

• 벨만-포드 알고리즘
• A* 알고리즘
• 최단 경로 문제
• 그래프 이론
• 우선순위 큐

참고 문헌

• Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. *Numerische Mathematik*, 1(1), 269–271.