MIT - Introduction to Algorithms
- Lecture 17. Bellman-Ford 벨만 포드 Review
Copyright to MIT & Srini Devadas & Erik Demaine
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/
음의 가중치가 있는 Negative Weight Edges들에 대해 그래프의 최단 경로를 찾는 알고리즘으로 음의 순환에 대해서도 정확한 답을 알려준다.
Polynomial Time Algorithm 다항 시간 알고리즘으로 기술이 쉽다.
Recall General Case : 강의 시간 - 1:59
Figure 1을 기반으로 하는 Graph에서 $v_1, v_2$에 Negative Cycle이 존재한다면
$\delta(u,v_1), \delta(u,v_2), \delta(u,v_3) \cdots \delta(u,v)=\infty$들은 undefined
$v_1$조차도 negative cycle의 영향력을 받기 때문에 최단 거리의 가중치는 계속 변함
2가지 문제점이 있었다
1. 양의 가중치를 가지는 상황에서도 Complexity 복잡도가 지수 시간이다.
Figure 3과 같은 그림에서 n nodes에서는 $O(2^{n \over 2})$
2. 음의 가중치를 가지는 순환이 시작점으로부터 도달이 가능하다면 정해진 대로 알고리즘이 종료되지 않을 수 있다.
1의 경우 Dijkstra로 해결
그러나 일반적인 경우의 2번은 어떻게 처리하는지 모름 - 벨만 포드 방법을 통해 해결 - 직관적
말하고자하는 바는 졸업 후 5분이면 모든 강의 내용이 기억이 나지 않는다. - 그러므로 핵심만이라도 기억하게 된다는 의미?
10초 버전으로 설명하면
Polynomial Time 다항 시간 알고리즘이 Best
Exponential Time 지수 시간 알고리즘 Bad
Infinity Time 무한 시간 알고리즘 해고 당함 Fired
Bellman - Ford (G,W,s) : Graph, Weight, Source
처음은 Initialize와 Relaxation Operation을 수행 후
또 Relaxation Operation을 수행하는데 만약 이 과정에서 조건문이 부합한다면 Negative Cycle이 있다는 것을 감지할 수 있다.
i는 단순 카운터, 사용되지 않음
O(VE+E) = O(VE)
다익스트라와 같이 우선순위 큐 구현에 정해진 요구사항이 있지 않음
단순 그래프에서 E는 $O(V^2)$
O(VE) : 다익스트라보다 느림, 다익스트라는 선형 복잡도를 가지지만 벨만 포드는 $O(V^3)$
우리가 증명해야할 2가지
1. Theorem : 강의 시간 - 18:40
2. Corollary 추론 : 강의 시간 - 19:45
이를 위해서 일반적인 최단 경로가 의미하는 바를 생각해야함
Figure 6를 기반으로 $k \le |V|-1$가 보장돼야한다. 아니면 Cycle 순환이 생김
이 정리에서는 음의 순환이 없다고 가정
간선의 수가 가장 적은 경로를 선택
귀납적으로 $k \le |V|-1$ 후에 $d[v_k]=d[v]=\delta(s,v)$라는 사실에 도달
source vertex 1개 + (|V|-1)개 vertexes = V개의 Vertex
source $d[s]=d[v_0]=0$는 초기 설정이므로
당연히 i=1 ~ |V|-1까지 도는 것
참조 : https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/
