최단 경로 알고리즘 그래프에서 노드 간의 가장 짧은 경로를 찾고자 할 때 사용한다. 알고리즘의 종류는 3가지로 문제의 요구사항과 간선에 부여된 가중치의 상태에 따라 효과적인 알고리즘을 골라 사용하면 된다. 1. 다익스트라(Dijkstra) 다익스트라 알고리즘은 특정한 하나의 노드에서 다른 모든 노드로 가는 최단 경로를 구할 수 있다. 간선의 가중치가 0 이상으로 이루어져 있을 때 사용할 수 있다. 매번 가장 적은 비용을 선택해가며 이를 그대로 사용하기에 그리디+DP 문제이다. 작동 과정은 다음과 같다. ① 출발 노드 설정 ② 출발 노드를 기준으로 최단 경로 배열 갱신 ③ 방문하지 않은 노드 중에서 비용이 가장 적은 노드 선택 ④ 해당 노드를 거쳐 다른 노드로 가는 최단 경로 갱신 ⑤ 3, 4번을 반복 #..
