1. 최단 경로 (Shortest Path)
ㅇ 그래프 이론에서, 출발지와 목적지 사이 링크들의 가중치 합이 최소가 되는 경로
- 특히, 그래프가 방향성이고, 가중치를 갖으며, 순환을 포함하는 경우
※ [참고]
- 경로 (Path) : 어떤 정점에서 시작하여 특정 정점으로 끝나는 순회/방문/여정
- 경로 표현 : 두 정점 사이를 잇는 간선 또는 정점들을 순서대로 나열하게됨 (중간에 비면 안됨)
- 경로 길이 (Path Length) : 경로 상에 있는 각각의 링크 가중치(거리,시간,비용 등)들의 합
- 최단 경로 (Shortest Path) : 모든 가능한 경로 길이 중 최소 경로 길이를 갖는 경로
- 방향 그래프 (Directed Graph) : 정점들 간에 방향성이 있는 그래프 ☞ 그래프 종류 참조
- 가중치 (Weight) : 두 정점 간의 연결선에 수치(비용 등)를 부여한 것 ☞ 라우팅 메트릭 참조
- 순환 경로 (Cyclic Path) : 순환적으로 이어지는 간선 또는 경로 ☞ 루프 순환 참조
2. 최단 경로 문제 및 그 종류 (Shortest Path Problem)
ㅇ 최단 경로 문제 : 다양한 경로들 중에 가장 빠른 경로를 찾는 문제
* [참고] ☞ 그래프 알고리즘 참조
. 그래프 내 모든 정점을 순회하는 방법 : 그래프 순회 (Graph Traversal)
. 작업 사이에 특정 의존(순서)관계가 있을 때 이를 정렬시키는 방법 : 例) 위상 정렬
. 루프가 없는 그래프(신장 트리)를 생성시키는 방법 : 신장 트리 (Spanning Tree)
. 최소 신장 트리를 작성하는 방법 : 최소 신장트리 알고리즘 (MST)
. 그래프 상에서 최단 경로를 탐색하는 방법 : 최단 경로 알고리즘 (SPF) (*)
ㅇ 최단 경로 문제의 종류
- 단일 출발지,목적지 최단 경로 문제 (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)
ㅇ 그래프 이론에서, 최단 경로를 찾는 그래프 알고리즘들을 총칭
- 주로, 단일 출발지로부터 모든 정점까지의 최단 경로를 찾는 탐색 알고리즘