Shortest Path   최단 경로

(2021-05-19)

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


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

  ㅇ [참고 용어]
     - 경로 (Path) : 어떤 정점에서 시작하여 특정 정점으로 끝나는 순회/방문/여정
     - 경로 표현 : 두 정점 사이를 잇는 간선 또는 정점들을 순서대로 나열하게됨 (중간에 비면 안됨)
     - 경로 길이 (Path Length)  :  경로 상에 있는 각각의 링크 가중치(거리,시간,비용 등)들의 합
     - 최단 경로 (Shortest Path)  :  모든 가능한 경로 중 최소 경로 길이를 갖는 경로
     - 방향 그래프 (Directed Graph)  :  정점들 간에 방향성이 있는 그래프그래프 종류 참조
     - 가중치 (Weight) : 두 정점 간의 연결선에 수치(비용 등)를 부여한 것
     - 순환 경로 (Cyclic Path)  :  순환적으로 이어지는 간선 또는 경로            ☞ 루프순환 참조


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

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

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

        . 例) A* 알고리즘 (에이 스타 알고리즘)

     - 단일 출발지 최단경로 문제 (single source shortest paths problem)
        . 하나의 출발 정점에서 임의 다른 모든 정점에 대한 최단 경로를 찾는 문제
        . 총 n개 정점에서, (n-1)개의 경로를 구하는 문제

        . 例) 다익스트라 알고리즘, 벨만 포드 알고리즘 등

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

     - 모든 쌍 최단경로 문제 (all pairs shortest paths problem)
        . 모든 쌍 정점 간에 최단 경로를 구하는 문제
           .. 총 n개 정점에서, n(n-1)개의 최단 경로를 구함

        . 例) 플로이드 알고리즘 등

     - 도달 가능성 문제

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


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



Copyrightⓒ written by 차재복 (Cha Jae Bok)
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"