Shortest Path   최단 경로

(2020-07-31)

최적 경로, Dijkstra's Algorithm, Dijkstra 알고리즘, 다익스트라 알고리즘

1. 최단 경로그래프 이론에서 출발지와 목적지 사이 링크들의 가중치 합이 최소가 되는 경로
     - 경로 길이(Path Length)  :  경로 상에 있는 각각의 링크들이 갖는 가중치들의 합
        . 가중치 기준 例 : 거리,시간,비용 등 
     - 최단 경로(Shortest Path)  :  모든 가능한 경로 중 최소 경로 길이를 갖는 경로


2. 최단 경로를 찾는 문제

  ㅇ 다양한 경로들 중에 가장 빠른 경로를 찾는 문제

  ㅇ 최단 경로 문제의 종류
     - 단일 출발지,목적지 최단 경로 문제 (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. 다익스트라 알고리즘 (Dijkstra Algorithm)

  ㅇ Dijkstra가 1956년에 개발하고, 1959년에 발표한 최단 경로 계산 알고리즘
     - Edsger W. Dijkstra (1930~2002) : 네덜란드 과학자

  ㅇ 첫 출발 정점을 기준으로, 연결된 정점들을 추가해가며, 최단 거리를 갱신해 가는 것

  ㅇ 시작 정점에서 모든 다른 정점까지의 최단 경로는, 신장 트리를 형성하게 됨

  ㅇ 음의 가중치를 허용 않는 일반적인 경우

  ㅇ 입력,출력
     - 입력 : 그래프, 시작 노드
     - 출력 : 두 배열
        . 최단 경로 상에 있는 첫 노드
        . 최단 경로의 길이

  ㅇ ... (작성중) ...


4. 벨만 포드 알고리즘

  ㅇ 음의 가중치도 허용하는 경우

  ㅇ ... (작성중) ...


[그래프 알고리즘] 1. 그래프 알고리즘 2. 그래프 순회 (DFS,BFS) 3. 최단 경로 4. 최소비용 신장트리

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