Shortest Path   최단 경로

(2018-07-06)

최적 경로

1. 최단 경로그래프 이론에서 출발지와 목적지 사이 링크들의 가중치 합이 최소가 되는 경로
     - 경로 길이(Path Length)   : 경로 상에 있는 각각의 링크들이 갖는 가중치들의 합
     - 최단 경로(Shortest Path) : 두 정점 간에 최소 경로 길이를 갖는 경로


2. 최단 경로를 찾는 문제

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

  ㅇ 최단 경로 문제 종류
     - 단일 출발지 최단경로 문제
     - 단일 도착지 최단경로 문제
     - 단일 쌍 최단경로 문제
     - 모든 쌍 최단경로 문제


[그래프] 1. 그래프 2. 그래프 용어 3. 그래프 종류 4. 노드 5. 루프 6. 인접 행렬 7. 최단 경로 8. 최소비용 신장트리

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