다익스트라 최단경로 최소비용

최단경로지만 경로마다 가중치가 다를때 다익스트라 알고리즘을 사용한다고한다

 

하지만 코드만 보면 어떻게 동작 하는지 이해가 안되서 그려보면서 이해했다.

 

아래의 상황은 1번노드에서 부터 출발해서 나머지 노드들의 까지의 최단거리 테이블을 구하는 과정이다

 

핵심은  연결된 노드거리를 최솟값으로 업데이트해주면서 업데이트된 노드들을 우선순위 큐에 넣는걸 

 

큐가 빌때까지 반복하면된다.