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)그래프 이론에서, 최단 경로를 찾는 그래프 알고리즘들을 총칭
     - 주로, 단일 출발지로부터 모든 정점까지의 최단 경로를 찾는 탐색 알고리즘


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

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