24.
Dijkstra’s Algorithm
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
Have you ever used a map 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 locations. The algorithm works with weighted graphs, both directed and undirected, to calculate the optimal routes from one vertex to all others in the graph.
Dijkstra’s algorithm is known as a greedy algorithm. That means it picks the most optimal path at every step along the way. It ignores solutions where some steps might have a higher intermediate cost but result in a lower overall cost for the entire path. Nevertheless, Dijkstra’s algorithm usually arrives at a pretty good solution very quickly.
Some applications of Dijkstra’s algorithm include:
- Communicable disease transmission: Discovering where biological diseases are spreading the fastest.
- Telephone networks: Routing calls to the highest-bandwidth paths available in the network.
- Mapping: Finding the shortest and fastest paths for travelers.
Note: On the off chance you’ve never seen the letters “jkstr” in combination and have no idea how you’d say that, “Dijkstra’s” is pronounced ˈdaɪkstrəz. And if you aren’t familiar with phonetic symbols, just combine the pronunciation of the words “dike” and “extras”.
How Dijkstra’s Algorithm Works
Imagine the directed graph below represents a road map. The vertices represent physical locations, and the edges represent one-way routes of a given cost between locations.
While edge weight can refer to the actual cost, it’s also commonly referred to as distance, which fits the paradigm of finding the shortest route. However, if you like the word cost, you can think of route finding algorithms as looking for the cheapest route.
Initialization
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.
First Pass
From vertex A, look at all of the outgoing edges. In this case, there are three:
Second Pass
In every round, Dijkstra’s algorithm always takes the shortest path. Of the distances 8, 9 and 1, the shortest is 1. That means column G with the 1 is the direction that Dijkstra will go:
Third Pass
In the next pass, you look at the next-lowest distance. The distance to B is 8, the distance to C is 4, and the distance to F is 9. That means C is the winner:
Fourth Pass
Of the unvisited vertices, which path has the lowest distance now? According to the table, E does, with a total distance of 5:
Fifth Pass
Next, you continue the search from B since it has the next-lowest distance:
Sixth Pass
Of the remaining unvisited vertices, D is closest to A with a distance of 7:
Seventh Pass
F is up next. It’s the only unvisited vertex that you have any information about:
Eighth Pass
You’ve covered every vertex except for H. H has one outgoing edge to G and one to F. However, there’s no path from A to H:
Implementation
Implementing Dijkstra’s algorithm brings together a lot of the previous concepts that you’ve learned in this book. Besides the basic data structures of lists, maps and sets, you’ll also use a priority queue, which itself is made from a min-heap, which is a partially sorted binary tree.
Creating Distance-Vertex Pairs
In the example diagrams above, you saw that the tables contained a distance-vertex pair for every destination vertex. You’ll implement a class for this now to make it easier to pass these values around.
import 'graph.dart';
class Pair<T> implements Comparable<Pair<T>> {
Pair(this.distance, [this.vertex]);
double distance;
Vertex<T>? vertex;
@override
int compareTo(Pair<T> other) {
if (distance == other.distance) return 0;
if (distance > other.distance) return 1;
return -1;
}
@override
String toString() => '($distance, $vertex)';
}
Setting Up a Class for Dijkstra’s Algorithm
Add the following class to dijkstra.dart:
class Dijkstra<E> {
Dijkstra(this.graph);
final Graph<E> graph;
}
Generating the Shortest Paths
Now you’re ready to start building the actual algorithm.
Initializing Dijkstra’s Algorithm
First, import the file with your priority queue data structure at the top of dijkstra.dart:
import 'priority_queue.dart';
Map<Vertex<E>, Pair<E>?> shortestPaths(Vertex<E> source) {
// 1
final queue = PriorityQueue<Pair<E>>(priority: Priority.min);
final visited = <Vertex<E>>{};
final paths = <Vertex<E>, Pair<E>?>{};
// 2
for (final vertex in graph.vertices) {
paths[vertex] = null;
}
// 3
queue.enqueue(Pair(0, source));
paths[source] = Pair(0);
visited.add(source);
// more to come
return paths;
}
Visiting a New Vertex
Continue your implementation of shortestPaths by replacing the // more to come comment with the following while loop. Each loop handles visiting a new vertex:
// 1
while (!queue.isEmpty) {
final current = queue.dequeue()!;
// 2
final savedDistance = paths[current.vertex]!.distance;
if (current.distance > savedDistance) continue;
// 3
visited.add(current.vertex!);
// more to come
}
Looping Over Outgoing Edges
You’re almost done. Now replace the // more to come comment inside the while loop with the following code. This for loop iterates over the outgoing edges of the current vertex:
for (final edge in graph.edges(current.vertex!)) {
final neighbor = edge.destination;
// 1
if (visited.contains(neighbor)) continue;
// 2
final weight = edge.weight ?? double.infinity;
final totalDistance = current.distance + weight;
// 3
final knownDistance = paths[neighbor]?.distance
?? double.infinity;
// 4
if (totalDistance < knownDistance) {
paths[neighbor] = Pair(totalDistance, current.vertex);
queue.enqueue(Pair(totalDistance, neighbor));
}
}
Trying it Out
Navigate to bin/starter.dart and replace the contents of the file with the following code:
import 'package:starter/dijkstra.dart';
import 'package:starter/graph.dart';
void main() {
final graph = AdjacencyList<String>();
final a = graph.createVertex('A');
final b = graph.createVertex('B');
final c = graph.createVertex('C');
final d = graph.createVertex('D');
final e = graph.createVertex('E');
final f = graph.createVertex('F');
final g = graph.createVertex('G');
final h = graph.createVertex('H');
graph.addEdge(a, b, weight: 8, edgeType: EdgeType.directed);
graph.addEdge(a, f, weight: 9, edgeType: EdgeType.directed);
graph.addEdge(a, g, weight: 1, edgeType: EdgeType.directed);
graph.addEdge(g, c, weight: 3, edgeType: EdgeType.directed);
graph.addEdge(c, b, weight: 3, edgeType: EdgeType.directed);
graph.addEdge(c, e, weight: 1, edgeType: EdgeType.directed);
graph.addEdge(e, b, weight: 1, edgeType: EdgeType.directed);
graph.addEdge(e, d, weight: 2, edgeType: EdgeType.directed);
graph.addEdge(b, e, weight: 1, edgeType: EdgeType.directed);
graph.addEdge(b, f, weight: 3, edgeType: EdgeType.directed);
graph.addEdge(f, a, weight: 2, edgeType: EdgeType.directed);
graph.addEdge(h, g, weight: 5, edgeType: EdgeType.directed);
graph.addEdge(h, f, weight: 2, edgeType: EdgeType.directed);
}
final dijkstra = Dijkstra(graph);
final allPaths = dijkstra.shortestPaths(a);
print(allPaths);
{A: (0.0, null), B: (6.0, E), C: (4.0, G), D: (7.0, E), E: (5.0, C), F: (9.0, A), G: (1.0, A), H: null}
Finding a Specific Path
The shortestPaths method found the shortest route to all of the other reachable vertices. Often you just want the shortest path to a single destination, though. You’ll add one more method to accomplish that.
List<Vertex<E>> shortestPath(
Vertex<E> source,
Vertex<E> destination, {
Map<Vertex<E>, Pair<E>?>? paths,
}) {
// 1
final allPaths = paths ?? shortestPaths(source);
// 2
if (!allPaths.containsKey(destination)) return [];
var current = destination;
final path = <Vertex<E>>[current];
// 3
while (current != source) {
final previous = allPaths[current]?.vertex;
if (previous == null) return [];
path.add(previous);
current = previous;
}
// 4
return path.reversed.toList();
}
Trying it Out
Open bin/starter.dart and add the following two lines at the end of main:
final path = dijkstra.shortestPath(a, d);
print(path);
[A, G, C, E, D]
Performance
When performing Dijkstra’s algorithm, you need to visit every edge. That means the time complexity is at least O(E). After visiting an edge, you add the destination vertex to a priority queue if the distance for this edge is shorter. However, in a worst-case scenario where every edge is shorter that the previous ones, you’d still have to enqueue a vertex for every edge. Since enqueuing and dequeuing with your heap-based priority queue has a logarithmic time complexity, this operation would be O(log E). Repeating that for every edge would thus be O(E log E).
Challenges
Here are a few challenges to help you practice your new knowledge about Dijkstra’s algorithm. As always, you can find the answers in the Challenge Solutions section at the back of the book as well as in the downloadable supplemental materials.
Challenge 1: Dijkstra Step-by-Step
Given the following graph, step through Dijkstra’s algorithm yourself to produce the shortest path to every other vertex starting from vertex A.
Challenge 2: Find All the Shortest Paths
Add an extension on Dijkstra that returns all the shortest paths in list form from a given starting vertex. Here’s the method signature to get you started:
Map<Vertex<E>, List<Vertex<E>>> shortestPathsLists(
Vertex<E> source,
)
Key Points
- Dijkstra’s algorithm finds the shortest path from a starting vertex to the rest of the vertices in a graph.
- The algorithm is greedy, meaning it chooses the shortest path at each step.
- The priority queue data structure helps to efficiently return the vertex with the shortest path.