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

이전에 다익스트라 알고리즘을 알아봤었습니다

https://kuk6933.tistory.com/78

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

다익스트라 알고리즘은 특정 정점에서 모든 정점까지의 최단 경로를 구하는 알고리즘이었습니다.

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘입니다.

 

플로이드 와샬 알고리즘은 경유 노드를 기준으로 진행됩니다.

만약 노드 A -> 노드 B로의 최단 경로를 찾고싶은 경우에

A -> B, 일때랑 임의의 노드 S를 경유해 A -> S -> B를 갈때의 비용을 비교해서 완성해 나가는것이죠 

모든 노드를  경유지로 잡아서 과정을 진행해줍니다.

 

예시와 함께 보겠습니다

https://blog.naver.com/ndb796/221234427842

이 그래프로 해보겠습니다

0	5	inf	8
7	0	9	inf
2	inf	0	4
inf	inf	3	0

자기 자신은 0, 직접적인 간선이 없는 노드는 inf(무제한)으로 초기화합니다

이 배열은 현재까지 계산된 최소 비용이고 거쳐가는 정점을 기준으로 업데이트해 나갈것입니다.

 

1. 노드 1을 거쳐가는 경우

0	5	inf	8
7	0	9	15
2	7	0	4
inf	inf	3	0

노드 1을 거쳐가는 경우를 고려해서 업데이트 해줍니다

2 -> 1 -> 4

2 -> 1 -> 4 -> 3

3 -> 1 -> 2

3 -> 1 -> 4

4 -> 3 -> 1 -> 2

4 -> 3 -> 1 -> 3

이 경우들을 업데이트 시켜줘야합니다.

즉 X 노드에서 Y노드로 가는 거리 VS X노드에서 노드1로 가는 거리 + 노드 1 에서 노드 Y로 가는 거리

이 비교를 해서 더 작은 값으로 업데이트 시켜주는 것이죠

이렇게 똑같이 노드2, 노드3, 노드4 에대해 수행하면

0	5	11	8
7	0	9	13
2	7	0	4
5	10	3	0

이런 결과를 만들 수 있습니다

 

플로이드 와샬 알고리즘의 시간복잡도

요약: 모든 노드는 경유 노드가 될 수 있기에 O(N²)의 단계를 N번 반복하기에 총 시간복잡도는  O(N³)입니다.

경유 노드를 제외한 (N-1)개의 노드는 각각 시작 노드가 됩니다. 그리고 (N-1)개의 노드중 시작 노드를 제외한 나머지 노드들이 도착 노드가 되므로 N-1 개의 노드 중 임의의 두 노드를 나열하는 개수만큼의 비교 연산이 필요합니다. 그러므로 각 단계O(N²)의 시간복잡도를 가집니다. 이 단계를 총 N개의 노드에 대해 시행하므로 시간 복잡도는  O(N³)입니다.

 

 

참고

https://camel-it.tistory.com/104

플로이드워셜(Floyd–Warshall) 알고리즘

https://blog.naver.com/ndb796/221234427842