Kotlin coding test course, finding the minimum cost

Hello! In this post, we will discuss an algorithm problem that can be solved using Kotlin.
The topic is Finding the Minimum Cost. This problem can be presented in various forms and is a common type seen in coding tests.
In this article, I will explain a systematic problem-solving process that includes problem description, algorithm design, Kotlin code implementation, examples, and test cases.

Problem Description

There is a directed graph with N vertices and M edges. Each edge is irreversible and has a specific cost assigned.
Your task is to find the minimum cost from a specific starting vertex to the target vertex.
The edges can be connected in various ways, and there may be multiple paths leading to the same vertex.

Input Format:

  • The first line contains the number of vertices N and the number of edges M.
  • From the second line to the M-th line, edge information is given: starting vertex A, ending vertex B, cost C.
  • The last line contains the starting vertex and the target vertex.

Output Format:

  • Output the minimum cost to reach the target vertex from the starting vertex. If it is unreachable, output -1.

Example Input

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

Example Output

8

Problem Solving Approach

This problem is a shortest path problem and can be effectively solved using Dijkstra’s algorithm. Dijkstra’s algorithm
shows excellent performance in finding the shortest path from a specific starting vertex to all other vertices in a graph.
In this section, we will take a closer look at the overview of Dijkstra’s algorithm and how to implement it in Kotlin.

Overview of Dijkstra’s Algorithm

Dijkstra’s algorithm operates based on the following principles:

  • Initialize the shortest path from the starting vertex to all other vertices. Set the distance from the starting vertex to 0, and other vertices to infinity.
  • Use a priority queue to repeatedly select the vertex with the shortest path discovered so far.
  • Update distances for adjacent vertices based on the shortest path criteria.
  • Repeat this process until all vertices are selected or all remaining vertices have distances of infinity.

Through this process, we can ultimately find the minimum cost from the starting vertex to the target vertex.

Kotlin Code Implementation

Now let’s implement the Dijkstra’s algorithm in Kotlin to solve the problem.
We will first import the necessary libraries, process the input, and then implement the algorithm. 


import java.util.PriorityQueue

data class Edge(val to: Int, val cost: Int)

fun dijkstra(n: Int, edges: List>, start: Int): IntArray {
    val distance = IntArray(n + 1) { Int.MAX_VALUE }
    val priorityQueue = PriorityQueue>(compareBy { it.first })
    
    distance[start] = 0
    priorityQueue.add(0 to start)

    while (priorityQueue.isNotEmpty()) {
        val (currentDist, currentNode) = priorityQueue.poll()
        
        if (currentDist > distance[currentNode]) continue

        for (edge in edges[currentNode]) {
            val newDist = currentDist + edge.cost
            
            if (newDist < distance[edge.to]) {
                distance[edge.to] = newDist
                priorityQueue.add(newDist to edge.to)
            }
        }
    }

    return distance
}

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val edges = List(n + 1) { mutableListOf() }

    for (i in 1..m) {
        val (a, b, cost) = readLine()!!.split(" ").map { it.toInt() }
        edges[a].add(Edge(b, cost))
    }

    val (start, end) = readLine()!!.split(" ").map { it.toInt() }
    val distances = dijkstra(n, edges, start)

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

Code Explanation

The above code is a Kotlin program that uses Dijkstra’s algorithm to solve the problem. Let’s take a look at the main components of the code.

  • Edge Data Class: A data class that represents the edges of the graph. Each edge contains information about the destination vertex and the cost.
  • dijkstra Function: A function that implements Dijkstra’s algorithm. It takes the number of vertices n, the list of edges edges, and the starting vertex start as inputs.
    It initializes the distance array to store the shortest path information and uses a priority queue to search for paths.
  • main Function: Handles input and calls the dijkstra function. Finally, it outputs the minimum cost to the target vertex.
    If it cannot be reached, -1 is printed.

Test Cases

Let’s create some test cases to verify the functionality of the code.
It’s important to check the performance and accuracy of the code by considering various scenarios.

Test Case 1


Input:
5 6
1 2 2
1 3 3
2 4 1
3 4 4
2 5 5
4 5 1
1 5

Output:
8

Test Case 2


Input:
3 2
1 2 2
1 3 4
2 3 5
1 3

Output:
4

Test Case 3


Input:
4 3
1 2 10
2 3 5
3 4 10
1 4

Output:
-1

Conclusion

In this post, we learned about how to solve the minimum cost finding problem using Kotlin.
We explained how to efficiently find the shortest path in a graph using Dijkstra’s algorithm,
implemented it in Kotlin, and verified the code’s functionality with several test cases.
It was an opportunity to deepen our understanding of algorithms and Kotlin programming.
I will return with useful algorithm problems and solutions in the future.
Thank you!