22
Dijkstra’s Algorithm
Written by Irina Galata, Kelvin Lau and Vincent Ngo
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.
Have you ever used the Google or Apple Maps app to find the shortest distance or fastest time from one place to another? Dijkstra’s algorithm is particularly useful in GPS networks to help find the shortest path between two places.
Dijkstra’s algorithm is a greedy algorithm. A greedy algorithm constructs a solution step-by-step, and it picks the most optimal path at every step. In particular, Dijkstra’s algorithm finds the shortest paths between vertices in either directed or undirected graphs. Given a vertex in a graph, the algorithm will find all shortest paths from the starting vertex.
Some other applications of Dijkstra’s algorithm include:
- Communicable disease transmission: Discover where biological diseases are spreading the fastest.
- Telephone networks: Routing calls to highest-bandwidth paths available in the network.
- Mapping: Finding the shortest and fastest paths for travelers.
Example
All the graphs you’ve looked at thus far have been undirected graphs. Let’s change it up a little and work with a directed graph! Imagine the directed graph below represents a GPS network:
The vertices represent physical locations, and the edges between the vertices represent one way paths of a given cost between locations.
First pass
In Dijkstra’s algorithm, you first choose a starting vertex, since the algorithm needs a starting point to find a path to the rest of the nodes in the graph. Assume the starting vertex you pick is vertex A.
Second pass
Third pass
Fourth pass
Fifth pass
Sixth pass
Seventh pass
Eighth pass
You’ve covered every vertex except for H. H has two outgoing edges to G and F. However, there’s no path from A to H. This is why the whole column for H is null.
Implementation
Open up the starter playground for this chapter. This playground comes with an adjacency list graph and a priority queue, which you’ll use to implement Dijkstra’s algorithm.
class Dijkstra<T>(private val graph: AdjacencyList<T>){
// to be continued ...
}
class Visit<T>(val type: VisitType, val edge: Edge<T>? = null)
enum class VisitType {
START, // 1
EDGE // 2
}
Helper methods
Before building Dijkstra, let’s create some helper methods that will help create the algorithm.
Tracing back to the start
private fun route(destination: Vertex<T>, paths: HashMap<Vertex<T>, Visit<T>>): ArrayList<Edge<T>> {
var vertex = destination // 1
val path = arrayListOf<Edge<T>>() // 2
loop@ while (true) {
val visit = paths[vertex] ?: break
when(visit.type) {
VisitType.EDGE -> visit.edge?.let { // 3
path.add(it) // 4
vertex = it.source // 5
}
VisitType.START -> break@loop // 6
}
}
return path
}
Calculating total distance
private fun distance(destination: Vertex<T>, paths: HashMap<Vertex<T>, Visit<T>>): Double {
val path = route(destination, paths) // 1
return path.sumByDouble { it.weight ?: 0.0 }
}
Generating the shortest paths
After the distance method, add the following:
fun shortestPath(start: Vertex<T>): HashMap<Vertex<T>, Visit<T>> {
val paths: HashMap<Vertex<T>, Visit<T>> = HashMap()
paths[start] = Visit(VisitType.START) // 1
// 2
val distanceComparator = Comparator<Vertex<T>>({ first, second ->
(distance(second, paths) - distance(first, paths)).toInt()
})
// 3
val priorityQueue = ComparatorPriorityQueueImpl(distanceComparator)
// 4
priorityQueue.enqueue(start)
// to be continued ...
}
while (true) {
val vertex = priorityQueue.dequeue() ?: break // 1
val edges = graph.edges(vertex) // 2
edges.forEach {
val weight = it.weight ?: return@forEach // 3
if (paths[it.destination] == null
|| distance(vertex, paths) + weight < distance(it.destination, paths)) { //4
paths[it.destination] = Visit(VisitType.EDGE, it)
priorityQueue.enqueue(it.destination)
}
}
}
return paths
Finding a specific path
Add the following method to class Dijkstra:
fun shortestPath(destination: Vertex<T>, paths: HashMap<Vertex<T>,
Visit<T>>): ArrayList<Edge<T>> {
return route(destination, paths)
}
Trying out your code
val dijkstra = Dijkstra(graph)
val pathsFromA = dijkstra.shortestPath(a) // 1
val path = dijkstra.shortestPath(d, pathsFromA) // 2
path.forEach { // 3
println("${it.source.data} --|${it.weight ?: 0.0}|--> + " +
"${it.destination.data}")
}
E --|2.0|--> D
C --|1.0|--> E
G --|3.0|--> C
A --|1.0|--> G
Performance
In Dijkstra’s algorithm, you constructed your graph using an adjacency list. You used a min-priority queue to store vertices and extract the vertex with the minimum path. This has an overall performance of O(log V). This’s because the heap operations of extracting the minimum element or inserting an element both take O(log V).
Challenges
Challenge 1: Running Dijkstra’s
Given the following graph, step through Dijkstra’s algorithm to produce the shortest path to every other vertex starting from vertex A. Provide the final table of the paths as shown in the previous chapter.
Solution 1
Challenge 2: Collect Dijkstra’s data
Add a method to class Dijkstra that returns a dictionary of all the shortest paths to all vertices given a starting vertex. Here’s the method signature to get you started:
fun getAllShortestPath(source: Vertex<T>): HashMap<Vertex<T>, Visit<T>> {
val paths = HashMap<Vertex<T>, Visit<T>>()
// Implement solution here ...
return paths
}
Solution 2
This function is part of Dijkstra.kt. To get the shortest paths from the source vertex to every other vertex in the graph, do the following:
fun getAllShortestPath(source: Vertex<T>): HashMap<Vertex<T>, ArrayList<Edge<T>>> {
val paths = HashMap<Vertex<T>, ArrayList<Edge<T>>>() // 1
val pathsFromSource = shortestPath(source) // 2
graph.vertices.forEach { // 3
val path = shortestPath(it, pathsFromSource)
paths[it] = path
}
return paths // 4
}
Key points
- Dijkstra’s algorithm finds a path to the rest of the nodes given a starting vertex.
- This algorithm is useful for finding the shortest paths between different endpoints.
-
Visitstate is used to track the edges back to the start vertex. - The priority queue data structure helps to always return the vertex with the shortest path.
- Hence, it is a greedy algorithm!
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:
© 2021 Razeware LLC
