다익스트라가 PriorityQueue를 사용하는 이유는 뭐야?

✅ 다익스트라

출발 노드와 그외 노드 간의 최단 거리를 구하는 알고리즘이다.
에지는 항상 양수!
출발 노드와 도착 노드 간의 최단 거리이기도 하지만,
출발 노드와 이외의 모든 노드 간의 최단 거리를 표현하는 것도 맞음에 유의하자.

Queue를 사용해서 풀 수도 있지만 PriorityQueue를 주로 사용한다.

👾
Queue를 사용한 다익스트라 알고리즘은 시간 복잡도가 O(V제곱)인데, O(ElogV)를 보장하여 해결할 수 있기 때문이다.

힙 자료구조를 이용하게되면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다. 이 과정에서 선형 시간이 아닌 로그 시간이 걸린다.

• O( E log V )
  V : 노드의 개수
  E : 간선의 개수