▶ 다익스트라(Dijkstra) 알고리즘이란? 다이나믹 프로그래밍(DP)를 활용한 최단 경로(Shortest Path) 탐색 알고리즘. 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 구현은 Greedy 알고리즘이나 DP 알고리즘을 사용하는데, Greedy 알고리즘을 사용할 수 있는 이유는 인접한 노드들 중 가장 작은 비용을 갖고 있는 노드를 선택하여 탐색을 진행하기 때문이다. DP 알고리즘을 활용할 수 있는 이유는 "최단 거리는 여러 개의 최단 거리들"로 이루어져있기 때문이다. (최단 거리 = 최단 거리 정보들의 합) 위의 그림은 a(1)와 b(5)사이의 최단 경로를 찾는 다익스트라 알고리즘의 흐름을 보여준다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인..
