다익스트라 알고리즘 (Dijkstra's Algorithm)
다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 주로 양의 가중치를 가진 그래프에서 사용되며, 그래프가 음의 가중치를 가진 경우에는 사용할 수 없다.
다익스트라 알고리즘은 그리디 알고리즘(Greedy Algorithm)의 한 종류로, 각 단계에서 가장 비용이 적은 경로를 선택하면서, 그 경로를 확장하는 방식으로 진행된다.
다익스트라 알고리즘의 동작 원리
다익스트라 알고리즘의 핵심 아이디어는 각 노드에 대해 최단 경로를 점차적으로 확장해 나가는 것이다. 출발 노드에서 시작해 다른 모든 노드로 가는 최단 경로를 찾는 과정에서, 매번 가장 비용이 적은 노드를 선택해 최단 경로를 확정짓는다. 각 단계에서 방문하지 않은 노드들 중에서 가장 작은 비용으로 갈 수 있는 노드를 선택한다.
기본 흐름:
- 초기화:
- 출발 노드를 선택하고, 해당 노드까지의 거리를 0으로 설정한다.
- 나머지 노드들은 무한대(∞)로 설정한다.
- 방문할 노드 선택:
- 아직 방문하지 않은 노드 중, 출발 노드에서 가장 짧은 거리를 가진 노드를 선택한다. 처음에는 출발 노드 자체를 선택한다.
- 최단 경로 업데이트:
- 선택한 노드에 연결된 이웃 노드들을 확인하고, 그 이웃 노드들까지의 거리가 더 짧은 경로가 있다면 그 경로를 업데이트한다.
- 방문 완료 처리:
- 현재 선택된 노드는 방문이 완료되었으므로, 해당 노드는 다시 선택하지 않도록 처리한다.
- 모든 노드를 방문할 때까지 반복:
- 모든 노드를 방문할 때까지 위 과정을 반복한다.
이 과정에서 우선순위 큐를 사용하여 가장 비용이 적은 노드를 빠르게 선택하면 알고리즘을 효율적으로 수행할 수 있다.
다익스트라 알고리즘의 동작 예시
예시 그래프:
(A)
1/ \4
(B) (C)
2| \1
(D)---(E)
5이 그래프에서, 노드 A에서 다른 모든 노드까지의 최단 경로를 찾는 과정을 살펴보겠다.
- 초기화:
- 출발 노드 A의 거리를 0으로 설정하고, 다른 노드들은 무한대(∞)로 설정한다.
- 현재 상태:
- A: 0, B: ∞, C: ∞, D: ∞, E: ∞
- A에서 가장 가까운 노드 선택:
- A에서 B까지는 1, C까지는 4이므로 B를 선택한다.
- 현재 상태:
- A: 0, B: 1, C: 4, D: ∞, E: ∞
- B에서 가장 가까운 노드 선택:
- B에서 D까지의 경로는 1(B) + 2 = 3입니다.
- 현재 상태:
- A: 0, B: 1, C: 4, D: 3, E: ∞
- D에서 가장 가까운 노드 선택:
- D에서 E까지의 경로는 3(D) + 5 = 8입니다.
- 현재 상태:
- A: 0, B: 1, C: 4, D: 3, E: 8
- C에서 가장 가까운 노드 선택:
- C에서 E까지의 경로는 4(C) + 1 = 5로, E까지의 기존 경로(8)보다 짧으므로 갱신합니다.
- 현재 상태:
- A: 0, B: 1, C: 4, D: 3, E: 5
- 모든 노드 방문 완료:
- 최종 최단 경로:
- A: 0, B: 1, C: 4, D: 3, E: 5
다익스트라 알고리즘의 구현 (Python)
다음은 우선순위 큐(최소 힙)를 사용하여 다익스트라 알고리즘을 구현한 예시이다. 이를 통해 매번 가장 짧은 경로를 가진 노드를 효율적으로 선택할 수 있다.
import heapq # 우선순위 큐를 위한 heapq 모듈 사용
def dijkstra(graph, start):
# 각 노드까지의 최단 거리를 저장하는 딕셔너리 (초기값: 무한대)
distances = {node: float('inf') for node in graph}
distances[start] = 0 # 시작 노드까지의 거리는 0
# 우선순위 큐를 사용해 최단 경로를 가진 노드를 선택
priority_queue = [(0, start)] # (거리, 노드)
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# 현재 노드까지의 거리가 기존 거리보다 크면 무시
if current_distance > distances[current_node]:
continue
# 현재 노드와 연결된 다른 노드들에 대해 거리를 계산
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# 새로운 경로가 더 짧으면 최단 거리 갱신
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# 테스트를 위한 그래프
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'D': 2},
'C': {'A': 4, 'E': 1},
'D': {'B': 2, 'E': 5},
'E': {'C': 1, 'D': 5}
}
# A 노드에서 시작하여 다른 노드들까지의 최단 거리 계산
print(dijkstra(graph, 'A'))
출력 결과:
{'A': 0, 'B': 1, 'C': 4, 'D': 3, 'E': 5}
코드 설명:
- 초기화:
- distances 딕셔너리를 사용해 각 노드까지의 최단 거리를 ∞로 설정하고, 출발 노드의 거리는 0으로 설정한다.
- priority_queue는 (거리, 노드) 형태의 최소 힙으로, 매번 최단 거리를 가진 노드를 선택하기 위해 사용된다.
- 노드 선택:
- 우선순위 큐에서 최단 거리를 가진 노드를 꺼내어, 해당 노드에 대해 연결된 노드들의 경로를 계산한다.
- 최단 경로 갱신:
- 이웃 노드까지의 거리를 계산하고, 그 값이 기존 최단 거리보다 작다면 해당 경로를 갱신하고, 갱신된 노드를 다시 큐에 추가한다.
- 모든 노드 탐색 완료:
- 큐가 빌 때까지 이 과정을 반복하면, 출발 노드에서 다른 모든 노드까지의 최단 거리를 계산할 수 있다.
다익스트라 알고리즘의 시간 복잡도
우선순위 큐(힙)를 사용하는 경우, 다익스트라 알고리즘의 시간 복잡도는 다음과 같다:
- 노드 개수 V, 간선 개수 E일 때:
- 각 노드를 큐에 삽입하는 비용: O(V log V)
- 각 간선을 처리하는 비용: O(E log V)
따라서, 다익스트라 알고리즘의 전체 시간 복잡도는 O((V + E) log V)이다. 이는 우선순위 큐를 사용하는 다익스트라 알고리즘의 경우에 해당합니다. (간선이 많을수록 O(E log V)가 더 중요해진다.)
다익스트라 알고리즘의 특징
- 양의 가중치에서만 사용 가능:
- 다익스트라 알고리즘은 음수 가중치가 있을 경우에는 올바른 결과를 보장하지 않는다. 음수 가중치가 있는 경우에는 벨만-포드 알고리즘을 사용해야 한다.
- 한 번 방문한 노드는 다시 방문하지 않음:
- 한 번 방문하여 최단 거리가 확정된 노드는 더 이상 업데이트되지 않는다.
- 그리디 알고리즘:
- 다익스트라 알고리즘은 그리디 방식으로 매번 가장 작은 경로를 선택하여 최단 경로를 확정한다.
다익스트라 알고리즘의 응용
다익스트라 알고리즘은 네트워크 경로 최적화, 지도 탐색 애플리케이션(예: 구글 지도), 항공사 예약 시스템 등에서 최단 경로를 찾는 문제에 매우 유용하게 사용된다. 주로 가중치 그래프에서 각 노드 간의 최단 경로를 찾는 데 사용된다.
- 다익스트라 알고리즘은 양의 가중치를 가지는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
- 그리디 방식으로 매번 가장 짧은 경로를 선택하고, 이를 기반으로 경로를 확장해 나간다.
- 우선순위 큐(힙)을 사용하여 효율적으로 구현할 수 있으며, 시간 복잡도는 O((V + E) log V)이다.
- 음의 가중치가 있는 경우에는 사용하지 못하고, 벨만-포드 알고리즘과 같은 다른 알고리즘을 사용해야 한다.
모든 코드는 github에 저장되어 있습니다.
https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms