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

 

일단 Longest Increasing Subsequence 랑 RNA Secondary Structure 복습을 하고

 

DP 방식으로 shortest path problem을 풀어본다. 

 

Disjktra’s Algorithm 에서 전 단계의 node + weight를 더했을떄 더 작은걸 고르는 느낌이다. 

 

 

하지만 이런 계산을 할 경우 음수 weight 가 있다면 계속 값이 줄어드리 오류가 생길수도 있다. 

 

그걸 증명한다. 그걸 앞서

 

Cycle 이 생기지 않으려면 Vertex - 1 개수의 edge 로 이루어진 shortest path가 생긴다. 

 

위의 식을 보면 전 단계까지 돌린 distance 이든지 전 단계에서 + weight를 추가해서 최소를 가져가면 된다. 

 

V-1 까지 다 돌리고 나서 G가 cycle이 아니면 멈추면 된다. 

 

G가 Negative CYcle을 가지는지 확인해보려면 V번 돌릴떄랑 V-1번 돌릴때랑 distance 의 값이 똑같은지 확인해보면 된다. 

 

 

Bell-Man Ford Algorithm 처럼 O(|V||E|) 만큼이 걸린다. 

여기서 하나의 row 만 쓸수가 있다. 이 과정은 relax 를 거친다. 즉 값을 업데이트 한 값을 저장하는 배열이다