CHAPTER 9. 최단 경로

• 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다.
• 상황에 맞는 효율적인 알고리즘이 정립되어 있다.
• 사례에 맞는 알고리즘을 알고 있어야 문제를 풀기 쉽다.
• 보통 그래프를 이용해 표현되며 각 지점은 노드(node)이고 지점에 연결된 부분은 간선(edge)이다.
• 단순히 최단 거리를 구하는 문제가 많이 출력된다.
• 그리디 및 다이나믹 프로그래밍의 한 유형이다.

그래프, 노드는 보통 마을, 도시 등으로 간선은 도로, 다리 등으로 표현된다.

대표적인 최단 거리 알고리즘

1. 다익스트라 최단 경로 알고리즘
2. 플로이드 워셜
3. 벨만 포드 알고리즘