[Algorithm] Dijkstra 알고리즘에 대해 알아보자

다익스트라(dijkstra) 알고리즘은 '최단 경로'를 찾을 때 유용하게 쓰인다.

한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이라고 할 수 있다.

 

 

알고리즘의 아이디어

1. 출발 노드와 도착 노드를 설정한다.

2. 알고 있는 모든 거리값을 부여한다.

3. 출발 노드부터 시작하여 방문하지 않은 인접 노드를 방문하여 둘 사이의 거리를 계산한다. 이때 이미 알고 있는 거리보다 짧으면 해당 거리를 갱신한다.

4. 현재 노드에 인접한 모든 노드를 방문했다면 해당 노드는 모든 방문을 끝낸 것이므로 미방문 노드에서 없앤다.

5. 모든 미방문 노드를 방문했다면 알고리즘을 종료한다.

 

 

해당 알고리즘은 파이썬에서 heap을 이용해 구현할 수 있다. 보통 최소 힙으로 정렬이 되기 때문에 최단 경로를 찾을 때 유용하다. 주로 우선순위 큐를 만들 때 쓰인다.

 

 

알고리즘을 코드로 구현하면 다음과 같다.

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