[Algorithm] Dynamic Programming(5) - 플로이드 와샬 (Floyd-Warshall)

🤔Dynamic Programming

다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다.

 

다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다.

 

이번 포스팅에서는 All-pairs shortest Paths에 대해 알아보도록 하겠습니다.

 

가장 대표적인 알고리즘인 플로이드 와샬 알고리즘을 통해 해당 알고리즘을 해결하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 All-pairs Shortest Path

이전의 다익스트라 알고리즘 또는 벨만포드 알고리즘의 경우에는 하나의 시작 정점 source에서 다른 모든 정점 들 간에 최소 경로를 구하는 알고리즘입니다.

 

이와 같은 문제를 single-source 최단 경로 문제라고 합니다.

 

그에 반해 단일 source가 아닌 임의의 모든 두 정점 u, v에 대해 u에서 v로의 최단경로를 구하는 문제를 All-pairs 최단 경로 문제라고 합니다.

 

 

 

 

 

 

 

✍️벨만포드 알고리즘을 이용한 All-pairs shortest path문제 해결 

Directed Graph G = (V, E)가 negative cycle이 없는 경우, G에서 All-pairs shortest path 문제를 해결하는 방법은 다음과 같습니다.(이때 G가 undirected graph인 경우에는 벨만포드 알고리즘과 같은 방법으로 directed graph로 변환하면 됩니다.)

 

 

 

"G의 각 정점을 source로 둔 다음, 해당 source에 대해 벨만포드 알고리즘을 수행합니다."

 

 

 

위 알고리즘의 시간복잡도는 $O(n x nm) = O(n^2m)$이 됩니다.

 

위의 알고리즘보다 더 빠른 알고리즘을 이용하여 해당 문제를 해결하는 방법을 찾기 위해 플로이드 와샬 알고리즘이 개발되었습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)

Dynamic programming 방법을 이용하여 해당 문제를 해결해보겠습니다.

 

  

 

 

 

 

✍️Recurrence relation 정의

V = { 1, 2, ..., n }으로 두고, G의 임의의 두 정점 i, j에 대해 dist(i, j, k)를 정점 {1, 2, ..., k}만을 path의 중간 거점 정점 (intermediate vetex)로 포함시킬 수 있을 때, i에서 j의 shortest path의 길이라 하자.

 

위의 intermediat vertex는 아래와 같이 이해하면 됩니다.

 

 

 

 

즉, dist(i, j, k)라는 것은 정점 i 에서 정점 j 까지 도달하기 위해 intermediate vetex만을 사용하여 도달한다는 것입니다.

 

 

 

base case) k = 0인 경우 

dist(i, j, 0) = 0 ( i = j 인 경우 )

dist(i, j, 0) = w(i, j) ( edge(i, j)가 존재하는 경우 )

dist(i, j, 0) = 무한대 ( edge(i, j)가 존재하지 않는 경우 )

 

 

 

Inductive step) dist(i, j, k)의 길이를 가진 path를 가진 두 case로 나누어 보자

case1) 정점 k를 지나치지 않는 경우 ( 즉, 정점 k를 중간 기점으로 사용 가능하더라도 정점 {1, ..., k-1}을 중간 기점으로 사용할 때와 비교해서 최단 경로의 길이가 줄어들 지 않을 때를 말합니다.)

dist(i, j, k) = dist(i, j, k-1)

 

 

 

case2) 정점 k를 지나가는 경우 (즉, 정점k를 중간 기점으로 사용했을 때 최단 경로의 길이가 줄어들었을 때를 말합니다.)

dist(i, j, k) = dist(i, k, k-1) + dist(k, j, k-1)

 

 

이를 그림을 통해 이해를 하면 아래와 같습니다.

 

 

 

주의할 점은 그래프 G는 negative cycle을 포함하지 않기 때문에 정점 i에서 k까지의 path와 정점 k에서 j까지의 path상에 존재하는 정점은 공유되지 않는다는 것입니다.

 

만약 해당 정점이 공유된다고 한다면 최단 경로는 공유하는 정점을 지나쳐 i에서 j로 지나치는 path가 형성될 것이기 때문에 k를 중간 기점으로 사용한다고 한 가정에 모순이 됩니다.

 

 

 

최종) case1과 case2를 비교하여 더 작은 경우를 dist(i, j k)로 설정

dist(i, j, k) = min( dist(i, k, k-1) + dist(k, j, k-1),   dist(i, j, k-1))

 

최종적으로 정점 i에서 j까지의 shortest path의 길이는 dist(i, j, n)이 됩니다.

 

 

 

 

 

 

 

✍️ Floyd-Warshall Algorithm outline

1. 알고리즘은 총 0 ~ n의 stage(iteration)으로 구성되며, k 번째 stage가 끝날 때마다 G의 모든 정점 i, j에 대해 dist(i, j, k)가 dist(i, j)에 저장됩니다. (invariant)

2. 0번째 stage에서는 앞선 base case에 맞게 dist값을 정해줍니다.

3. 이후 k번째 stage마다 모든 정점 i,j 에 대해 다음 작업을 반복합니다.

→ dist(i, k, k-1) + dist(k, j, k-1) < dist(i, j, k-1)인 경우 dist(i, j)를 dist(i, k, k-1) + dist(k, j, k-1)로 업데이트 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Floyd-Warshall Algorithm Example

예제를 통해 알고리즘의 해결 흐름을 따라가보겠습니다.

 

 

 

 

 

 

 

 

✍️ 수도코드

이를 수도코드로 나타내면 아래와 같습니다.

 

 

 

 

 

 

 

 

✍️Time Complexity

각 stage마다 모든 1 ≤ i, j ≤ n에 대해서 dist(i, j)를 업데이트합니다.

 

stage가 총 n+1번 존재하므로 해당 알고리즘의 시간복잡도는 아래와 같습니다.

 

$$O(n^2 * (n+1)) = O(n^3)$$