플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)이란?
그래프 혹은 이차원 배열에서 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용한다.
가중치가 있는 그래프에서 각각의 지점까지의 최소 거리를 구하는 알고리즘 이다.
ABCD라는 네 지점이 있고, 각각의 가중치가 아래와 같다고 가정한다.
A-B 10
A-C 3
A-D 4
B-C 3
B-D 5
C-D 7
이런 가중치가 있을 경우 A에서 B를 가는 최소 경로를 구해보자.
A에서 바로 B로 가는 경우 10의 가중치이지만, A-C-B로 간다면 6이 가중치로 더 적은 거리로 이동할 수 있다.
더 쉽게 말하자면 서울에서 부산을 간다고 생각해보자.
그런데 오후 늦게 출발을 해서 대전 혹은 대구에서 하룻밤을 보내고 가야한다. 이때 최소거리로 이동하고 싶다면 어디서 쉬어야할까?
서울에서 대구는 298km, 서울에서 대전은 162km가 걸린다. 그리고 대구에서 부산은 109km가 걸리고, 대전에서 부산은 259km가 걸린다.
서울에서 대구를 거쳐서 부산에 간다면 298 + 109 = 407km
서울에서 대전을 거쳐서 부산을 간다면 162 + 259 = 421km
즉 가중치 상으로 서울에서 대구를 거쳐서 부산을 가는게 더 최소 경로다.
이러한 가중치가 있을때 최소 경로를 구하는 알고리즘이다.
그건 다익스트라 아닌가?
맞다. 단순히 위에 설명한 내용상으론 다익스트라와 다른점이 없다.
다익스트라는 한 점으로부터 다른 곳까지의 최단 경로를 구하는 알고리즘이지만, 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해준다.
즉 A에서 출발해서 BCD까지 가는 최단경로만 구해주는 것이 아니라 B에서 ACD의 최단경로, C에서 ABD의 최단경로, D에서 ABC의 최단경로까지 전부 구해준다.
그럼 어떻게 쓸까?
D_ab = min(D_ab, D_ak + D_kb)위와같은 점화식을 활용하면 된다. D_ab라는 것은 a에서 b로 이동하는 거리를 뜻한다. 그렇다면 D_ak는 a에서 k로 이동하는 거리, D_kb는 k에서 b로 이동하는 거리를 뜻한다.
즉. a에서 b로 이동할때 바로 가는 것과 어디 한곳을 거쳐서 가는 것 중 더 작은값(가까운 거리)를 저장한다는 뜻이다.
저걸 총 몇번 하냐면 3중 반복이다 ㅋㅋㅋㅋㅋ
요소가 N개일 경우 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 "모든 경로"를 고려해서 계산한다.
Ex)
// 총 요소의 갯수가 n개, 2차원 배열의 이름을 graph라고 가정한다.
// Kotlin
for (k in 1 .. n)
for (i in 1 .. n)
for (j in 1 .. n)
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])이렇게 반복시키면 끝이다. 참 쉽죠?
시간복잡도는?
시간 복잡도는 총 O(N^3)이다.
사실 난 정말 특별한 경우 아니면 이 알고리즘은 잘 안쓸 것 같긴 하다.
왜냐고? 시간복잡도를 보자.... O(N^2)만 돼도 지양하며 코드를 작성하고 있는데 O(N^3)이란다...
그래도 알고있지만 안쓰는것과 몰라서 못쓰는 것과는 차이가 있기때문에 일단 공부해봤다.
세상에 나쁜 알고리즘은 없다... 더 좋은 알고리즘이 있는거지....