Dijkstra Algorithm
개요
다익스트라 알고리즘 (Dijkstra Algorithm)은 그래프에서 하나의 시작점에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 비음수 가중치가 있는 그래프에서 최단 경로를 찾을 때 사용되며, 우선순위 큐를 활용하여 효율적으로 탐색할 수 있다.
다익스트라 알고리즘
다익스트라 알고리즘의 기본 동작 방식은 다음과 같다:
1.
시작 노드 설정: 출발점이 되는 시작 노드를 선택하고, 그 노드에서 다른 노드로 가는 경로를 계산한다. 처음에는 시작 노드에서 자신의 거리를 0으로 설정하고, 다른 모든 노드까지의 거리는 무한대로 초기화한다.
2.
방문하지 않은 노드 중에서 최단 거리를 가진 노드 선택: 시작 노드에서 출발하여 인접한 노드 중 가장 가까운 노드를 선택하고 그 노드를 탐색한다. 아직 방문하지 않은 노드들 중에서 현재까지의 최단 거리가 가장 짧은 노드를 선택한다.
3.
최단 거리 갱신: 선택한 노드의 인접한 노드를 확인하고, 해당 노드를 거쳐 가는 경로가 더 짧으면 그 노드까지의 거리를 갱신한다.
4.
이 과정을 반복: 모든 노드를 탐색할 때까지 위의 과정을 반복하며, 한 번 방문한 노드는 다시 방문하지 않는다. 각 노드를 탐색할 때마다 우선순위 큐를 사용하여 가장 작은 값을 가진 노드를 효율적으로 선택한다.
이 과정이 끝나면, 시작점에서 각 노드까지의 최단 경로가 결정된다.
예시
다음은 다익스트라 알고리즘을 적용한 예시이다.
노드 A에서 시작하여 각 노드로 가는 최단 경로를 찾는 문제를 가정한다. 각 경로는 가중치(거리)를 갖는다.
A --2--> B
A --5--> C
B --1--> C
B --4--> D
C --2--> D
D --1--> E
Plain Text
복사
1.
시작 노드인 A를 설정하고, A에서 출발하는 경로를 탐색한다. A에서 B로 가는 경로는 2, A에서 C로 가는 경로는 5이다. 현재까지의 거리:
A: 0, B: 2, C: 5, D: ∞, E: ∞
Plain Text
복사
2.
다음으로 가장 짧은 경로인 B를 선택한다. B에서 C로 가는 경로는 1이므로, A를 통해 B에서 C로 가는 경로는 2 + 1 = 3이다. C의 거리를 갱신한다. B에서 D로 가는 경로는 4이므로 D까지의 거리는 2 + 4 = 6이다. 현재까지의 거리:
A: 0, B: 2, C: 3, D: 6, E: ∞
Plain Text
복사
3.
다음으로 C를 선택하고, C에서 D로 가는 경로는 2이므로, A를 거쳐 C에서 D로 가는 경로는 3 + 2 = 5이다. D의 거리를 갱신한다. 현재까지의 거리:
A: 0, B: 2, C: 3, D: 5, E: ∞
Plain Text
복사
4.
이제 D를 선택하고, D에서 E로 가는 경로는 1이므로, A에서 D를 거쳐 E로 가는 경로는 5 + 1 = 6이다. E의 거리를 갱신한다. 최종 경로:
A: 0, B: 2, C: 3, D: 5, E: 6
Plain Text
복사
우선순위 큐를 기반한 구현 (Python)
다익스트라 알고리즘은 우선순위 큐를 활용하면 효율적으로 구현할 수 있다. Python에서는 heapq 모듈을 사용하여 우선순위 큐를 쉽게 구현할 수 있다.
import heapq
# 다익스트라 알고리즘 구현
def dijkstra(graph, start):
# 시작 노드에서 각 노드까지의 거리 초기화 (무한대)
distances = {node: float('infinity') for node in graph}
distances[start] = 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': 2, 'C': 5},
'B': {'C': 1, 'D': 4},
'C': {'D': 2},
'D': {'E': 1},
'E': {}
}
# A에서 출발하여 각 노드까지의 최단 경로를 계산
shortest_paths = dijkstra(graph, 'A')
print(shortest_paths)
Python
복사
이 코드는 우선순위 큐를 사용하여 다익스트라 알고리즘을 구현한 예시이다. heapq 모듈을 사용해 우선순위 큐를 구현하고, 출발점에서 다른 모든 노드까지의 최단 경로를 계산한다.
요약
다익스트라 알고리즘은 그래프에서 하나의 시작점에서 다른 모든 노드까지의 최단 경로를 찾는 데 사용되는 알고리즘이다. 이 알고리즘은 우선순위 큐를 활용하여 가장 효율적인 경로를 탐색하며, 각 노드에서 인접한 노드로의 최단 거리를 반복적으로 갱신한다. Python의 heapq 모듈을 사용해 쉽게 구현할 수 있으며, 다양한 경로 최적화 문제에 적용된다.
REFERENCES
Written by Changyu Lee