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

플로이드 워셜 알고리즘이란?

---

플로이드 워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 이전에 배웠던 다익스트라 알고리즘은 한 노드에서 가능한 모든 노드 쌍에 대해 최단 거리를 구했기 때문에 이 점이 2가지의 알고리즘에  차이라고 할 수 있다. 플로이드 워셜 알고리즘의 시간 복잡도는 O(N³)으로 3중 for문으로 보통 모든 경우의 수를 비교한다.

 

 플로이드 워셜 알고리즘의 핵심은 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다. 그래서 k를 두어서 모든 노드에 대해서 최단 거리를 구할 수 있도록 하였다.

fun floydWarshall() {
    val d = Array(4) { IntArray(4) }
    for (i in 0 until 4) {
        for (j in 0 until 4) {
            d[i][j] = arr[i][j]
        }
    }

    for (k in 0 until 4) 
    	for (i in 0 until 4) 
        	for (j in 0 until 4)
        		d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    for (i in 0 until 4){
        for (j in 0 until 4){
            print("${d[i][j]} ")
        }
        println()
    }
}