Floyd-Washall Algorithm
플로이드 워셜 알고리즘
플로이드 워셜 알고리즘은 다익스트라 알고리즘과 같이 최단 거리를 찾는 알고리즘입니다.
다만 다익스트라와 다른 점이 있다면, 다익스트라는 한 점에서 모든 점으로 가는 가장 짧은 거리를 찾지만
플로이드 워셜 알고리즘은 모든 점에서 다른 모든 점으로 가는 가장 짧은 거리를 찾습니다.
때문에 최단거리를 저장하는 레코드(배열)도 2차원으로 선언을 하죠.
다익스트라때 예제를 그대로 가져와서 사용해 보겠습니다. 플로이드 알고리즘은
각 노드에서 이동 가능한 점들만을 고려해 shortest path를 만들어 나갑니다.
이때, 플로이드 알고리즘은 차근차근 모든 경우의 수를 고려하기 때문에 A부터 E 순서로 경유하는 지점을 달리합니다.
위에서는 DA로 A 지점을 경유하는 것부터 갱신을 해보죠.
간단한 예시로 B에서 C로 가는 루트를 갱신해 보겠습니다.
우선 B에서 C로 바로 가는 루트는 없습니다. 때문에 다른 노드를 경유해서 이동을 해야 하는데요.
이때, A를 경유해서 이동하면 BA+AC가 최소 거리가 될 수 있습니다. ∞보다 4+5=9가 더 작으니
BC의 최소 거리를 9로 갱신해 줍니다. 위와 같은 방식으로 첫 번째 경유 노드를 고려하여 계산을 해보면,
이렇게 갱신이 됩니다. 아직 갱신이 되지 못한 곳들도 많이 있네요.
근데 자세히 보시면 가운데 0이 있는 라인을 기준으로 위와 아래가 똑같습니다.
만약에 이렇게 진출 path와 진입 path의 거리가 똑같은 경우에는 어느 한쪽만
위와 아래의 값이 똑같으므로, 한쪽만 갱신해도 됩니다. 다만 두 path의 거리가 다른 경우에는
모두 고려를 해야겠지요.
다음은 DB 즉, B를 경유할 때를 고려해 갱신을 해보겠습니다.
이번엔 AE와 EA가 갱신이 되는군요, 중요한 점은 B를 경유한다고 해서
A를 경유하는 점을 고려하지 않는 것이 아닙니다.
ABCDE로 점점 경유하는 점을 많이 고려할수록 모든 경우의 수를 고려하는 것이죠.
예를 들면 A를 경유할 때는 BAC만 고려했지만, B도 고려할 때는 CABE도 고려하는 것이죠.
다음은 앞에 경유를 생각하면서 C를 경유하는 path를 갱신한 것입니다. AD는 원래 지나갈 수 없는
노드였으나, 현재 C를 거쳐가면서 AC+CD가 되어 10으로 갱신되었죠.
또한 DB를 보시면 14로 갱신되었는데요. D에서 바로 B로 가는 방법은 없지만, 앞에서 CB를 CAB로 갱신했었습니다.
때문에 D에서 C를 경유하기만 해도 DCAB라는 함축적인 path가 나오게 되는 거죠. 이를 토대로 계산을 해보면
DB = DC+(CA+AB)= 14가 됩니다.
(D를 경유하는 path에서는 변화가 없어 건너뛰고 E를 경유하는 path로 넘어가겠습니다.)
마지막에는 많은 갱신이 있는데요. 그중에 주목할 것은 A에서 D로 가는 path입니다.
왜 주목을 해야 하냐면 AD는 원래 E를 거쳐가므로 AE+ED=9인 것 같지만,
앞에서 A에서 E로 가는 제일 짧은 path를 AB+BE=6으로 갱신을 했기 때문에
AB+BE+ED = 8로 갱신을 해야 하기 때문이죠.
플로이드 알고리즘은 모든 경우의 수를 고려해서 항상 최적의 값을 도출하는 최적화 알고리즘입니다.
항상 최적의 값을 띄는 만큼 오랜 시간이 걸리는 알고리즘인데요.
시간 복잡도가 O(n3)입니다. 꽤나 느린 편이죠.
#include <stdio.h>
#define length 5
#define max 100
int arr[5][5]={
{ 0, 4, 5, max, 7},
{ 4, 0, max, max, 2},
{ 5, max, 0, 5, 3},
{max, max, 5, 0, 2},
{ 7, 2, 3, 2, 0}
};
int main()
{
for(int k=0; k<length; k++)
{
for(int i=0; i<length; i++)
{
for(int j=0; j<length; j++)
{
if(arr[i][k]+arr[k][j]<arr[i][j])
arr[i][j]=arr[i][k]+arr[k][j];
}
}
}
for(int i=0; i<length; i++){
for(int j=0; j<length; j++){
printf("%3d,", arr[i][j]);
}
printf("\n");
}
return 0;
}다만 코드는 상당히 간단한 편이라, 다익스트라를 n 번 더 실행시켜 최적값을 얻는 것보다 빠르고 간편합니다.
다익스트라를 n 번 실행시키는 것보다 빠른 이유는, 전에 구했던 값을 참고해 다음 최적해를 만들어내기 때문입니다.
마무리
오늘은 플로이드 워셜 알고리즘에 대해서 알아봤습니다.
동적계획 알고리즘을 배울 때 반드시 등장하는 알고리즘입니다.
당장 수행을 할 때는 복잡해 보이지 않지만 동적계획 알고리즘들은
항상 함축적인 순서를 가지고 있어서 실제로 설명을 하고 싶으시면
이 함축적 순서를 이해하셔야 다른 사람에게 이 내용을 알려줄 수 있습니다.
오늘도 감사하고 좋은 하루 보내십쇼.