Dijkstra Algorithm (다익스트라 알고리즘) with 프로그래머스 - 배달

다익스트라 알고리즘이란? 다익스트라 알고리즘은 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는알고리즘이다.

가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다. 처음 고안되었을때의 다익스트라 알고리즘은 O(N²)의 시간복잡도를 가진다.

이후에 PriorityQueue 를 이용해서 O(NlogN) 까지 시간복잡도를 줄이는 방식이 고안되었다. 다익스트라 알고리즘은 다음과 같다.

(P[A][B]는 A와 B 사이의 거리라고 가정한다. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다.

(정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 .....