최단 경로 알고리즘은 지하철 노선도, 지도 등 경로탐색에 사용되는 알고리즘으로, 이번 포스트는 Python을 이용해 하나의 시작점으로 부터 모든 도착점까지의 최단 경로를 찾는 최단 경로 알고리즘인 다익스트라(dijkstra) 알고리즘에 대해서 알아 보려고 합니다.
자료구조인 graph를 사용하여 노드와 가중치를 가진 간선 을 이용하여 실제 거리를 표현함
알고리즘을 간단히 요약하면 다음과 같음
다익스트라 알고리즘을 실행 하는 중에는 방문하지 않은 인접 노드를 방문하는 부분에 대해 우선순위 큐(heapq 모듈을 이용해 구현)를 사용 하면, 지금까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산할 수 있으며, 더 긴 거리로 계산 되었을 시 스킵 또한 가능
graph = {
'0': {'1': 8},
'1': {'0': 1, '2': 2, '3': 2},
'2': {'1': 2, '6': 3, '5': 6},
'3': {'1': 2, '4': 1, '5': 4},
'4': {'3': 1},
'5': {'2': 6, '3': 4},
'6': {'2': 3}
}
그림에 그래프를 예시로 작성함(노드가 숫자로 되어있어 순서의 방향이 헷갈릴 수 있으나 문자로 인식하고 노드에 연결된 모든 인접 노드를 표시해야함)
import heapq # 우선순위 큐 구현을 위함
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph} # start로 부터의 거리 값을 저장하기 위함
distances[start] = 0 # 시작 값은 0이어야 함
queue = []
heapq.heappush(queue, [distances[start], start]) # 시작 노드부터 탐색 시작 하기 위함.
while queue: # queue에 남아 있는 노드가 없으면 끝
current_distance, current_destination = heapq.heappop(queue) # 탐색 할 노드, 거리를 가져옴.
if distances[current_destination] < current_distance: # 기존에 있는 거리보다 길다면, 볼 필요도 없음
continue
for new_destination, new_distance in graph[current_destination].items():
distance = current_distance + new_distance # 해당 노드를 거쳐 갈 때 거리
if distance < distances[new_destination]: # 알고 있는 거리 보다 작으면 갱신
distances[new_destination] = distance
heapq.heappush(queue, [distance, new_destination]) # 다음 인접 거리를 계산 하기 위해 큐에 삽입
return distances