MIT - Introduction to Algorithms
- Lecture 16. Dijkstra 다익스트라 Review
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/
Review
d[v] : Source S에서 V까지 현재 가장 짧은 길의 길이
$\delta(s,v)$ : 유일하지 않을 수 있으나 하나의 짧은 길의 길이
$\Pi(v)$ : S에서 V의 짧은 길의 전 선행자 predecessor
s에서 나가는 간선들 edges에 대해 완화 Relaxation operation
$d[A]=1, d[B]=3$
B로 가는 길이 2가지(S->B=3 or S->A->B=2)
$d[A]=1, d[B]=2$ => $\delta$에 수렴하므로 종료 terminate
왜 완화 과정 Relaxation Operation이 유용하고 안전하며 정확한지 알아봄
위의 예시를 통해 기본 완화 연산에 대해 떠올리면 d[A]에서 무한대롤 1로, d[B]에서 3을 2로 갱신하는 작업을 수행함
이 때 d[v]의 값만 변형하는 것이 아닌 선행자 $\Pi[v]$ 역시 또한 변형 시켜주는 이 과정을 완화 단계 Relaxation Operation이라고 칭함
Relaxation Safe : 특정 간선에 대해 완화 했는데 잘못된 결과로 $\delta(s,v)$보다 작은 값을 얻어내는 가능성을 확인해야하지만 할 필요가 없음
만약 $\delta(s,v)$보다 작은 값을 얻었다면 다시 올라가는 법을 생각해야함(이것은 우리가 원하는 알고리즘 종류가 아님)
Lemma(보조 정리) : 다른 정리를 증명하는 데 쓸 목적으로 증명된 명제.
Lemma : $d[v] \ge \delta(s,v)$ for all $v \in V$
=> 최단 경로 길이보다 짧은 것이 나오지 않는다는 증명
Triangle Inequality와 귀납적 정의로 증명 가능
위 방향 그래프 S,A,B에서 보듯이
$(\delta[S,B]=2) \le (\delta[S,A]=1) + (\delta[A,B]=1)$
음의 값을 가져도 상관 없음
위상 정렬 Topological Sort
O(V+E) time Complexity
Figure 1
시작점을 z에 둔다면 더 나아갈 Edge가 없기 때문에 시작점 왼쪽 Vertexes들까지의 거리는 다 무한대가 될 것이다.
s를 시작점으로 둔다면 왼쪽의 r은 당연히 무한대의 거리가 될 것이다.(s에서 r로 갈 수 없으므로)
물론 처음에는 오른쪽의 Vertex들 또한 무한대일 것이다. 그러나 Relaxation을 통해 완화될 것
다이나믹 프로그래밍의 간단한 예제
다익스트라 알고리즘은 이 경우를 포함하지 않음
상당히 직관적인 알고리즘 : 탐욕 알고리즘 Greedy Algorithms이기 때문
다익스트라 의사 코드 Dijkstra Pseudo Code
대문자 S는 집합 : 공집합
d[s]=0 나머지 distance는 무한대로 초기값
Q는 우선순위 큐 Prior Queue
Q = {0 7(=3+4) 3 11(=3+8) 5(=3+2)}
Relaxation Safe Lemma를 통해 우리는 S={A,C}는 최단이라는 것을 확인할 수 있다.
이진 최소 힙을 사용하면 Extract-min을 살펴보면 최소를 찾는 것은 상수 시간
최적의 알고리즘은 우리가 배우지 않는 Fibonacci Heap을 이용한 방식
