1753 최단경로

다익스트라 알고리즘의 시간 복잡도는 O(V^2)이다. 모든 정점을 한 번씩 방문하면서 방문하지 않은 노드와 최소거리를 찾기 위해서 모든 정점을 탐색하기 때문이다

 

탐색하는 시간은 우선순위 큐로 줄일 수 있다. 매번 정렬을 해야하는 경우, 우선순위 큐를 사용한다고 말했다. 즉 삽입과 삭제가 logE인 우선순위 큐를 사용한다면 빠르게 탐색할 수 있게 된다. 따라서 다익스트라 알고리즘은 O(VlogE)로 해결할 수 있게 된다

 

문제: https://www.acmicpc.net/problem/1753

https://github.com/surinoel/boj/blob/master/1753.cpp