Dijkstra Algorithm in Kotlin

Dijkstra’s algorithm is a popular algorithm used in computer science to find the shortest path between two nodes in a weighted graph. The algorithm was invented by Edsger W. Dijkstra in 1956.

Here’s how the algorithm works:

Initialize the algorithm with a starting node and a list of all nodes in the graph.
Set the initial distance to the starting node as 0, and the distance to all other nodes as infinity.
Create an empty set of visited nodes.
While there are unvisited nodes:a. Select the unvisited node with the smallest distance, and mark it as visited.b. For each neighbor of the current node, calculate the distance from the starting node to that neighbor through the current node. If this distance is smaller than the previously calculated distance, update the distance.
When all nodes have been visited, the algorithm is complete. The shortest path from the starting node to any other node can be found by following the path with the smallest distance.

Dijkstra’s algorithm is commonly used in applications such as routing protocols in computer networks, finding shortest paths in road networks, and for solving other optimization problems involving weighted graphs.

Kotlin

import java.util.*

fun dijkstra(start: Int, graph: Array<Array<Pair<Int, Int>>>) {
    val n = graph.size
    val dist = IntArray(n) { Int.MAX_VALUE }
    dist[start] = 0
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
    pq.offer(Pair(start, 0))
    while (!pq.isEmpty()) {
        val (u, d) = pq.poll()
        if (d > dist[u]) continue
        for ((v, w) in graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w
                pq.offer(Pair(v, dist[v]))
            }
        }
    }
    println(dist.contentToString())
}

The dijkstra function takes two arguments: start, which is the index of the starting node, and graph, which is an adjacency list representation of the graph. Each element of graph is an array of pairs, where the first element of the pair is the index of a neighboring node, and the second element is the weight of the edge connecting the two nodes.

The function initializes an array dist to store the distances from the starting node to all other nodes in the graph. The distance to the starting node is set to 0, and the distance to all other nodes is initialized to Int.MAX_VALUE.

The function also uses a PriorityQueue to keep track of the nodes to visit next. The queue is initially populated with the starting node and its distance of 0.

The main loop of the function continues until the queue is empty. In each iteration, the function extracts the node with the smallest distance from the queue. If the distance to this node is greater than the distance already recorded in dist, the function skips the node.

For each neighbor of the current node, the function calculates the distance from the starting node to that neighbor through the current node. If this distance is smaller than the previously calculated distance, the distance is updated in dist and the neighbor is added to the queue.

After the loop completes, the function prints out the dist array, which contains the shortest distances from the starting node to all other nodes in the graph.

Kotlin

import java.util.*

fun dijkstra(start: Int, graph: Array<Array<Pair<Int, Int>>>) {
    val n = graph.size
    val dist = IntArray(n) { Int.MAX_VALUE }
    dist[start] = 0
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
    pq.offer(Pair(start, 0))
    while (!pq.isEmpty()) {
        val (u, d) = pq.poll()
        if (d > dist[u]) continue
        for ((v, w) in graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w
                pq.offer(Pair(v, dist[v]))
            }
        }
    }
    println(dist.contentToString())
}
fun main() {
    // Example graph with 5 nodes and 7 edges
    val graph = arrayOf(
        arrayOf(Pair(1, 2), Pair(2, 1)),
        arrayOf(Pair(0, 2), Pair(2, 3), Pair(3, 1)),
        arrayOf(Pair(0, 1), Pair(1, 3), Pair(3, 4)),
        arrayOf(Pair(1, 1), Pair(2, 4), Pair(4, 3)),
        arrayOf(Pair(3, 3))
    )
    dijkstra(0, graph) // Find shortest paths starting from node 0
}

In this example, we define a graph with 5 nodes and 7 edges, represented as an adjacency list in the graph array. We then call the dijkstra function with a starting node of 0 and the graph array as arguments.

The output of this program would be an array of integers representing the shortest distances from node 0 to all other nodes in the graph.

This indicates that the shortest path from node 0 to node 1 has a length of 2, the shortest path from node 0 to node 2 has a length of 1, and so on.

Leave a Comment Cancel reply