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