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

플로이드 와샬(Floyd-Warshall) 알고리즘은 모든 정점에서 모든 다른 정점까지의 최단 경로를 구하는 알고리즘 입니다.

이 알고리즘은 다익스트라(Dijkstra) 알고리즘과는 달리 음의 가중치를 가진 그래프에서도 사용할 수 있습니다.

이 알고리즘은 동적 계획법을 사용하여 구현되며, 시간 복잡도는 O(n^3)입니다.

 

알고리즘의 동작 방식은 아래와 같습니다.

1. 그래프의 인접 행렬을 만듭니다.
2. 3중 반복문을 이용하여 모든점을 순회합니다.
3. i에서 j로 가는 최단 거리를 d[i][j]라고 할 때, d[i][j] = min(d[i][j], d[i][k] + d[k][j])의 점화식을 이용하여 d[i][j]를 갱신합니다.

이 때, k는 1부터 n까지의 정점입니다.

이제 Kotlin으로 플로이드 와샬 알고리즘을 구현해보겠습니다.

fun floydWarshall(graph: Array<IntArray>): Array<IntArray> {
    val n = graph.size
    val dist = Array(n) { i -> graph[i].copyOf() }

    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    return dist
}

위 코드에서 graph는 인접 행렬을 나타내는 2차원 배열입니다.

dist는 최단 거리를 저장하는 2차원 배열로, 초기 값은 graph의 값으로 초기화됩니다.

그리고 3중 반복문을 이용하여 dist를 갱신하고, 마지막에 최종 dist를 반환합니다.

이렇게 플로이드 와샬 알고리즘을 Kotlin으로 구현할 수 있습니다.