다익스트라 알고리즘
다익스트라 알고리즘(Dijkstra's Algorithm)은 주어진 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 데 유용하며, 특히 가중치가 모두 양수일 때 효율적으로 작동한다.
🔍 예제 그래프
정점: A, B, C, D, E
간선: (A-B, 2), (A-D, 1), (B-C, 4), (B-D, 3), (C-E, 1), (D-E, 6) 2 4
A ------- B ------- C
\ / \ /
\ 1 / \ 3 / 1
\ / \ /
\ / \ /
D -------- E
6
🔍 단계
1. 초기화
시작 정점에서 다른 모든 정점까지의 거리를 무한대로 설정한다.
단, 시작 정점의 거리는 0으로 설정한다.
시작 정점에서부터의 최단 경로를 추적하기 위해, 시작 정점을 포함한 집합(보통 visited 또는 S로 불림)을 초기화한다.
시작 정점 A에서 다른 모든 정점까지의 거리를 무한대로 설정합니다.
시작 정점 A의 거리를 0으로 설정합니다.
초기 거리 배열: [A: 0, B: ∞, C: ∞, D: ∞, E: ∞]2. 반복
현재까지 방문한 정점들 중에서 최단 거리가 가장 짧은 정점을 선택한다.
선택된 정점에서 인접한 모든 정점에 대해 현재까지 알려진 최단 거리와 새로운 경로를 통한 거리를 비교하여, 더 짧은 경로를 발견하면 그 거리를 업데이트한다.
선택된 정점을 visited 집합에 추가하고, 더 이상 업데이트할 정점이 없을 때까지 이 과정을 반복한다.
2-1. 현재까지 방문한 정점들 중에서 최단 거리가 가장 짧은 정점을 선택한다.
2-2. A에서 출발하여 인접한 정점 B와 D를 방문하고, 거리를 업데이트한다.
- A에서 B로 가는 거리는 2, A에서 D로 가는 거리는 1이다.
- 거리 배열 업데이트: [A: 0, B: 2, C: ∞, D: 1, E: ∞]
2-3. D를 선택하고 인접한 정점 B와 E를 방문한다.
- D에서 B로 가는 거리는 3이므로, 총 거리는 4이다.
이는 기존 거리 2보다 크므로 업데이트하지 않는다.
- D에서 E로 가는 거리는 6이므로, 총 거리는 7이다.
- 거리 배열 업데이트: [A: 0, B: 2, C: ∞, D: 1, E: 7]
2-4. B를 선택하고 인접한 정점 C와 D를 방문한다.
- B에서 C로 가는 거리는 4이므로, 총 거리는 6이다.
- 거리 배열 업데이트: [A: 0, B: 2, C: 6, D: 1, E: 7]
2-5. C를 선택하고 인접한 정점 E를 방문한다.
- C에서 E로 가는 거리는 1이므로, 총 거리는 7이다.
이는 기존 거리 7과 동일하므로 업데이트하지 않는다.
2-6. 더 이상 업데이트할 정점이 없으므로 알고리즘을 종료한다.3. 종료
모든 정점에 대해 최단 거리가 결정되면 알고리즘이 종료되고, 시작 정점으로부터 각 정점까지의 최단 경로가 계산된다.
최종 거리 배열: [A: 0, B: 2, C: 6, D: 1, E: 7]💡 특징
가중치가 있는 그래프에서만 동작한다. 최단 경로 탐색에 사용되며, 현재 정점에서 최단 거리를 가지는 인접 정점을 선택하는 탐욕적 접근법을 사용한다. 효율성을 높이기 위해 우선순위 큐(보통 힙 구조)를 사용하여 최단 거리를 가지는 정점을 빠르게 선택한다.
🙆♀️ 장점
가중치가 양수인 그래프에서 최단 경로를 빠르게 찾을 수 있다. 알고리즘의 논리적 흐름이 비교적 간단하고 직관적이다. 네트워크 경로 찾기, 지도 서비스의 최단 경로 계산, 교통 시스템 최적화 등 다양한 실세계 문제에 적용될 수 있다. 특정 시작 정점에서 다른 모든 정점까지의 최소 비용 경로를 정확하게 계산할 수 있다.
🙅♀️ 단점다익스트라 알고리즘은 음수 가중치를 포함하는 그래프에서는 동작하지 않으므로, 이런 경우에는 벨만-포드 알고리즘 등을 사용해야 한다. 기본 구현의 경우 시간 복잡도가 O(V^2)로, 정점의 수가 많을 때 비효율적일 수 있다. 힙 구조를 사용하면 O((V+E)logV)로 개선할 수 있지만, 대규모 그래프에서는 부담이 될 수 있다. 한 번의 실행으로 단일 시작 정점에서 다른 모든 정점까지의 최단 경로만을 찾을 수 있다. 모든 정점 쌍 간의 최단 경로를 찾으려면 모든 정점에 대해 반복 실행해야 한다.
💻 빈출 예제
1. 네트워크 라우팅
문제: 네트워크에서 각 라우터를 정점으로, 라우터 간의 연결을 간선으로 표현한 그래프가 주어진다. 라우터 A에서 라우터 B까지의 최소 지연 시간을 찾아라.
예제 입력
시작 라우터 : A
라우터 간의 지연 시간 :
A -> B (2)
A -> C (5)
B -> C (1)
B -> D (3)
C -> D (2)예제 코드
import heapq
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# 그래프 정의
graph = {
'A': [('B', 2), ('C', 5)],
'B': [('A', 2), ('C', 1), ('D', 3)],
'C': [('A', 5), ('B', 1), ('D', 2)],
'D': [('B', 3), ('C', 2)]
}
# 시작 라우터 A로부터의 최단 경로 계산
distances = dijkstra(graph, 'A')
print(distances) # 결과: {'A': 0, 'B': 2, 'C': 3, 'D': 5}2. 지도에서 최단 경로 찾기
문제: 도시를 정점으로, 도시 간의 도로를 간선으로 표현한 그래프가 주어진다. 한 도시에서 다른 도시까지의 최단 경로를 찾아라.
예제 입력
시작 도시 : 서울
도시 간 거리 :
서울 -> 부산 (400)
서울 -> 대전 (150)
대전 -> 부산 (250)
대전 -> 광주 (200)
광주 -> 부산 (150)예제 코드
import heapq
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# 그래프 정의
graph = {
'서울': [('부산', 400), ('대전', 150)],
'부산': [('서울', 400), ('대전', 250), ('광주', 150)],
'대전': [('서울', 150), ('부산', 250), ('광주', 200)],
'광주': [('대전', 200), ('부산', 150)]
}
# 시작 도시 서울로부터의 최단 경로 계산
distances = dijkstra(graph, '서울')
print(distances) # 결과: {'서울': 0, '부산': 400, '대전': 150, '광주': 350}