다익스트라(Dijkstra) 알고리즘
다익스트라(Dijkstra) 알고리즘 DP를 활용한 최단 경로 탐색 알고리즘 다익스트라 알고리즘은 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 기록한다. 여기서 DP가 적용되는 이유는, 굳이 한 번 최단 거리를 구한 곳은 다시 구할 필요가 없기 때문이다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할 때 최단 거리를 효율적으로 구할 수 있다. 다익스트라를 구현하기 위해 두 가지를 저장해야 한다. 해당 정점까지의 최단 거리를 저장 정점을 방문했는 지 저장 시작 정점으로부터 정점들의 최단 거리를 저장하는 배열과, 방문 여부를 저장하는 것이다. 다익스트라의 알고리즘 순서는 아래와 같다. 최단 거리 값은 무한대 값으로 초기화한다. for(int i = 1; i
