Cherry & Cherish

최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 보통 그래프를 이용해서 표현하고, 각 지점은 그래프에서 노드로 표현되고 지점간 연결된 도로는 그래프에서 간선으로 표현된다. ‘한 지점에서 특정 지점까지의 최단 경로를 구해야하는 경우’, ‘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우’ 등 다양한 사례가 존재한다. 일반적으로 사용하는 최단거리 알고리즘은 ‘다익스트라 알고리즘’, ‘플로이드 워셜 알고리즘’, ‘벨만 포드 알고리즘’ 등 여러 가지가 존재한다. 그러나 코딩 테스트에서 가장 많이 등장하는 유형은 ‘다익스트라’, ‘플로이드 워셜’ 알고리즘이다. 최단 경로 알고리즘은 DP와 그리디가 그대로 적용된다는 특징이 있다. 따라서, 그리디와 DP 유형의 하나로 보는 경우도 있다..