DEV Community

fy
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.

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
Enter fullscreen mode Exit fullscreen mode

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:
Add Vertex and Path classes

data class Vertex(val name: String, var distance: Int = Int.MAX_VALUE, var visited: Boolean = false)
{
    val linkedEdges = mutableListOf<Path>()

    fun addEdges(edges: List<Path>) {
        edges.sortedBy { it.weight }.forEach {
            linkedEdges.add(it)
        }
    }
}

data class Path(val start: Vertex, val end: Vertex, val weight: Int)
Enter fullscreen mode Exit fullscreen mode

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()
    }
}
Enter fullscreen mode Exit fullscreen mode

Dijkstra's algorithm

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

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

        for (edge in vertex.linkedEdges) {
            val distance = d + edge.weight
            val connectedEdge = edge.end

            if (distance < connectedEdge.distance) {
                connectedEdge.distance = distance
                distances.add(DistanceRow(connectedEdge.name, distance, vertex.name))
            }
            if (!connectedEdge.visited) {
                shortestPath(connectedEdge, connectedEdge.distance)
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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")

    zero.addEdges(listOf(
        Path(zero, one, 3),
        Path(zero, four, 8),
        Path(zero, three, 7),
    ))

    one.addEdges(listOf(
        Path(one, two, 1),
        Path(one, three, 4),
    ))

    two.addEdges(listOf(
        Path(two, three, 2),
    ))

    three.addEdges(listOf(
        Path(three, two, 2),
    ))

    four.addEdges(listOf(
        Path(four, three, 3)
    ))

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

}
Enter fullscreen mode Exit fullscreen mode

Output:

Distances:
---------------
To|Dist|Via
---------------
1 | 3 | 0
2 | 4 | 1
3 | 6 | 2
4 | 8 | 0
Enter fullscreen mode Exit fullscreen mode

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.

Src code: https://github.com/faizzed/datastructures-algorithms/blob/master/src/main/kotlin/algorithms/graphs/DijkstraShortestPath.kt

Discussion (0)