kotlin coding test course, finding the shortest path

Problem Description

Finding the shortest path from a specific starting point to all other vertices is a very important problem in graph theory.
Various algorithms can be used to solve this problem, including Dijkstra’s algorithm, Bellman-Ford algorithm, and Floyd-Warshall algorithm.

In this lecture, we will focus on Dijkstra’s algorithm to address the problem of finding the shortest path.
The specific form of the problem is as follows.

After constructing a directed graph with the given edges, find the shortest path from the starting vertex to all other vertices.
Input consists of the number of vertices N and the number of edges M,
and each edge consists of the starting vertex A, the destination vertex B, and the weight C.

Example Problem

Input example:

Output example:

Here, the first line represents the number of vertices (N) and the number of edges (M),
and from the next line, the information of each edge is presented.
The starting vertex is 1, and 0 means the shortest path to itself.

Problem Solving Process

1. Overview of Dijkstra’s Algorithm

Dijkstra’s algorithm is an algorithm for finding the shortest path from the starting vertex to all other vertices in a graph.
This algorithm is valid for graphs with non-negative weights and is generally implemented using a priority queue.

The basic idea of this algorithm is to update the paths between vertices that have not yet had their shortest paths calculated based on the shortest path found so far at each step.

2. Steps of the Algorithm

Initialize the distances from the starting vertex to all vertices to infinity, except for the starting vertex which is initialized to 0.
Select the currently closest vertex using a priority queue.
Update the distance values of adjacent vertices using the distance of the selected vertex.
Repeat steps 2 and 3 until the distances of all vertices are finalized.

3. Kotlin Code Implementation

Now, let’s implement this process in Kotlin. Below is the code that solves the given problem using Dijkstra’s algorithm.

                
                    import java.util.PriorityQueue
                    import kotlin.math.min

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

                    fun dijkstra(n: Int, edges: List>, start: Int): IntArray {
                        val graph = MutableList(n + 1) { mutableListOf() }
                        for ((a, b, c) in edges) {
                            graph[a].add(Edge(b, c))
                        }

                        val distances = IntArray(n + 1) { Int.MAX_VALUE }
                        distances[start] = 0

                        val priorityQueue = PriorityQueue>(compareBy { it.first })
                        priorityQueue.add(0 to start)

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

                            if (dist > distances[current]) continue

                            for (edge in graph[current]) {
                                val newDist = dist + edge.weight
                                if (newDist < distances[edge.target]) {
                                    distances[edge.target] = newDist
                                    priorityQueue.add(newDist to edge.target)
                                }
                            }
                        }

                        return distances
                    }

                    fun main() {
                        val input = readLine()!!.split(" ").map { it.toInt() }
                        val n = input[0]
                        val m = input[1]

                        val edges = mutableListOf>()
                        for (i in 0 until m) {
                            val edgeInput = readLine()!!.split(" ").map { it.toInt() }
                            edges.add(Triple(edgeInput[0], edgeInput[1], edgeInput[2]))
                        }

                        val distances = dijkstra(n, edges, 1)

                        for (i in 1..n) {
                            println(if (distances[i] == Int.MAX_VALUE) "INF" else distances[i])
                        }
                    }

In the above code, the dijkstra function takes the number of vertices and edge information as input and calculates the shortest path from the starting vertex.
The distances array stores the shortest path distances to each vertex, initially set to infinity.

After processing the given input, the main function outputs the distances array.
If there are vertices that cannot be reached, they are marked as “INF”.

Testing and Verification

After implementing the algorithm, various test cases should be conducted to verify the accuracy of the code.
For example, consider the following additional test case:

The operation result should be as follows:

Verify the accuracy by providing actual input and comparing the output of the code.
It is also important to consider various scenarios and handle edge cases.

Conclusion

In this lecture, we covered the problem of finding the shortest path using Dijkstra’s algorithm.
We passed through the process of implementing the algorithm in Kotlin, connecting theoretical background with actual implementation.
While preparing for coding tests, learn various algorithms and data structures to enhance your problem-solving capabilities.