- 두 노드를 잇는 최단 경로를 구하기 위한 알고리즘
- 라우팅 프로토콜, 길찾기 서비스 등에서 이용
최단경로 문제의 구분
Shortest path problem
- 단일 출발 최단경로: 특정 노드에서 출발하여 다른 모든 노드에 도착하는 최단 경로 찾기
- single-source shortest path problem
- 단일 도착 최단경로: 모든 노드들에서 출발하여 특정 노드에 도착하는 최단 경로 찾기
- single-destination shortest path problem
- 단일 쌍 최단 경로: 특정 노드에서 출발하여 특정 노드에 도착하는 최단 경로 찾기
- single-pair shortest path problem
- 전체 쌍 최단 경로: 모든 출발지-도착지 쌍에 대한 최단 경로 찾기
- all-pair shortest path problem
최적 부분경로
Optimal substructure
- 최단경로의 부분경로는 역시 최단경로라는 전제
- 어떤 문제의 해가 그 부분문제들의 최적해로 구성되어 있다면 그 해는 최적해가 됨
- 이 속성을 이용하여 다이나믹 프로그래밍이나 탐욕 알고리즘 적용 가능