kotlin coding test course, Dijkstra

Solution Process

The Dijkstra algorithm is an algorithm for finding the shortest path from one vertex to another in a graph.
This algorithm works correctly only when there are no negative weights, so it is important to check whether the weights are non-negative.

Below is the implementation process of the Dijkstra algorithm using Kotlin.

1. Graph Representation

To represent the graph, we use an adjacency list.
For each vertex, we store the vertices reachable from that vertex and the weight of the edge.
For example, we can represent each vertex as a list using an integer array.

    val graph = Array(N) { mutableListOf>() }
    

2. Input Processing

Add the edge information received as input to the graph.
According to the input format, we store the information of each edge through a loop.

    for (i in 0 until M) {
        val (A, B, C) = readLine()!!.split(" ").map { it.toInt() }
        graph[A-1].add(Pair(B-1, C)) // Edge from A to B with weight C
    }
    

3. Dijkstra Algorithm Implementation

Implement the algorithm to find the current shortest path using a priority queue.
Below is the core logic of the Dijkstra algorithm.

    fun dijkstra(start: Int) {
        val distance = Array(N) { Int.MAX_VALUE }
        distance[start] = 0
        
        val pq = PriorityQueue>(compareBy { it.second })
        pq.add(Pair(start, 0))

        while (pq.isNotEmpty()) {
            val (current, dist) = pq.poll()

            if (dist > distance[current]) continue

            for (next in graph[current]) {
                val (nextNode, weight) = next
                val newDist = dist + weight

                if (newDist < distance[nextNode]) {
                    distance[nextNode] = newDist
                    pq.add(Pair(nextNode, newDist))
                }
            }
        }
    }
    

4. Output Result

Finally, calculate and print the shortest distance to the endpoint.
If the endpoint is unreachable, print -1.

    dijkstra(S - 1)
    val result = if (distance[E - 1] == Int.MAX_VALUE) -1 else distance[E - 1]
    println(result)
    

Entire Code

Based on the above logic, a complete code is as follows.

    import java.util.*

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

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

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

        fun dijkstra(start: Int) {
            val distance = Array(N) { Int.MAX_VALUE }
            distance[start] = 0

            val pq = PriorityQueue>(compareBy { it.second })
            pq.add(Pair(start, 0))

            while (pq.isNotEmpty()) {
                val (current, dist) = pq.poll()

                if (dist > distance[current]) continue

                for (next in graph[current]) {
                    val (nextNode, weight) = next
                    val newDist = dist + weight

                    if (newDist < distance[nextNode]) {
                        distance[nextNode] = newDist
                        pq.add(Pair(nextNode, newDist))
                    }
                }
            }
            return distance
        }

        dijkstra(S - 1)
        val result = if (distance[E - 1] == Int.MAX_VALUE) -1 else distance[E - 1]
        println(result)
    }