Skip to content

Instantly share code, notes, and snippets.

@VizGhar
Created Oct 10, 2022
Embed
What would you like to do?
Dijkstra implementation in Kotlin language
private const val startPoint = "A"
private const val finalPoint = "G"
data class Vertex(val id: String, val length: Int)
// adjacency list graph
val graph =
mapOf(
"A" to listOf(Vertex("B", 3), Vertex("C", 5)),
"B" to listOf(Vertex("A", 3), Vertex("D", 4), Vertex("E", 2)),
"C" to listOf(Vertex("A", 5), Vertex("D", 3)),
"D" to listOf(Vertex("C", 3), Vertex("B", 4)),
"E" to listOf(Vertex("B", 2), Vertex("F", 2), Vertex("G", 3)),
"F" to listOf(Vertex("E", 2), Vertex("G", 2)),
"G" to listOf(Vertex("F", 2), Vertex("E", 3)),
)
data class Item(
val id: String,
var length: Int = Int.MAX_VALUE,
var bestPath: List<String> = emptyList()
)
fun main() {
// initialize priority queue
val queue = graph
.map { Item(it.key, if (it.key == startPoint) 0 else Int.MAX_VALUE) }
.toMutableList()
// while target is not on top of priority queue
while (queue[0].id != finalPoint) {
// remove item from priority queue
val item = queue.removeAt(0)
graph[item.id]!!.forEach { edge ->
val neighbor = queue.firstOrNull { it.id == edge.id } ?: return@forEach
// compute new distance from $item to $neighbor following $edge
val alt = edge.length + item.length
// update priority queue if new distance is smaller than actual
if (neighbor.length > alt) {
neighbor.length = alt
neighbor.bestPath = item.bestPath + edge.id
}
}
queue.sortBy { it.length }
}
println("Shortest distance from $startPoint to $finalPoint is ${queue[0].length}")
println(queue[0].bestPath.joinToString(" -> "))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment