최단 경로를 찾는 두 가지 대표적인 알고리즘 중에 하나입니다.
다른 하나는 다익스트라 알고리즘이 있는데, 이는 탐욕법에서 알아봅니다.
프로이드의 알고리즘은 모든 점에서 모든 다른 점까지의 거리를 알아냅니다.
최단 경로 문제는 Optimization Problem입니다.
여러 가지 해답의 후보가 있고, 각 후보마다 값이 있고, 우리는 최적의 값을 찾아야 합니다. (여기서는 경로의 최솟값)
최단 경로의 문제에서 한 마디에서 다른 마디로 가는 최단 경로는 하나 이상이 있기 때문에, 여기서는 최단 경로 중 하나를 찾습니다.
1. 알고리즘
시작은 단순무식한 접근법 (Brute-Force)입니다.
한 정점에서 다른 정점으로 가는 모든 경로를 구한 후, 그 경로 중 최솟값을 찾는 방법입니다.
이때 경우의 수는 (n-2)(n-3)...1 = (n-2)! 입니다. 지수 시간보다도 나쁘죠?
이러한 상황은 최적화 문제에서 자주 나타나는데, 실제로 모든 가능성을 따지면 정말로 비효율적입니다.
따라서 우리의 목표는 더 효율적인 알고리즘을 찾는 것입니다.
이때 플로이드의 알고리즘을 사용하면 3차 시간 알고리즘으로 줄일 수 있습니다.
DP를 사용하여, 우리는 최단 경로의 길이만 구하는 알고리즘을 설계할 수 있습니다.
모든 경로를 구한 후 최저값을 찾는 것이 아닌 최단 경로의 길이만 구하는 겁니다.
이때 경로의 길이를 저장하는 배열을 만들어야겠죠?? 인접행렬인 W배열을 만듭시다.
\(W[i][j] = \left\{\begin{matrix}
weight\, on \, edge & if\, there\, is\, an\, edge\, from\, v_1\, to\, v_2 \\
\infty & if\, there\, is\, no\, edge\, from\, v_1\, to\, v_2 \\
0 & \, if\, \, i \, == \, j \\
\end{matrix}\right.\)
입니다.
또한 우리는 최단 경로의 길이를 저장하는 D 배열도 만듭시다.
D(k)[i][j]= 집합(v1, v2, ... , vk)에 속하는 정점만을 거쳐서 vi에서 vj로 가는 최단 경로의 길이입니다.
W를 이용해서 D를 풀면 됩니다.
이렇게 W가 정의되어 있다고 생각해봅시다. D는 일단 지금은 보지 마시고
단순히 일부만 계산해보면,
이런 결과가 나오게 됩니다.
이때 D(0) = W와 같고, D(n) = D과 같습니다.
따라서 저희는 D(0)를 이용하여 D(n)을 구해야 합니다.
이제 DP를 적용하는 절차를 세워봅시다.
- D(k-1)로부터 D(k)를 계산하는 재귀 관계식을 만든다.
- k = 1부터 n까지 과정을 반복하여 문제를 해결한다.
이때 재귀 관계식은 두 가지가 있습니다.
- vi에서 vj로 가는데 vk를 쓰지 않는 경우에는
- D(k)[i][j] = D(k-1)[i][j]입니다.
- 반대로 vk를 쓰는 경우에는
- D(k)[i][j] = D(k-1)[i][k] + D(k-1)[k][j]와 같습니다.
무조건 이 재귀 관계식 두 가지 경우에 해당해야 하므로, D(k-1)로부터 D(k)를 구할 수 있습니다.
따라서 관계식은 아래와 같습니다.
\(D^{k}[i][j] = minimum(D^{k-1}[i][j],\,D^{k-1}[i][k]+D^{k-1}[k][j])\)
이때 D배열은 하나만 써도 상관이 없는데, 이유는 다음과 같습니다.
왜냐하면 k번째 행과 열은 k째 반복을 할 때 변하지 않기 때문입니다.
k째 반복에서
D[i][k] = minimum(D[i][k], D[i][k] + D[k][k])이고,
D[k][j] = minimum(D[k][j], D[k][j] + D[k][k])이므로, 값이 변하지 않습니다.
3. 시간 복잡도
k가 0부터 n까지 들어가면서, 0부터 n번째 행까지 계산하면서, 0부터 n까지의 열을 계산합니다.
따라서 n^3의 시간 복잡도를 가집니다.
감사합니다.
지적 환영합니다.
추가)
만약 i = 1, j = 5이고, k가 3일때, <1, 3, 5>가 최적의 경로라고 칩시다.
근데 알고보니까 <1, 4, 3, 5>가 최적이라고 가정한다면,
k = 4이고, i = 1, j = 3일 때 <1, 4, 3> 이라는 최적의 경로가 생기겠죠?
또한 <1, 3, 4, 5> 가 최적이라고 가정했을 때,
k = 4이고, i = 3, j = 5이면 <3, 4, 5> 라는 최적의 경로가 생깁니다.
그러므로 D[i][j] = min(D[i][j], D[i][k] + D[k][j])에 의문을 안 품으셔도 됩니다.
부분적으로 이미 최적화가 되니까요