Kotlin에서 최단 경로 알고리즘 구현하기: 다익스트라와 플로이드-워셜

최단 경로 문제는 그래프 이론에서 두 노드 간의 가장 짧은 경로를 찾는 문제로, 교통 네트워크 최적화, 네트워크 라우팅 프로토콜 등 다양한 분야에서 응용됩니다. Kotlin을 활용해 이 문제를 해결하는 데에는 여러 알고리즘이 있으나, 여기서는 가장 널리 알려진 두 가지 알고리즘인 다익스트라(Dijkstra) 알고리즘과 플로이드-워셜(Floyd-Warshall) 알고리즘을 소개합니다.

다익스트라 알고리즘

다익스트라 알고리즘은 하나의 소스 노드에서 다른 모든 노드로의 최단 경로를 찾는 데 사용됩니다. 가중치가 있는 그래프에서 작동하며, 가중치는 음수가 아니어야 합니다. Kotlin에서의 구현 예제는 다음과 같습니다:

fun dijkstra(graph: Array<IntArray>, src: Int): IntArray {
    val V = graph.size
    val dist = IntArray(V) { Int.MAX_VALUE }
    val sptSet = BooleanArray(V)

    dist[src] = 0

    for (count in 0 until V - 1) {
        val u = minDistance(dist, sptSet)
        sptSet[u] = true

        for (v in 0 until V) {
            if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Int.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v]
            }
        }
    }
    return dist
}

fun minDistance(dist: IntArray, sptSet: BooleanArray): Int {
    var min = Int.MAX_VALUE
    var minIndex = -1

    for (v in dist.indices) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v]
            minIndex = v
        }
    }
    return minIndex
}

 

이 알고리즘은 선택되지 않은 노드 중에서 가장 거리가 짧은 노드를 찾아 선택하고, 해당 노드를 경유하여 다른 노드로 가는 거리를 갱신하는 과정을 반복합니다.

플로이드-워셜 알고리즘

플로이드-워셜 알고리즘은 그래프 내의 모든 노드 쌍 간의 최단 경로를 찾는 데 사용됩니다. 가중치가 있는 그래프에서 음수 가중치를 가진 간선이 있어도 작동합니다(단, 음수 가중치 순환은 없어야 합니다). Kotlin에서의 구현 예제는 다음과 같습니다:

fun floydWarshall(graph: Array<IntArray>): Array<IntArray> {
    val dist = graph.map { it.clone() }.toTypedArray()
    val V = graph.size

    for (k in 0 until V) {
        for (i in 0 until V) {
            for (j in 0 until V) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }
    return dist
}

 

이 알고리즘은 모든 노드 쌍에 대해 각 노드를 경유하는 경우를 고려하여 최단 경로를 찾습니다.

 

Kotlin을 이용한 다익스트라와 플로이드-워셜 알고리즘 구현은 최단 경로 문제를 해결하는 데 있어 강력한 도구를 제공합니다. 이러한 알고리즘을 이해하고 구현할 수 있다면, 복잡한 네트워크 시스템의 설계와 최적화에 크게 기여할 수 있을 것입니다. Kotlin의 간결하고 표현력 있는 문법은 이러한 알고리즘을 이해하고 구현하는 데 있어 뛰어난 가독성과 유지보수성을 제공합니다.