플로이드 워셜 알고리즘(Floyd Warshall Algorithm) 개념

플로이드 워셜 알고리즘(Floyd Warshall Algorithm) 이란?

그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용할 수 있다.

그래프 공부 시, 아주 중요한 알고리즘이며, 

이 알고리즘 및 다익스트라 알고리즘(Dijkstra Algorithm) 그리고 

벨만 포드 알고리즘(Bellman-Ford Algorithm) 이 3가지 알고리즘을 통해 최단 경로를 구할 수 있다.

이러한 세가지 알고리즘은 각각 정점과 간선의 개수가 어떻게 구성되냐에 따라 시간 복잡도의 차이가 있기에,

각 상황에 맞는 알고리즘을 이용하면 된다.

이번 게시물에서는 플로이드 워셜에 대해 알아 보도록 한다.

다익스트라, 벨만 포드 알고리즘은 하나의 시작점에 대해 최단 경로를 찾아주지만

플로이드 워셜 알고리즘은 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 다 구해준다.

그렇기에 많은 시간이 소요되지만, 이 알고리즘을 이용해 해결해야 할 상황도 존재하므로, 꼭 알고 있어야 한다.

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘, 플로이드 워셜 알고리즘, 플로이드 워셜 알고리즘 이라고도 알려져 있다. >> 위키트리 - 플로이드 워셜 알고리즘

다음은 플로이드 워셜 알고리즘의 시간 복잡도 분석이다.

플로이드 워셜은 그림을 통해 확인해 보는것이 글보다 더 쉽다.

그림을 보는데 다소 반복적이고, 그림이 3중 포문이기에 많다보니 집중해서 보길 바란다. 흐름을 놓치기 쉽다.

다음과 같이 방향이 존재하는 정점 5개, 간선 20개의 그래프가 주어져있고, 

모든 정점에서 서로 다른 모든 정점으로 가는 최단 거리를 구해보자.

결국 플로이드 워셜을 통해 얻어지는 최단거리는 여기서 5P2 즉, 20개이다.

(결국 이 게시물에서 확인해야 할 이미지는 |V|^3이라면, 125개가 될 것이다..)

점 x에서 0번을 통해 점 y로 가는 최단 거리를 찾아보자.

현재는 1번에서 0번을 통해 가는 과정이다.

1->0->2에 대한 과정이다. 

총 11이라는 길이가 나왔고, 이것은 1->2의 길이 6보다 길기 때문에 고려하지 않는다.

1->0->3에 대한 과정이다.

총 12라는 길이가 나왔고, 이것은 1->3의 길이 2보다 길기 때문에 고려하지 않는다.

1->0->4에 대한 과정이다.

총 12라는 길이가 나왔고, 이것은 1->4의 길이 2보다 길기 때문에 고려하지 않는다.

이렇게 1번 정점에서 0번 정점을 거쳐 다른 정점 y로 갈때 거리는

그냥 1->y보다 모두 길기때문에 1->0->y는 모두 무시된다.

이제 1이 아닌 다른 값 -> 0 -> y를 찾아볼 차례이다.

2번 정점 -> 0번 정점 -> y번 정점을 갈 차례이다.

2->0->1에 대한 과정이다.

총 11이라는 길이가 나왔고, 이것은 2->1의 길이 2보다 길기 때문에 고려하지 않는다.

2->0->3에 대한 과정이다.

총 8이라는 길이가 나왔고, 이것은 2->3의 길이 3보다 길기 때문에 고려하지 않는다.

2->0->4에 대한 과정이다.

총 8이라는 길이가 나왔고, 이것은 2->4의 길이 7보다 길기 때문에 고려하지 않는다.

이렇게 2번 정점에서 0번 정점을 거쳐 다른 정점 y로 갈때 거리는

그냥 2->y보다 모두 길기때문에 2->0->y는 모두 무시된다.

이제 1,2가 아닌 다른 값 -> 0 -> y를 찾아볼 차례이다.

3번 정점 -> 0번 정점 -> y번 정점을 갈 차례이다.

3->0->1에 대한 과정이다.

총 15라는 길이가 나왔고, 이것은 3->1의 길이 3보다 길기 때문에 고려하지 않는다.

3->0->2에 대한 과정이다.

총 11이라는 길이가 나왔고, 이것은 3->2의 길이 7보다 길기 때문에 고려하지 않는다.

3->0->4에 대한 과정이다.

총 12라는 길이가 나왔고, 이것은 3->4의 길이 1보다 길기 때문에 고려하지 않는다.

이렇게 3번 정점에서 0번 정점을 거쳐 다른 정점 y로 갈때 거리는

그냥 3->y보다 모두 길기때문에 3->0->y는 모두 무시된다.

이제 1,2,3이 아닌 다른 값 -> 0 -> y를 찾아볼 차례이다.

4번 정점 -> 0번 정점 -> y번 정점을 갈 차례이다.

4->0->1에 대한 과정이다.

총 11이라는 길이가 나왔고, 이것은 4->1의 길이 7보다 길기 때문에 고려하지 않는다.

4->0->2에 대한 과정이다.

총 7이라는 길이가 나왔고, 이것은 4->2의 길이 4보다 길기 때문에 고려하지 않는다.

4->0->3에 대한 과정이다.

총 8이라는 길이가 나왔고, 이것은 4->3의 길이 2보다 길기 때문에 고려하지 않는다.

이렇게 4번 정점에서 0번 정점을 거쳐 다른 정점 y로 갈때 거리는

그냥 4->y보다 모두 길기때문에 4->0->y는 모두 무시된다.

이제 1,2,3,4가 아닌 다른 값 -> 0 -> y를 찾아볼 차례이다.

하지만 이제 1,2,3,4가 아닌 다른 값 -> 0 - > y가 존재하지 않는다.

따라서 0 다음인 x -> 1 -> y를 찾으러 간다.

0번 정점 -> 1번 정점 -> y번 정점을 갈 차례이다.

0->1->2에 대한 과정이다.

총 14라는 길이가 나왔고, 이것은 0->2의 길이 4보다 길기 때문에 고려하지 않는다.

0->1->3에 대한 과정이다.

총 10이라는 길이가 나왔고, 이것은 0->3의 길이 5보다 길기 때문에 고려하지 않는다.

0->1->4에 대한 과정이다.

총 10이라는 길이가 나왔고, 이것은 0->4의 길이 5보다 길기 때문에 고려하지 않는다.

이렇게 0번 정점에서 1번 정점을 거쳐 다른 정점 y로 갈때 거리는

그냥 0->y보다 모두 길기때문에 0->1->y는 모두 무시된다.

이제 0이 아닌 다른 값 -> 1 -> y를 찾아볼 차례이다.

(이제 곧 플로이드 워셜 알고리즘을 쓰는 이유가 나온다.. 조금만 더 집중해서 보도록 하자.)

(작성중인 저 또한 계속되는 반복에 어지럽습니다...)

2번 정점 -> 1번 정점 -> y번 정점을 갈 차례이다.

2->1->0에 대한 과정이다.

총 9라는 길이가 나왔고, 이것은 2->0의 길이 3보다 길기 때문에 고려하지 않는다.

2->1->3에 대한 과정이다.

총 4라는 길이가 나왔고, 이것은 2->3의 길이 3보다 길기 때문에 고려하지 않는다.

2->1->4에 대한 과정이다.

총 4라는 길이가 나왔고, 이것은 2->4의 길이 7보다 짧기 때문에 이 값을 2->4의 최단거리에 저장한다.

이렇게 2번 정점에서 1번 정점을 거쳐 다른 정점 y로 갈때 거리는

2->1->4 를 제외하고, 0->y보다 모두 길기때문에 0->1->y는 모두 무시된다.

이제 0,2가 아닌 다른 값 -> 1 -> y를 찾아볼 차례이다.

이렇게 계속해서 반복한다.

플로이드 워셜을 이미지로 설명하기에는 너무나 많으므로, 

또다른 플로이드 와셜의 예시의 과정을 처음부터 마지막까지 동영상으로 올리겠습니다.

값이 바뀌는 부분을 부분적 이미지로 올려보자면

<0->2->1>의 값 :: 6이 <0->1>의 값 :: 8보다 작으므로 업데이트 해준다.

<4->2->1>의 값 :: 6이 <4->1>의 값 :: 7보다 작으므로 업데이트 해준다.

<4->3->1>의 값 :: 5가 <4->1>의 값 :: 7보다 작으므로 업데이트 해준다.

<1->4->0>의 값 :: 5가 <1->0>의 값 :: 7보다 작으므로 업데이트 해준다.

<1->4->2>의 값 :: 6이 <1->2>의 값 :: 6과 같으므로 업데이트 해준다.(해주지 않아도 된다.)

<3->4->0>의 값 :: 4가 <3->0>의 값 :: 7보다 작으므로 업데이트 해준다.

<3->4->2>의 값 :: 5가 <3->2>의 값 :: 7보다 작으므로 업데이트 해준다.

<< 생각해보기 >> 

최초로 나왔던 2->1->4의 길이가 4고 2->4가 7이기에 2->4의 최단 거리가 4로 업데이트 되었지만,

3->2->4에서 3->4의 크기가 1밖에 되지않아, 3->2->1->4 같이 11인 길이인 경우 업데이트 되지 못한다.

실제 플로이드 워셜 알고리즘이 추적한 경로는 다음과 같다.