DP - Floyd Algorithm : APSP

Floyd Algorithm - Part 1.

All Pair Shortest Path(APSP) Problem
=> 한 노드에서 다른 모든 노드까지 가는 최단거리의 모든 조합을 다 구하는거
Floyd-Warshal algorithm (DP)

 

APSP def.
Problem : Given any pair (u,v) find a SP from u to v.
Model : on graph.
Solution Algo: Design -> Analysis -> Best algorithm?

1) Brute-force, enumeration: O(n!)
2) Divide and Conq(나눈 subproblem 간의 독립이 아닌 간섭이 있을 수 있음): think?!
3) Dynamic prog: O(n^3)
-> S0 : example (easy small subproblems)
-> S1: recurrence eqn.

What is the easiest (sub)problem?
: a direct path from u to v.
: save 2D matrix(array)

D0 -> D1 -> D2 -> .. -> D(n-2) (u,v를 제외한 모든 노드를 경유할 때까지, n=>vertax 수, 괄호 => 중간 경유 노드 개수)
: D[i,j] = D[u,v] = SP from i to j, u to v.

 

D0 : input graph info.(given)
D0[2,5] = direct path from 2 to 5 = inf.
D1[2,5] = min(2-1-5, 2-3-5, 2-4-5)  => 2와 5를 제외한 노드 중, 하나를 거쳐간 경유 중 최솟값
= min(  D0[2,1]+D0[1,5] = 14
            D0[2,3]+D0[3,5] = inf
            D0[2,4]+D0[4,5] = 5)

D2[2,5] = min {   =====> wrong!! 1) too many enumeration  ==> brute-force로 간다(더이상 DP가 x)
2-1-3-5, ==>> D0[2,1]+D0[1,3]+D0[3,5] XX (D1을 활용 x  ==> dp의 design과 맞지 않음)
             ==>> D1[2,3] + D0[3,5] XX (이건 2-1-3-5 경유가 아님,  D1[2,3] => min이 1을 경유한다는 보장x)  
             ==>> 결론적으로 이런 전개로는 DP recurrence를 도출해낼 수 없음
2-3-1-5,
2-4-1-5,
2-1-4-5,
2-4-3-5,
2-3-4-5
}  ==> We need another examples!!! another approach!

 

 

Floyd Algorithm: Part 2.

Key:
- D1[i,j] = i에서 j까지 가는데, 1번 도시를 경유할 수 있다.(직접갈 수도 있고 OR 경유 할수도 있음)

  ==> i에서 j까지 가는데, 직접 가거나 or 경유하거나 두 경우 중 최솟값 저장 
- D2[i,j] = i >> j : 직접 OR 1번 도시 OR 2번 도시 경유 (직접 or 1번의 최솟값은 위에서 계산함 ==> 활용가능)

 

D1[5,4]  = min(A, B) ==> 5에서 4까지 직접가거나 or v1을 경유 하거나 두가지 비교
             = min(D0[5,4], D0[5,1]+D0[1,4])
             = min (inf, 3+1) = 4.
....

D2[5,4] = min(   A = D1[5,4]  ,  B = D1[5,2]=4  +  D1[2,4]=2   )

(D0 아닌 이유: 5 >> 4가는데 직접 vs 1번노드 경유

이미 D1이 해서 짧은게 저장되어 있음. 더 짧은 D1이랑 D2를 비교해야 최소를 찾을 수 있다.)

           = min(A = 4, B = 6)

...

D3[5,4] = min(D2[5,4] , D2[5,3]+D2[3,4])

 

 

 

Recurrence Equation

Dk[i,j] = min(k를 거치지 않는 경우, k를 경유하는 경우)

Dk[i,j] = min(D(k-1)[i,j] , D(k-1)[i,k] + D(k-1)[k,j])

k : 경유지

 

이해가 팍 안돼서 그림 그림

D2에서 5 >> 2 >> 4 인 경우만 생각 했더니 이게 왜 최소인지 납득이 안갔음..

5 >> 2도 5 >>2일지 5>>1>>2 일지 이미 계산 되어있는거였음... 

Floyd Algorithm: Part 3

Floyd Recurrence:
D(k)[i,j] = min( D(k-1)[i,j] , D(k-1)[i,k]+D(k-1)[k,j] )

procedure Floyd(input graph D)
for-loop k = 1 -> ...
for-loop i
for-loop j
D(k)[i,j] = min( D(k-1)[i,j] , D(k-1)[i,k]+D(k-1)[k,j] )



Question: We need a single D array for the entire calculation
D0 -> D1 -> D2 ... ==> XXX
==> Q: Why D matrix(single) is enough instead of D0, D1, D2, D3, ...?
--> Textbook. (최적화 가능 하다는 뜻...)

 

=> 그냥 단순하게 생각해봐도, k for문 돌아가면서 array D에 지금 단계(k)에서의 최소값이 저장되었기 때문에, 굳이 array 새로 만들 필요 없이, k+1단계에서의 최솟값은 이미 앞서 저장된 D[i,j] 와 새로 돌아가는 k+1번째 노드를 거치는 경우만 비교해주고, 다시 D[i,j]에 새로운 최솟값을 덮어쓰면 된다.

Time complexity : O(n^3), n =|V|

Question: shortest path 계산 X, shortest distance O
--> How to find(print) shortest paths between i->j
--> Save the "k" vertex. 교과서 참고..

=> Dk[i,j] = min(D(k-1)[i,j] , D(k-1)[i,k] + D(k-1)[k,j]) 계산 시, 

전자가 선택되었는지, 후자가 선택되었는지 if문을 통해 검사 

=> 만약 후자가 선택되었다면, k 값을 다시 저장해서 출력 

=> 어케함...?

 

Q. CMM: print the optimal multiplication.

=> 여기서도 matrix 합의 최솟값만 계산한 것이지, 실제로 어디에 괄호를 쳐야 최소가 되는지는 출력 x

==> 어떻게 아냐? matrix의 k값을 이용하자.

DP: Principle of Optimality == Optimal substructure

"All subsolutions of an optimal solution are _optimal_."
"Optimal subsolutions can build up a global(final) optimal solution."
If a problem A satisfies "principle of optimality(opt. sub)"
-----> then DP provides the best design(optimal results).
---> (not saying DP is the most effcient design)

 

APSP: D[2,5] = D[2,1] + D[1,5]

Example: Longest simple path problem :  1-- 3 -- 2 -->4
--> optimal substructure X (principle of optimality 만족 x) -> 1-2-3: LSP

 

 

Week 6.4 MIT Dynamic Programming
MIT 6.006 Lec 19~22
19=> 반드시 들어라
20=> text justfi 추천, 5 easy steps by prof erick e.
21 => 모두 반드시 추천, Edit Distance : general problem
=> 교과서 3.7 sequence alignment