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

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

흔히들 알고 있는 최단 경로 알고리즘인 다익스트라 알고리즘에서는 가장 적은 비용을 하나씩 선택해야 했다면 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 특징이 있습니다.

이러한 플로이드 와샬 알고리즘은 기본적으로 다이나믹 프로그래밍 기술에 의거합니다! 모든 경로에 대해 최솟값으로 갱신해주거든여!! 

package floydwarshall

import kotlin.math.min

private lateinit var arr: Array<IntArray>
private const val INF = 1000000000
private fun main() {

    arr = arrayOf(
            intArrayOf(0, 5, INF, 8),
            intArrayOf(7, 0, 9, INF),
            intArrayOf(2, INF, 0, 4),
            intArrayOf(INF, INF, 3, 0)
    )
    floydWarshall()
}

private fun floydWarshall() {


    // 노드 개수 :4
    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()
    }
}