[알고리즘] 다익스트라 알고리즘 (Dijkstra)

개념 그래프 알고리즘에서 '최소 비용'을 구해야 하는 경우 사용할 수 있는 대표적인 알고리즘은 '다익스트라 알고리즘', '벨만-포드 알고리즘', '플로이드 워샬 알고리즘' 이 있다. 다익스트라 알고리즘은 최소 비용 중에서도 주어진 두 노드(시작노드, 도착노드) 사이의 최소 비용인 경로를 찾을 때 유용하게 사용된다.

특징 다익스트라에서 요구되는 연산은 크게 두 가지이다. 1. 모든 간선을 탐색하는 과정 2.

그 과정 속에서 우선 순위 큐를 조작하는 연산 최단 거리를 구하기 위해 그래프 내 모든 간선을 탐색하게 되므로 해당 시간 복잡도는 O(E)에 해당한다. 우선순위 큐는 들어갈 수 있는 후보..........