[삼성 알고리즘] 플로이드 와샬(Floyd Warshall) 알고리즘

안녕하세요~!

이번 포스팅은 플로이드 와샬 알고리즘입니다.

플로이드 와샬 알고리즘은 각 노드에서 다른 노드로 이동할 때 걸리는 각각의 최소 경로 비용을 구하는 알고리즘입니다.

 

플로이드 와샬 알고리즘은 2차원 배열을 이용해서 진행합니다.

플로이드 알고리즘은 i 노드에서 출발하여 j 노드로 이동할 때 걸리는 비용의 최솟값은

i와 j중간에 있는 k에 대하여

min(i에서 k까지 이동한거리+k에서 j로 이동한 거리, i에서 j까지의 거리)값과 같음을 이용해서 동작하는 알고리즘입니다.

 

이번 알고리즘 역시 예를 통해서 플로이드 와샬알고리즘 포스팅을 진행하겠습니다.

 

먼저 위와 같은 노드 그래프가 존재할 때 그래프에서 이동할 수 있는 부분의 비용을 기입하고 각 노드에서 한 번에 이동하지 못하는 부분은 infinity로 기입합니다.

 

그 후에는 각 노드에 대해서 1번노드 부터 4번노드까지 반복문을 통해 지나가는 경로를 계산합니다.

예를들어 1번노드를 지나가는 경우에는 2,3,4번 노드에서 출발하여 1번을 거쳐서 이동하는 경로로 비용을 계산해서 기존의 표에들어있는 값과 비교를 통해 최솟값으로 표를 갱신합니다.

 

-> 1번노드를 경유하는 경우

1번노드를 경유하는 경우 2번,4번 노드에서 출발하는 경유에는 1번노드로 이동할 수 없기 때문에 처리하지 않고 3번 노드의 경유에만 1번으로 경유한 뒤 목적지까지의 비용을 계산합니다. 하지만 1번을 경유한 뒤 2번노드 및 4번노드로 가는 경우에는 1번을 경유하지 않을 때보다 비용이 더 들기 때문에 표의 변화가 일어나지 않습니다.

 

-> 2번노드를 경유하는 경우

 

2번노드를 경유하는 경우에는 1,3,4 노드를 모두 출발지로 계산할 수 있습니다. 먼저 1번노드에서 출발하여 2번노드를 경유하는 경우 4번노드까지의 비용이 기존의 무한대 값보다 작기 때문에 10으로 셋팅됩니다.

마찬가지로 3번노드에서 출발 했을 경우 2번을 경유해서 4번으로 가는 경우 직접 가는 경우보다 비용이 적기 때문에 값이 4로 셋팅됩니다.

 

-> 3번노드를 경유하는 경우

1번에서 출발하는 경우 3을 거쳐 2로 갈 때 6의 최소비용을 얻을 수 있습니다.

마찬가지로 4번에서 출발하는 경우 3을 거쳐 1과 2로 갈 수 있고 이 때의 비용을 갱신할 수 있습니다.

 

-> 4번노드를 경유하는 경우

2번노드에서 출발하는 경우 4번을 거쳐 1번노드와 3번노드로 이동이 가능하고 이 때 무한대였던 기존의 값과 비교해서 작기 때문에 최솟값으로 다시 갱신 됩니다.

 

4개의 노드를 경유노드로 결정해서 진행한 결과 각 노드를 시작노드로 했을 때 다른 노드로 이동하기 위한 각각의 최소 경로 비용을 구할 수 있습니다.

 

마지막으로 알고리즘의 효율성에대해서 알아보겠습니다. 해당 알고리즘은 최악의 경우 모든 노드를 방문하기 때문에 O(N^2)의 복잡도를 가지게 되고 이 때, 경유로 하는 노드 역시 N개이므로 O(N^3)이 됩니다.