다익스트라

• 최단 경로 문제(Shortest Path Problem)는 일상생활에서 자주 경험하는 문제로, 문제 자체의 역사도 깊고, 응용가치도 커 많은 연구가 이루어진 문제 dijkstra는 인접 노드 중 최단 경로의 길이의 노드로 계속해서 이동하여 최소 경로 길이 계산, 적응형 힙 이용

-code-

n = int(input())
m = int(input())
direct_g = [[] for i in range(n)]
source_node = 0
distance = [float("inf") for i in range(n)]
distance[0] = 0

for i in range(m):
  u, v, w = map(int, input().split())
  direct_g[u].append([v, w])

H = AdaptedHeap()
H.insert(distance[0])
while H:
  u = H.delete_min()
  for i in direct_g[u]:
    if(distance[u] + i[1] < distance[i[0]]):
      old = distance[i[0]]
      distance[i[0]] = distance[u] + i[1]
      H.insert(i[0])