TIL : 다익스트라 알고리즘 (5)

💻 알고리즘

 ✔️ 다익스트라 알고리즘

그래프 이론 알고리즘 중 목적지에서 다른 노드로 이동할 때 최단 경로를 계산하는 알고리즘이다!

이 알고리즘의 특징과 동작 원리는 다음과 같다.

 

💡 특징

1. 최단 거리를 기록할 추가적인 테이블이 필요하다.
2. 그리디 알고리즘과 비슷한 면이 있다.

💡 동작 원리

1. 출발 노드를 정하고 최단거리 테이블을 초기화한다.
2. 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다.
3. 거리를 계산해서 더 짧은 거리라면 최신화해준다.
4. 2번, 3번 과정을 반복한다.

 

import heapq

def dijkstra(graph, start):
  # 최단거리 계산용 리스트, INF는 무한대를 의미한다.
  distance = [INF] * (size + 1)
  distance[start] = 0
  queue = []
  # 방문하지 않은 노드 중 가장 cost가 적은 노드를 선택하기 위해서 heapq를 사용
  heapq.heappush(queue, [0, start])

  while queue:
    current_cost, current_node = heapq.heappop(queue) 

	# 기존에 있는 비용보다 더 비용이 크다면 따질 필요가 없다.
    if distance[current_node] < current_cost: continue
    
    for next_cost, next_node in graph[current_node]:
      new_cost = current_cost + next_cost
      if new_cost < distances[next_node]: 
        distances[next_node] = new_cost
        heapq.heappush(queue, [new_cost, next_node])
    
  return distance