1. 최단 경로 알고리즘 (Shortest Path Algorithm)
ㅇ 그래프 이론에서, 최단 경로를 찾는 그래프 알고리즘들을 총칭
- 특히, 그래프가 방향성이고, 가중치를 갖으며, 순환을 포함하는 경우
ㅇ 여기서는, 단일 출발지 최단경로 문제 (single source shortest paths problem)에 국한 함
- 단일 출발지로부터, 임의 다른 모든 정점까지, 모든 최단 경로를 찾는 탐색 알고리즘
. 하나의 출발 정점에서 임의 다른 모든 정점에 대한 최단 경로를 찾는 문제
. 결국, 총 n개 정점에서, 시작 정점으로부터 (n-1)개의 최단 경로를 구하는 문제
- 단일쌍 최단 경로 (single pair shortest path) 문제 라고도 함
ㅇ 例) 다익스트라 알고리즘, 벨만 포드 알고리즘 등
- 단일 출발지 최단 경로 계산 알고리즘
. 단일 출발 정점에서 출발하여, 나머지 모든 정점까지의 최단 경로를 찾아냄
2. 다익스트라 알고리즘 (Dijkstra Algorithm)
ㅇ Dijkstra가 1956년에 개발하고, 1959년에 발표
- Edsger W. Dijkstra (1930~2002) : 네덜란드 과학자
ㅇ 그래프 상의 특징
- 간선에서 음의 가중치를 허용 않음
- 순환 포함 허용
- 기본적으로, 탐욕 알고리즘에 속함
. 매번 가장 비용이 적은 노드를 선택하려고 함
ㅇ 방식 상의 특징
- 첫 출발 정점을 기준으로 함
- 연이어, 연결된 정점들을 추가해가며, 최단 거리를 갱신해 감
- 항상, 각 노드에 대해, 현재까지의 최단 거리 정보를 최단 경로 테이블(1차원 리스트)에 저장,
- 이 최단 경로 테이블을 계속 갱신해 나감
- 결국, 시작 정점에서 모든 다른 정점까지의 최단 경로들은, 신장 트리를 형성하게 됨
ㅇ 입력, 출력
- 입력 : 그래프 (노드 개수, 간선 개수 등), 시작 노드
- 출력 : 통상, 출력은, 편의상, 각 노드별 최단 경로 길이가 담겨진 테이블 1개 정도 만 요구함
. 최단 경로 길이 테이블
.. (각 노드별로, 시작 노드에서 해당 노드까지, 최단 경로 상의 가중치들의 합)
. 추가적으로, 각 노드까지 최단 경로를 열거할 수 있는 힌트 등
.. 최단 경로 상에 있는, 출발 직후 노드 (선행 정점) 또는 도착 직전 노드 (후행 정점) 등
ㅇ 상태 자료구조
- 노드 집합
. 최단 경로를 찾은 노드 집합 (점점 커짐)
- 최단 경로 길이 배열
. 각 노드별로, 노드 집합에 있는 정점 만 거쳐,
. 현재까지의 최단 경로 길이(최단 거리)를 갱신 저장해 두기 위함
ㅇ 알고리즘 단계 : (단순한 방법 : 1956년 당시 Dijkstra가 제안한 방법)
* (초기화 단계)
- ① `최단 경로 길이 배열(테이블)`을 초기화함
. 최단 경로 길이 배열(테이블)
.. 각 노드별로, 현재까지의 최단 경로 길이(최단 거리)를 갱신 저장해 두기 위함
. 초기화
.. 시작 정점의 경로 길이 가중치는, 영(0) 적용
.. 나머지 모든 다른 정점의 경로 길이 가중치 값은, 무한대(∞) 적용
.. 무한대 적용은, 도달 못할 정점도 있기 때문
- ② 순환 방지를 위해, `이미 방문한 정점들의 집합`을 만듬
. 초기화 : 처음에는 공집합 으로 함 (개별 원소들을 False 또는 Null 적용)
* (반복 단계)
- ③ 미 방문 정점들 중 최단 거리 정점을 선택 (선형 탐색 필요)
. 매 반복 단계 마다, 현재 정점에 대한, 최단 거리가 확정됨
- ④ 현재 정점와 연결된(인접한) 미 방문 정점들을 확인
. 현재 정점을 경유하는 거리와 기존 저장된 거리를 비교하여, 더 짧은 거리이면 업데이트
ㅇ 알고리즘 단계 : (개선된 방법)
- ① 최단 경로 길이 배열(테이블)을 초기화함
. 위와 상동
- ② 순환 방지를 위해, 이미 방문한 정점들의 집합을 만듬
- ③ 정점 방문 큐(by 우선순위 큐)를 만들어 감
. 우선 그곳에 시작 정점을 넣어 둠
. 우선순위 큐를 사용함
. 현 정점에서 시작 정점까지 경로 길이가 짧을수록, 높은 우선순위를 줌
- ④ 현재 정점으로부터 미 방문 정점들 모두를 방문
- ⑤ 방문 정점은 방문했음으로 방문했을 알리는 마크 표시
- ⑥ 정점 방문 큐가 빌 때까지 단계 ④부터 되풀이
ㅇ 시간복잡도
- 단순한 방법 : O(V2)
. 모든 정점들을, 매번 최단거리를 선형 탐색 해야 하고,
. 현재 정점과 연결된 점정들을, 매번 일일이 확인해야 함
- 개선된 방법 : O(E log V)
. 여기서, V : 노드 갯수, E : 간선 갯수
ㅇ ... (작성중) ...
3. 벨만 포드 알고리즘 (Bellman-Ford Algorithm)
ㅇ 1958년 Richard Bellman,1962년 Lester Ford가 제안한 알고리즘을 기반으로 함
ㅇ 그래프 상의 특징
- 음의 가중치도 허용하는 경우
- 순환 포함 허용
ㅇ 방식 상의 특징
- 간선 가중치가 음수도 처리 가능
- 결과를 이용하여 음수 가중치 순환을 찾아낼 수 있음
ㅇ 시간복잡도 : O(nm)
- (n : 정점수, m : 간선수)
ㅇ ... (작성중) ...