알고리즘 - 다익스트라

• 한 노드에서 다른 모든 노드까지 가는데 최소비용
• 작동 원리
  • 간선 : 인접 리스트
  • 거리 배열 : 초기값 무한대로 설정
  • 힙 시작점 추가
  • 힙에서 현재 노드 빼면서, 간선 통할 때 더 거리 짧아진다면
    • 거리 갱신 및 힙에 추가

# 초기값 갱신
dist[K] = 0
# K는 시작 값
heapq.heappush(heap,(0,K))

while heap:
	# w : 현재 비용, v : 현재 노드
	w, v = heapq.heappop(heap)
    # v가 갱신되기 전 경로면 그냥 버리기
    if w != dist[v]:
    	continue
    for nw,nv in edge[v]:
    	if dist[nv] > dist[v] + nw:
        	dist[nv] = dist[v] + nw
            heapq.heappush(heap, (dist[nv],nv))