6-2강 - Dynamic Programming 2 (최단거리 유형, 플로이드 알고리즘 )

2. All Pairs Shortest Paths

0) 최단 경로 문제 유형

1> Shortest path finding problem 

u와 v간의 최단 경로 찾기 

2> Single source all destination shortest path problem

하나의 출발점(single source)에서 각 정점(all destination)까지 도달하는데 (필요한 비용을 계산하여) 최단 경로들을 구합니다.

3> All pairs shortest paths problem

모든 점들간의 거리 중 최단거리(경로)를 구하는 문제

 

cf> 최단 경로 문제의 공통적인 solution

step 1 : shortest path의 distance(cost)를 구하기step 2 : 그 distance(cost)를 가지는 path를 다시 구하기 (backtracing)(step 1과 step 2를 동시에 할 수 없습니다.)

 

 

1) Single source all destination shortest path problem

1> Dijkstra's algorithm (나중에 greedy에서 다룹니다.)

2> Bellman-Ford algorithm (DP이기는 하지만 까다로워서 나중에 다룹니다.)

 

cf> Minimum cost spanning tree (MST) vs Shortest path spanning tree (SPT)

0> spanning tree : 그래프 내의 모든 정점을 포함하는 그래프

1> Minimum cost spanning tree : 말 그대로 cost가 최소인 spanning tree

2> Shortest path spanning tree : spanning tree인데 최단 경로로 각 vertex에 도달하여 만든 spanning tree

 

2) All pairs shortest paths problem (Floyd's algorithm)

Single source all destination shortest path problem에 대한 algorithm을 n번 시행하면 되는데 복잡합니다.

그래서 Floyd's algorithm을 사용합니다.

(다익스트라가 적은 비용을 선택해야 했다면, Floyd는 '거쳐가는 정점'을 기준으로 알고리즘을 시행합니다.)

 

cf>  Floyd's algorithm 특징

• Dynamic Programming
• negative cost가 있어도 사용 가능
• directed와 undirected 모두 가능
• negative cycle에서는 사용 불가 (음수 가중치로 cycle을 이루는 경우)

0> 정의할 것

[1] W(i, j) (edge cost)

• edge가 없으면, W(i, j) = ∞
• edge가 있으면, W(i, j) = cost
• i = j이면, W(i, j) = 0

 

[2] D^k (i, j)

i부터 j까지 index가 k미만인 vertex만 거친 최단 경로 

• D0 (i, j) = W(i, j)
• i에서 j까지 최단 경로에 k를 지나지 않아도 shortest path인 경우 D^k (i, j) = D^k-1 (i, j)
• i에서 j까지 최단 경로에 k를 지나야 shortest path인 경우 D^k (i, j) = D^k-1(i, k) + D^k-1 (k, j)

1> recursive form

[1] 초항 D⁰ (i, j) = W(i, j)

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

 

<알고리즘 1>

2> bottom-up (k를 증가시키면서 bottom-up)

[1] k = 0 (그냥 edge cost W(i, j) )

[2] k = 1 

경유가 허용되는데 1만 허용됩니다.

즉, i와 j 사이의 cost vs i에서 j까지 지날 때 1을 경유하는 경우

[3] k = 2

경유가 1과 2만 허용됩니다.

[4] k = 3

경유가 1, 2, 3만 허용됩니다.

3까지 거쳐서 갱신될 수 있는 minimum cost path가 없습니다.

[5] k = 4

경유가 4까지 모두 허용됩니다.

여기까지 bottom-up을 하면 모든 minimum cost path를 다 구합니다.

3> top-down - backtracing (Finding Actual Shortest Path)

[0] bottom-up 과정에서 흔적(memo)을 남겨둡니다.

P[i][j] : i에서 j로 갈 때, 지난 vertex 중 가장 큰 index를 남깁니다.

[1] 경로를 기록할 array 준비 (sPath)

sPath[1]~sPath[nP]까지 각 vertex를 저장합니다. 

 

[2] p[i][j]를 이용해서 recursive하게 path 계산 (분할 정복 사용)

i부터 p[i][j]까지의 path를 구하고

p[i][j]부터 j까지의 path를 구합니다.

T(n) = O(n)

 

<알고리즘 2>

ex> 

cf> Transitive Closure 적용

0> Transitive Relation

<알고리즘 3>

1> Transitive closure of graph

i에서 j까지 접근이 가능한지에 대한 graph는

transitive closure가 성립합니다. (D[i][k] 와 D[k][j] 모두 1이면, D[i][j] = 1)