[알고리즘] 다익스트라(Dijkstra) 알고리즘 with heapq

[알고리즘] 다익스트라(Dijkstra) 알고리즘

• 다익스트라 알고리즘: 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용할 수 있는 최단 경로 알고리즘

• 입력 예시

  # 6개의 노드(1~6), 11개의 간선
  6 11
  # 시작 노드
  1
  # a, b, c: a 노드에서 b 노드로 가는 비용 c
  1 2 2
  1 3 5
  1 4 1
  2 3 3
  2 4 2
  3 2 3
  3 6 5
  4 3 3
  4 5 1
  5 3 1
  5 6 2

• 우선순위 큐(heapq)를 이용한 풀이

  import heapq
  import sys
  input = sys.stdin.readline
  INF = int(1e9)
  
  n, m = map(int, input().split())
  start = int(input())
  graph = [[] for i in range(n+1)]
  distance = [INF] * (n+1) # 최단 거리 테이블 무한으로 초기화
  
  # 간선 정보 입력받기
  for _ in range(m):
      a, b, c = map(int, input().split())
      graph[a].append((b,c))
  
  def dijkstra(start):
      q = []
      # 시작 노드로 가기 위한 최단 경로는 0으로 설정, 큐에 삽입
      heapq.heappush(q, (0, start))
      distance[start] = 0
  
      while q:
          # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
          dist, now = heapq.heappop(q)
          # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
          if distance[now] < dist:
              continue
          # 현재 노드와 연결된 다른 인접한 노드들을 확인
          for i in graph[now]:
              cost = dist + i[1]
              # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
              if cost < distance[i[0]]:
                  distance[i[0]] = cost
                  heapq.heappush(q, (cost, i[0]))
  
  dijkstra(start) 
  
  # 모든 노드로 가기 위한 최단 거리 출력
  for i in range(1, n+1):
      if distance[i] == INF:
          print("INF")
      else:
          print(distance[i])

• 출력

  0
  2
  3
  1
  2
  4