## DEV Community is a community of 877,885 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

fy

Posted on

# Finding Shortest Paths in a Graph - Dijkstra's Algorithm

Dijkstra's algorithm is used to find the shortest path(s) from node x to all its connected nodes.

Consider the following weighted graph.

Whats the shortest path from node 0 to node 3?

We can look at the followings possible paths

``````7: 0 <--> 3
11: 0 <--> 4 <--> 3
7: 0 <--> 1 <--> 3
6: 0 <--> 1 <--> 2 <--> 3
``````

The fourth path is the shortest path since we can look at the edges and see how long it will take to get there. But this is a small example, we can have graphs with millions of nodes and edges.

So how do we do this programmatically?

There are many algorithms for finding the shortest path between nodes within a graph but the focus here is Dijkstra's algorithm.

Implementation steps:

1. Use DFS to visit the smallest nodes first.
2. Compare parent distance and edge weight with node distance. In case it's less than infinity or calculated distance then update it.
3. Use recursive programming to visit the smallest nodes.

Code:

``````data class Vertex(val name: String, var distance: Int = Int.MAX_VALUE, var visited: Boolean = false)
{

edges.sortedBy { it.weight }.forEach {
}
}
}

data class Path(val start: Vertex, val end: Vertex, val weight: Int)
``````

Add a row class, this is used to print a table row at the end

``````data class DistanceRow(val to: String, val distance: Int, val via: String, ) {
override fun toString(): String {
return """
\$to | \$distance | \$via
""".trimIndent()
}
}
``````

Dijkstra's algorithm

``````class Dijkstra {
val distances = mutableListOf<DistanceRow>()

fun shortestPath(vertex: Vertex, d: Int = 0) {
vertex.visited = true

val distance = d + edge.weight
val connectedEdge = edge.end

if (distance < connectedEdge.distance) {
connectedEdge.distance = distance
}
if (!connectedEdge.visited) {
shortestPath(connectedEdge, connectedEdge.distance)
}
}
}
}
``````

Running the code

``````fun main() {
val zero = Vertex("0")
val one = Vertex("1")
val two = Vertex("2")
val three = Vertex("3")
val four = Vertex("4")

Path(zero, one, 3),
Path(zero, four, 8),
Path(zero, three, 7),
))

Path(one, two, 1),
Path(one, three, 4),
))

Path(two, three, 2),
))

Path(three, two, 2),
))

Path(four, three, 3)
))

Dijkstra().apply {
shortestPath(zero)
print("Distances:\n---------------\nTo|Dist|Via\n---------------\n")
distances.forEach {
println(it)
}
}

}
``````

Output:

``````Distances:
---------------
To|Dist|Via
---------------
1 | 3 | 0
2 | 4 | 1
3 | 6 | 2
4 | 8 | 0
``````

Note: The example focuses on finding the shortest path from node 0 to node 3 therefore the edges have more connectivity between these nodes. Some edges are still undirected. Add directed edges for other nodes if needed.