IT용어위키



최단경로 알고리즘

두 노드를 잇는 최단 경로를 구하기 위한 알고리즘
  • 라우팅 프로토콜, 길찾기 서비스 등에서 이용

최단경로 문제의 구분

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

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

알고리즘 종류


  출처: IT위키(IT위키에서 최신 문서 보기)
  * 본 페이지는 공대위키에서 미러링된 페이지입니다. 일부 오류나 표현의 누락이 있을 수 있습니다. 원본 문서는 공대위키에서 확인하세요!