알고리즘 시험 준비 - [8/13 Files] - 2019-09-23

 

Bellman Ford 는 V-1 까지 Update을 하고 한번 떠 돌려서 값이 다른지 안다른지 해서 Negative Cycle 을 판별한다. 

이 과정은 각각의 제일 짧은 거리 즉 어느 node 에서 어느 node로 가는게 젤 빠른지 알려주는 식이다.

 

best array를 사용하는 예시를 보여준다

 

BF Algorithm 의 특징 

 

어떤 v에서 거리가 무한대보다 작으면, s -> v 가는 path 가 dist(v) 랑 같아질수있다. 당연한거 아닌가…

 

Induction으로 증명을 해보자 한다. 

 

Bellman Ford 답게 iteration 이후 -> dist(u) >= distance(s,u) 가 있을 것이다. 

 

dist(v,k) >= dist(u)

 

u 는 전 단계이다. 

어쩃든 |v| - 1 iteration 이후 dist(v) = distance (s,v) 이다.

 

계속 싸이클 얘기다 

 

 

이것만 기억하면 될꺼같다. 

 

weight 값의 합이 음수일때

 

반대로 전단계 + 현재 weight 가  현재단계보다 크다고 할 경우 다 더하면 그것도 contradiction이라서 (양수가 된다..) False이다. 

 

Forest 는 Cycle이 아닌 Tree 라고 생각하면 될듯 

 

last edge를 더하면 음수 사이클이 생길수가 있다는 걸 말해준다. 

 

 

원래는 부등호가 미만인데 미만에서 이하로 바꿔서 음수 사이클이 생길수 있다는 걸 말하는거같다. 

 

좀 헷갈리네 

 

DP랑 BP

 

DP가 일단 크다고 생각하자.