최단경로 알고리즘 - 다익스트라 (Dijkstra)
목차
최단경로 문제
가중치 그래프에서 두 노드를 잇는 가장 짧은 경로를 찾는 문제. 간선 가중치 합이 최소가 되는 경로를 탐색.
다익스트라 알고리즘
컴퓨터 과학자 다익스트라가 고안. 출발 노드에서 다른 노드로 가는 가장 짧은 경로 탐색.
음수 가중치를 가지지 않는 문제에만 적용 가능
동작 원리
- 시작 노드 거리를 0, 다른 모든 노드 거리를 무한대로 설정
- 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택하여 최소 힙 큐에 추가
- 큐에서 하나를 꺼내어 현재까지의 거리 + 간선 가중치를 계산
- 계산된 값이 기존 거리보다 작으면 거리를 업데이트하고 큐에 추가
- 큐가 빌 때까지 3, 4번을 반복
구현
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
queue = [(0, start)]
while queue:
node_distance, node = heapq.heappop(queue)
# 기록된 거리가 현재 노드 값보다 작은 경우 제외
if distances[node] < node_distance:
continue
for neighbor, weight in graph[node].items():
distance = node_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
# 그래프 예시
graph = {
'A': {'B': 4, 'C': 2},
'B': {'D': 3, 'E': 1},
'C': {'B': 1, 'D': 5},
'D': {'E': 2},
'E': {}
}
result = dijkstra(graph, 'A')
print(f"Node A로부터의 최단 거리: {result}")