0. 개요
1956년 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)에 의해 고안된 이 알고리즘은, 그래프에서 한 정점(노드)에서 다른 모든 정점까지의 최단 경로를 효율적으로 찾는 방법을 제시한다.
핵심 아이디어
다익스트라 알고리즘의 핵심 아이디어는 단순하면서도 강력하다. 출발점에서 시작하여, 현재까지 알려진 최단 경로를 가진 정점을 선택하고, 그 정점을 통해 갈 수 있는 다른 정점들의 최단 경로를 갱신해나가는 과정을 반복한다. 이 과정을 통해 알고리즘은 그래프의 모든 정점을 방문하게 되며, 각 정점까지의 최단 경로를 모두 찾아낸다.
특징
다익스트라는 '탐욕적'(greedy) 접근 방식을 취한다. 이 말이 무슨 말이나면, 매 단계에서 가장 좋아 보이는 선택(여기서는 최단 거리의 정점)을 한다는 것이다. 이러한 접근 방식이 항상 최적의 결과를 보장하지는 않지만, 다익스트라 알고리즘의 경우 음의 가중치가 없는 그래프에서는 항상 최적의 해를 찾아낸다.
활용 분야
네비게이션 시스템에서 최단 경로를 찾거나, 네트워크에서 최적의 라우팅 경로를 결정하는 데 사용된다. 또한, 인공지능과 로봇공학 분야에서도 경로 계획에 활용되며, 사회 네트워크 분석이나 질병 전파 모델링과 같은 분야에서도 응용된다.
한계
가장 큰 제약은 음의 가중치를 가진 간선을 처리할 수 없다는 점이다. 음의 가중치가 있는 그래프에서는 벨만-포드(Bellman-Ford) 알고리즘이 더 적합할 수 있다. 또한, 모든 정점 쌍 간의 최단 경로를 구해야 하는 경우에는 플로이드-워셜(Floyd-Warshall) 알고리즘이 더 효율적일 수 있다.
1. 동작 방식
시나리오 ① : 출발 노드에서 모든 다른 노드까지의 최단 경로를 찾는 경우 (특정 도착 노드 없음)
- 시작 노드를 정한다.
- 시작 노드에서 모든 노드까지의 거리를 무한대로 초기화한다. 단, 시작 노드 자신까지의 거리는 0으로 설정한다.
- 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택한다.
- 선택한 노드를 거쳐 다른 노드로 가는 경우의 거리를 계산하여, 현재 알려진 거리보다 짧으면 갱신한다.
- 3-4 과정을 모든 노드를 방문할 때까지 반복한다.
예시
다음과 같은 그래프가 있다고 가정해보자.
이 그래프에서 노드 A에서 시작하여 다른 모든 노드까지의 최단 경로를 찾는 과정은 다음과 같다.
| 단계 | 선택노드 | A | B | C | D | E | 설명 |
| 0 | - | 0 | ∞ | ∞ | ∞ | ∞ | 초기 상태 |
| 1 | A | 0 | 4 | 2 | ∞ | ∞ | A에서 직접 연결된 B와 C의 거리 갱신 |
| 2 | C | 0 | 4 | 2 | 5 | 5 | C에서 D와 E로의 거리 갱신 (2+3=5) |
| 3 | B | 0 | 4 | 2 | 5 | 5 | B에서 갱신할 거리 없음 |
| 4 | D | 0 | 4 | 2 | 5 | 5 | D에서 갱신할 거리 없음 |
| 5 | E | 0 | 4 | 2 | 5 | 5 | 모든 노드 방문 완료 |
- 0단계 : 시작 노드 A의 거리를 0으로 설정하고, 나머지 모든 노드의 거리를 무한대(∞)로 초기화한다.
- 1단계 : 가장 가까운 미방문 노드인 A를 선택하고, A에서 직접 연결된 B(거리 4)와 C(거리 2)의 거리를 갱신한다.
- 2단계 : 가장 가까운 미방문 노드인 C를 선택한다. C를 통해 D와 E까지의 거리를 계산한다.(A->C->D = 2+3 = 5, A->C->E = 2+3 = 5) D와 E의 거리를 5로 갱신합니다.
- 3단계 : 다음으로 가까운 B가 선택되고, B를 통한 다른 노드로의 경로가 기존 경로보다 짧지 않아 갱신할 거리가 없다.
- 4단계 : D가 선택되고, D를 통한 E까지의 거리(5+1=6)가 기존 경로(5)보다 짧지 않아 갱신하지 않는다.
- 5단계 : 마지막으로 E가 선택되며, 모든 노드를 방문했으므로 알고리즘이 종료된다.
이 과정을 거치면 A에서 시작하여 각 노드까지의 최단 거리를 얻을 수 있다. (B=4, C=2, D=5, E=5)
시나리오 ② : 출발 노드에서 특정 도착 노드까지의 최단 경로를 찾는 경우
| 단계 | 선택 노드 | A | B | C | D | E | 설명 |
| 0 | - | 0 | ∞ | ∞ | ∞ | ∞ | 초기 상태 |
| 1 | A | 0 | 4 | 2 | ∞ | ∞ | A에서 직접 연결된 B와 C의 거리 갱신 |
| 2 | C | 0 | 4 | 2 | ∞ | 5 | C에서 E로의 가는 거리 갱신 |
| 3 | E | 0 | 4 | 2 | ∞ | 5 | 도착 노드 E에 도달, 알고리즘 종료 |
- 0단계 : 시작 노드 A의 거리를 0으로 설정하고, 나머지 모든 노드의 거리를 무한대(∞)로 초기화한다.
- 1단계 : 가장 가까운 미방문 노드인 A를 선택한다. A에서 직접 연결된 B(거리 4)와 C(거리 2)의 거리를 갱신한다.
- 2단계 : 가장 가까운 미방문 노드인 C를 선택한다. C를 통해 D와 E까지의 거리를 계산한다. (A->C->E->D = 2+3+1 = 6, A->C->E = 2+3 = 5) D와 E의 거리를 5로 갱신한다.
- 3단계 : 다음으로 가까운 미방문 노드이자 목적지인 E를 선택합니다. E는 목적지이므로 알고리즘을 종료한다.
A노드부터 E노드까지 최단 경로는 A -> C -> E이다. (최단 거리: 5)
2. 구현 방법
순차 탐색
순차 탐색을 사용한 다익스트라 알고리즘 구현은 알고리즘의 기본 원리를 가장 직관적으로 보여준다. 이 방법의 핵심은 매 반복마다 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선형 탐색으로 찾는 것이다.
def dijkstra_sequential(graph, start, end):
# 모든 노드에 대해 무한대 거리로 초기화
distances = {node: float('inf') for node in graph}
# 시작 노드의 거리는 0으로 설정
distances[start] = 0
# 방문하지 않은 노드 목록
unvisited = list(graph.keys())
# 각 노드의 이전 노드를 저장할 딕셔너리
previous = {node: None for node in graph}
while unvisited:
# 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택 (순차 탐색)
current = min(unvisited, key=lambda node: distances[node])
# 목적지에 도달했다면 경로를 재구성하고 반환
if current == end:
path = []
while current:
path.append(current)
current = previous[current]
return distances[end], path[::-1]
# 연결된 노드가 없는 경우 중단
if distances[current] == float('inf'):
break
# 현재 노드를 방문 처리
unvisited.remove(current)
# 현재 노드의 이웃 노드들에 대해 거리 갱신
for neighbor, weight in graph[current].items():
distance = distances[current] + weight
# 더 짧은 경로를 발견하면 갱신
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current
# 목적지에 도달하지 못한 경우
return float('inf'), []
# 예시 그래프
graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'D': 3},
'C': {'A': 2, 'E': 3},
'D': {'B': 3, 'E': 1},
'E': {'C': 3, 'D': 1}
}
# 알고리즘 실행
start, end = 'A', 'E'
distance, path = dijkstra_sequential(graph, start, end)
print(f"최단 거리: {distance}")
print(f"경로: {' -> '.join(path)}")
순차 탐색은 코드가 간단하고 이해하기 쉽다. unvisited 리스트와 distances 딕셔너리만을 사용하여 알고리즘을 구현했다. 노드 선택 방식은 current = min(unvisited, key=lambda node: distances[node]) 라인에서 볼 수 있듯이, 매 반복마다 방문하지 않은 모든 노드를 순회하며 최소 거리 노드를 찾는다. 이는 O(V) 시간이 소요되는 작업이다(V는 노드의 수). 전체 알고리즘의 시간 복잡도는 O(V^2)이다. 외부 루프가 최대 V번 반복되고, 각 반복에서 최소 거리 노드를 찾는 데 O(V) 시간이 소요되기 때문이다. 또한 추가적인 자료구조를 사용하지 않아 메모리 사용이 적다. 주요 메모리 사용은 distances, unvisited, previous 딕셔너리/리스트에 국한된다.
우선순위 큐
우선순위 큐는 대규모 그래프에서 매우 효율적으로 동작한다.
import heapq
def dijkstra_priority_queue(graph, start, end):
# 모든 노드에 대해 무한대 거리로 초기화
distances = {node: float('inf') for node in graph}
# 시작 노드의 거리는 0으로 설정
distances[start] = 0
# 우선순위 큐 초기화: (거리, 노드) 형태의 튜플을 저장
queue = [(0, start)]
# 각 노드의 이전 노드를 저장할 딕셔너리
previous = {node: None for node in graph}
while queue:
# 가장 거리가 짧은 노드를 큐에서 추출 (O(log N) 시간 소요)
current_distance, current = heapq.heappop(queue)
# 목적지에 도달했다면 경로를 재구성하고 반환
if current == end:
path = []
while current:
path.append(current)
current = previous[current]
return distances[end], path[::-1]
# 이미 처리된 노드는 무시 (더 긴 경로)
if current_distance > distances[current]:
continue
# 현재 노드의 이웃 노드들에 대해 거리 갱신
for neighbor, weight in graph[current].items():
distance = current_distance + weight
# 더 짧은 경로를 발견하면 갱신
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current
# 우선순위 큐에 새로운 거리 정보 추가 (O(log N) 시간 소요)
heapq.heappush(queue, (distance, neighbor))
# 목적지에 도달하지 못한 경우
return float('inf'), []
# 예시 그래프
graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'D': 3},
'C': {'A': 2, 'E': 3},
'D': {'B': 3, 'E': 1},
'E': {'C': 3, 'D': 1}
}
# 알고리즘 실행
start, end = 'A', 'E'
distance, path = dijkstra_priority_queue(graph, start, end)
print(f"최단 거리: {distance}")
print(f"경로: {' -> '.join(path)}")heapq 모듈을 사용하여 우선순위 큐를 구현했다. 이를 통해 최소 거리 노드를 O(log V) 시간에 선택할 수 있다. 노드 선택 방식은 current_distance, current = heapq.heappop(queue) 라인에서 볼 수 있듯이, 최소 거리 노드를 상수 시간에 추출한다. 이는 순차 탐색 방식과 비교했을 때 큰 성능 향상을 가져온다. 전체 알고리즘의 시간 복잡도는 O((V+E)log V)이다. 여기서 E는 간선의 수이다. 각 노드와 간선에 대해 최대 한 번씩 힙 연산을 수행하기 때문이다. 한편, 이 방법으로 구현하면 우선순위 큐를 위한 추가 메모리가 필요하다. queue 리스트가 이 역할을 수행하며, 최악의 경우 모든 노드와 간선 정보를 저장할 수 있어야 한다.
순차 탐색 vs 우선순위 큐 (차이점)
| 특징 | 순차 탐색 | 우선순위 큐 |
| 시간 복잡도 | O(V^2) | O((V+E)log V) |
| 공간 복잡도 | O(V) | O(V) |
| 구현 난이도 | 쉬움 | 중간 |
| 대규모 그래프 성능 | 낮음 | 높음 |
| 메모리 사용 | 적음 | 비교적 많음 |
| 최소 거리 노드 선택 | O(V) | O(log V) |
| 적합한 사용 사례 | 작은 그래프, 교육 목적 | 대규모 그래프, 실제 응용 |
'TIL' 카테고리의 다른 글
| [TIL] 다이나믹 프로그래밍(Dynamic Programming, DP) (0) | 2024.09.27 |
|---|---|
| 최소 신장 트리(Minimum Spanning Tree, MST) : 가장 경제적인 방식으로 모든 지점을 연결한다 (4) | 2024.09.25 |
| 위상 정렬(Topological Sort) (4) | 2024.09.22 |
| 알고리즘 그래프 탐색 - DFS(깊이 우선 탐색) (1) | 2024.09.22 |
| 리턴은 단순한 관행인가? 파이썬에서 리턴을 사용하는 이유 (1) | 2024.09.22 |