Hoon222y

이번 시간에는 최단거리 알고리즘인 다익스트라(Dijkstra)에 대해 알아보자. 다익스트라 알고리즘의 경우에는 크게 3개의 과정으로 나뉘게 된다. 1) 체크되어 있지 않은 정점 중에서 dist의 값이 가장 작은 정점x를 선택한다.2) x를 체크한다.3) x와 연결된 모든 정점을 검사하며 간선을 (x,y,z)라고 했을 때 dist[y]>dist[x]+z 이면 갱신한다. 그런데 보통 1번과정에서 가장 dist값이 작은 경우를 찾는 과정을 효율적으로 구현하기 위해 priority_queue를 사용한다.- priority_queue 자체가 max heap이기 때문에 -1을 곱해서 음수로 체크를 한다. 123456789101112131415161718192021222324for(int i=1;i