Python으로 다익스트라(dijkstra) 알고리즘 구현하기
최단 경로를 찾아보자 2020-05-31

최단 경로 알고리즘은 지하철 노선도, 네비게이션 등 다방면에 사용되는 알고리즘입니다. 이번 시간에는 Python을 이용해 하나의 시작 정점으로 부터 모든 다른 정점까지의 최단 경로를 찾는 최단 경로 알고리즘인 다익스트라(dijkstra) 알고리즘에 대해서 알아 보려고 합니다.

목차

  1. 최단 경로 알고리즘의 아이디어
  2. 사전 배경 지식
  3. 코드 구현

최단 경로 알고리즘의 아이디어

최단 경로 알고리즘의 아이디어는 다음과 같습니다. 자료 구조로는 graph 를 사용하며, 노드가중치를 가진 간선 을 이용하여 실제 거리를 표현합니다. 알고리즘을 간단하게 설명 하자면, 다음과 같습니다.

  1. 출발 노드와, 도착 노드를 설정
  2. 알고 있는 모든 거리 값을 부여
  3. 출발 노드부터 시작하여, 방문하지 않은 인접 노드를 방문, 거리를 계산한 다음, 현재 알고있는 거리보다 짧으면 해당 값으로 갱신한다.
  4. 현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면, 현재 노드는 방문한 것이므로, 미방문 집합에서 제거한다.
  5. 도착 노드가 미방문 노드 집합에서 벗어나면, 알고리즘을 종료한다.

사전 배경 지식

다익스트라 알고리즘을 실행 하는 중에는 방문하지 않은 인접 노드를 방문하는 부분이 있습니다. 이 부분에서 우선순위 큐를 사용 하면, 지금까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산할 수 있으며, 더 긴 거리로 계산 되었을 시 스킵 또한 가능합니다.

우선순위 큐는 heapq 모듈을 이용해 구현 할 수 있습니다.

https://justkode.kr/python/pygorithm-2 (heapq 부분 참조)

코드 구현

  • 출발 노드와, 도착 노드를 설정 (전체 거리를 알고 싶을 때는, 출발 노드만 설정 하여도 무방)
  • 알고 있는 모든 거리 값을 부여 (Python에서는 dictionary 객체를 이용하여 graph를 표현 할 수 있다.)
graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

  • 출발 노드부터 시작하여, 방문하지 않은 인접 노드를 방문, 거리를 계산한 다음, 현재 알고있는 거리보다 짧으면 해당 값으로 갱신한다.
  • 현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면, 현재 노드는 방문한 것이므로, 미방문 집합에서 제거한다.
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

  • 실행 결과

in

print(dijkstra(graph, 'A'))

out

{'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}