Kotlin Coding Test Course: Finding the K-th Shortest Path

In this tutorial, we will solve the algorithm problem of finding the K-th shortest path using Kotlin. This problem utilizes shortest path algorithms, which are an important part of graph theory. Calculating the K-th shortest path in a given graph is often considered a complex problem, but with the appropriate algorithms and data structures, it can be solved efficiently.

Problem Description

The problem is to find the K-th shortest path between two points A and B when a graph is given. The weights of the paths are positive, and K is set to be 1 or greater. Paths may overlap, and K starts from 1. Thus, K=1 refers to the shortest path, while K=2 refers to the second shortest path. If the K-th path does not exist, “NO PATH” should be output.

4 5 2
1 2 1
1 3 4
2 3 2
2 4 6
3 4 3
        

3
        

Approach to Solve the Problem

To solve this problem, we will use Dijkstra’s algorithm along with a priority queue to find the K-th shortest path. This approach can be extended to find multiple shortest paths from a single starting point. The basic idea is to repeat the process of finding the shortest path K times and store the K-th length at each step.

1. Set up Data Structures

First, we need to set up a data structure to store the K-th shortest path information for each node. We can use a 2D array for this purpose. The index of each array represents the node ID, and the second index represents the K-th path.

val distance = Array(n + 1) { IntArray(k + 1) { Int.MAX_VALUE } }
    

2. Build the Graph

The graph will be represented in the form of an adjacency list. To do this, we will store the connected vertices and weights for each vertex. We will construct the graph from the input.

val graph = mutableListOf>()
for (i in 0 until n + 1) {
    graph.add(mutableListOf())
}
for (i in 0 until m) {
    val (u, v, w) = readLine()!!.split(" ").map { it.toInt() }
    graph[u].add(Edge(v, w))
}
    

3. Algorithm to Find the K-th Shortest Path

We will use a priority queue to find the shortest path. We will update the distance while adding each path to the queue. The distance array will be managed appropriately to store the K-th shortest path.

val queue = PriorityQueue(compareBy { it.weight })
distance[start][0] = 0
queue.add(Edge(start, 0))

while (queue.isNotEmpty()) {
    val current = queue.poll()
    val currentNode = current.node
    val currentWeight = current.weight
    
    for (edge in graph[currentNode]) {
        val nextNode = edge.node
        val newWeight = currentWeight + edge.weight
        if (distance[nextNode][k - 1] > newWeight) {
            distance[nextNode].sort()
            distance[nextNode][k - 1] = newWeight
            queue.add(Edge(nextNode, newWeight))
        }
    }
}
    

4. Output the Result

Finally, we will output the distance of the K-th shortest path. If the K-th path does not exist, we will output “NO PATH”.

if (distance[end][k - 1] == Int.MAX_VALUE) {
    println("NO PATH")
} else {
    println(distance[end][k - 1])
}
    

Full Code

fun main() {
    val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }
    val graph = mutableListOf>()
    
    for (i in 0..n) {
        graph.add(mutableListOf())
    }
    
    for (i in 0 until m) {
        val (u, v, w) = readLine()!!.split(" ").map { it.toInt() }
        graph[u].add(Edge(v, w))
    }
    
    val distance = Array(n + 1) { IntArray(k + 1) { Int.MAX_VALUE } }
    val queue = PriorityQueue(compareBy { it.weight })
    
    distance[1][0] = 0
    queue.add(Edge(1, 0))

    while (queue.isNotEmpty()) {
        val current = queue.poll()
        val currentNode = current.node
        val currentWeight = current.weight
        
        for (edge in graph[currentNode]) {
            val nextNode = edge.node
            val newWeight = currentWeight + edge.weight

            if (distance[nextNode][k - 1] > newWeight) {
                distance[nextNode].sort()
                distance[nextNode][k - 1] = newWeight
                queue.add(Edge(nextNode, newWeight))
            }
        }
    }
    
    if (distance[n][k - 1] == Int.MAX_VALUE) {
        println("NO PATH")
    } else {
        println(distance[n][k - 1])
    }
}

data class Edge(val node: Int, val weight: Int)
    

Conclusion

Finding the K-th shortest path is a graph problem with various algorithmic approaches possible. In the above example, we explained how to find the K-th shortest path by modifying Dijkstra’s algorithm. In practice, a variety of algorithms or optimization techniques can be applied, and it is important to choose the right algorithm depending on the problem.

The K-th shortest path finding problem we learned in this tutorial is often encountered in coding interviews, so it is advisable to improve your skills through various practice problems.