- 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘, 길찾기 문제라고도 불림
- 다양한 유형이 존재(한지점에서 특정 지점까지 최단 경로, 모든 지점에서 다른 모든 지점까지 모든 최단경로 등)
- 그래프로 표현(지점-노드, 도로-간선)
- 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다.
- 다익스트라 최단 경로 알고리즘
- 플로이드 워셜
- 벨만 포드 알고리즘
'코딩 테스트 > 최단 경로' 카테고리의 다른 글
| 전보 (0) | 2021.03.10 |
|---|---|
| 미래 도시 (0) | 2021.03.09 |
| 플로이드 워셜 알고리즘 (0) | 2021.03.09 |
| 다익스트라 최단 경로 알고리즘 (0) | 2021.02.28 |
댓글