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) : 네덜란드 과학자
ㅇ 그래프 상의 특징
- 간선에서 음의 가중치를 허용 않음
- 순환 포함 허용
ㅇ 방식 상의 특징
- 첫 출발 정점을 기준으로, 연결된 정점들을 추가해가며, 최단 거리를 갱신해 감
- 시작 정점에서 모든 다른 정점까지의 최단 경로들은, 신장 트리를 형성하게 됨
ㅇ 입력,출력
- 입력 : 그래프, 시작 노드
- 출력 : 두 배열
. 최단 경로 길이 (각각의 최단 경로 상의 가중치들의 합)
. 최단 경로 상에 있는 출발 직후 노드 또는 도착 직전 노드
ㅇ 알고리즘 단계
- ① 시작 정점의 경로 길이 가중치를 영(0),
나머지 모든 다른 정점의 경로 길이 가중치 값을 무한대(∞) 적용
. 이는 도달 못할 정점도 있기 때문
- ② 순환 방지를 위해, 이미 방문한 정점들의 집합을 만들어 감
- ③ 정점 방문 큐를 만들어둠
. 우선 그곳에 시작 정점을 넣어 둠
. 이는 우선순위 큐를 위함이며, 우선순위는 정점까지의 경로길이고,
. 현 정점에서 시작 정점까지 경로 길이가 짧을수록 높은 우선순위를 줌
- ④ 현재 정점으로부터 미 방문 정점들 모두를 방문
- ⑤ 방문 정점은 방문했음으로 방문했을 알리는 마크 표시
- ⑥ 정점 방문 큐가 빌 때까지 단계 ④부터 되풀이
ㅇ ... (작성중) ...
3. 벨만 포드 알고리즘 (Bellman-Ford Algorithm)
ㅇ 1958년 Richard Bellman,1962년 Lester Ford가 제안한 알고리즘을 기반으로 함
ㅇ 그래프 상의 특징
- 음의 가중치도 허용하는 경우
- 순환 포함 허용
ㅇ 방식 상의 특징
- 간선 가중치가 음수도 처리 가능
- 결과를 이용하여 음수 가중치 순환을 찾아낼 수 있음
ㅇ 시간복잡도 : O(nm)
- (n : 정점수, m : 간선수)
ㅇ ... (작성중) ...