다익스트라 알고리즘

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

1 개요

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

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

2 동작 원리

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

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

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

3 예시

3.1 기본 예시

다음은 가중치가 있는 그래프에서 시작 정점 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

3.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)

4 구현

다익스트라 알고리즘은 다양한 프로그래밍 언어로 구현할 수 있으며, 대표적인 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

5 응용

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

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

6 한계

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

7 같이 보기

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

8 참고 문헌

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