Kotlin coding test course, finding the fastest bus route

As part of the coding test course using Kotlin, we will tackle the problem of finding the fastest bus route. In modern society, public transportation is an important means of transportation, and understanding the travel routes by bus is a feature that many people need. In this problem, we will design and implement an algorithm that calculates the shortest time according to the given conditions.

Problem Definition

Several bus routes are given as follows. Each route includes a starting station, an arrival station, and the time taken. Your goal is to find the fastest time taken from a specific starting station to a specific arrival station.

Problem Input

- Number of stations N (1 ≤ N ≤ 100)
- Number of routes M (1 ≤ M ≤ 1000)
- Each route information: starting station A, arrival station B, time taken T (1 ≤ A, B ≤ N, 1 ≤ T ≤ 1000)
- Starting station S and arrival station D

Problem Output

- The fastest time taken to go from the starting station to the arriving station. Output -1 if it is impossible.

Problem Solving Strategy

This problem is about finding the shortest path, and an appropriate algorithm to use is Dijkstra’s shortest path algorithm. The Dijkstra algorithm is useful for finding the shortest path from a starting vertex to all other vertices in a weighted graph. We will build a graph using the bus route information and use that graph to calculate the shortest time.

Step-by-Step Approach

Step 1: Define Input Data Structure

First, based on the provided route information, we will decide how to represent the graph. It is efficient to manage each station’s associated route information using an adjacency list.

val graph: Array>> = Array(N + 1) { mutableListOf() }

Step 2: Process Input Data

Convert the route information received from the user into graph form. Add each route information to the graph in the appropriate format.

for (i in 0 until M) {
    val (A, B, T) = readLine()!!.split(" ").map { it.toInt() }
    graph[A].add(Pair(B, T))
}

Step 3: Implement Dijkstra’s Algorithm

Use Dijkstra’s algorithm to calculate the shortest path for all stations. A priority queue is used to process the route with the least current time first.

fun dijkstra(start: Int): IntArray {
    val distances = IntArray(N + 1) { Int.MAX_VALUE }
    distances[start] = 0
    val priorityQueue = PriorityQueue>(compareBy { it.second })
    priorityQueue.add(Pair(start, 0))

    while (priorityQueue.isNotEmpty()) {
        val (currentStation, currentTime) = priorityQueue.poll()

        if (currentTime > distances[currentStation]) continue

        for (edge in graph[currentStation]) {
            val (nextStation, travelTime) = edge
            val newTime = currentTime + travelTime

            if (newTime < distances[nextStation]) {
                distances[nextStation] = newTime
                priorityQueue.add(Pair(nextStation, newTime))
            }
        }
    }
    return distances
}

Step 4: Output Result

Finally, output the shortest time taken to go from the starting station to the arrival station. If it is not possible to reach the arrival station, output -1.

val distances = dijkstra(S)
println(if (distances[D] == Int.MAX_VALUE) -1 else distances[D])

Complete Code Example

fun main() {
    val (N, M) = readLine()!!.split(" ").map { it.toInt() }
    val graph: Array>> = Array(N + 1) { mutableListOf() }

    for (i in 0 until M) {
        val (A, B, T) = readLine()!!.split(" ").map { it.toInt() }
        graph[A].add(Pair(B, T))
    }

    val (S, D) = readLine()!!.split(" ").map { it.toInt() }
    val distances = dijkstra(S)

    println(if (distances[D] == Int.MAX_VALUE) -1 else distances[D])
}

fun dijkstra(start: Int): IntArray {
    val distances = IntArray(N + 1) { Int.MAX_VALUE }
    distances[start] = 0
    val priorityQueue = PriorityQueue>(compareBy { it.second })
    priorityQueue.add(Pair(start, 0))

    while (priorityQueue.isNotEmpty()) {
        val (currentStation, currentTime) = priorityQueue.poll()

        if (currentTime > distances[currentStation]) continue

        for (edge in graph[currentStation]) {
            val (nextStation, travelTime) = edge
            val newTime = currentTime + travelTime

            if (newTime < distances[nextStation]) {
                distances[nextStation] = newTime
                priorityQueue.add(Pair(nextStation, newTime))
            }
        }
    }
    return distances
}

Conclusion

In this lecture, we solved the problem of choosing the fastest bus route using Kotlin. We learned how to address the shortest path problem through the Dijkstra algorithm and how to implement the various elements of the problem in code. Algorithm problems can improve through practice, so it is recommended to continuously try solving various problems.