Shortest Path   최단 경로

(2021-02-18)

최적 경로, SPF, Shortest Path First, SPF 알고리즘, 최단 경로 알고리즘, 최단 경로 탐색 알고리즘, 최단 거리 알고리즘

1. 최단 경로 (Shortest Path)그래프 이론에서, 출발지와 목적지 사이 링크들의 가중치 합이 최소가 되는 경로
     - 특히, 그래프방향성이고, 가중치를 갖으며, 순환을 포함하는 경우

  ㅇ [참고용어]
     - 경로 길이 (Path Length)  :  경로 상에 있는 각각의 링크 가중치들의 합
        . 가중치 기준 例 : 거리,시간,비용 등 
     - 최단 경로 (Shortest Path)  :  모든 가능한 경로 중 최소 경로 길이를 갖는 경로


2. 최단 경로 문제 및 그 종류 (Shortest Path Problem)

  ㅇ 다양한 경로들 중에 가장 빠른 경로를 찾는 문제   ☞ 그래프 알고리즘 참조

  ㅇ 최단 경로 문제의 종류
     - 단일 출발지,목적지 최단 경로 문제 (single source, single destination shortest path problem)
        . 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제
        . 또는, 단일 쌍 최단경로 문제 라고도 함

     - 단일 출발지 최단경로 문제 (single source shortest paths problem)
        . 하나의 출발 정점에서 임의 다른 모든 정점에 대한 최단 경로를 찾는 문제
        . 총 n개 정점에서, (n-1)개의 경로를 구하는 문제
        . 例) 다익스트라 알고리즘, 벨만 포드 알고리즘 등

     - 단일 도착지 최단경로 문제 (single destination shortest path problem)
        . 하나의 목적지로 가는 모든 최단 경로를 찾는 문제

     - 모든 쌍 최단경로 문제 (all parts shortest paths problem)
        . 총 n개 정점에서, n(n-1)개의 경로를 구하는 문제
        . 例) 플로이드 알고리즘 등

     - 도달 가능성 문제

  ㅇ 초기 가정
     - 정점을 잇기 전까지는, 시작점을 제외한 모든 정점들은 가중치를 무한대(∞)로 간주 함


3. 최단 경로 알고리즘 (Shortest Path Algorithm, SPF)그래프 이론에서, 최단 경로를 찾는 그래프 알고리즘들을 총칭
     - 주로, 단일 출발지로부터 모든 정점까지의 최단 경로를 찾는 탐색 알고리즘


[그래프 알고리즘] 1. 그래프 알고리즘 2. 그래프 순회 (DFS,BFS) 3. 위상 정렬 4. 최소비용 신장트리 5. 최단 경로 6. 다익스트라 알고리즘 7. 플로이드 알고리즘

 
        최근수정     요약목록     참고문헌