최단경로 알고리즘

두 노드를 잇는 최단 경로를 구하기 위한 알고리즘

• 라우팅 프로토콜, 길찾기 서비스 등에서 이용

최단경로 문제의 구분

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

• 최단경로의 부분경로는 역시 최단경로라는 전제
  • 어떤 문제의 해가 그 부분문제들의 최적해로 구성되어 있다면 그 해는 최적해가 됨
• 이 속성을 이용하여 다이나믹 프로그래밍이나 탐욕 알고리즘 적용 가능

알고리즘 종류

• 다익스트라 알고리즘
• A+ 알고리즘
• 플로이드-와샬 알고리즘
• 벨만-포드 알고리즘