우선 순위 큐

stl 을 이용하며 priority_queue<pair<int,int>> pq; 를 선언한다.

pop 되는 순서 pair 에서 첫번째가 큰 순으로, 그 다음 두번째가 큰 순으로 나온다.

우선 순위 큐를 활용한 다익스트라 알고리즘.

O(ElogV)를 보장하여 해결할 수 있다.
V는 노드 개수 E는 간선 개수이다.
이전 알고리즘은 최단 거리가 가장 짧은 노드를 찾기 위해 모든 원소를 선형 탐색을 해야 했는데 이 부분을 힙(Heap) 자료구조를 이용해 하여 최소 노드를 로그 시간 만에 찾게 만든다.

코드를 입력하세요