23 Dijkstra’s Algorithm¶

Have you ever used a 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 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.

39282113185231HGCEBFAD

While edge weight can refer to the actual cost, it’s also commonly referred to as distance, which fits with 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.

You’ll use a table to keep track of the shortest routes from A to the other vertices. In the beginning, you don’t know anything, so fill in the table with nullvalues:

Start AnullnullnullnullnullnullnullBCDEFGH

As you work through this example, you’ll use each cell of the table to save two pieces of information:

The shortest known distance from A to this vertex.
The previous vertex in the path.

First Pass¶

From vertex A, look at all of the outgoing edges. In this case, there are three:

A to B has a distance of 8.
A to F has a distance of 9.
A to G has a distance of 1.

3221131852AHCEDFG1983B

Since you know the distance of traveling from A to these three vertices, write the values in the table:

Start Anullnullnullnull8ABCDEFGH9A1A

You can see in the first cell that the distance from A to column B is 8. Below the 8 you also write A. This means that the previous vertex on the path to B is A. You’ll update both the distance and the previous vertex if you find a better path to B in the future. Columns F and G follow the same pattern. The other vertices are still null since there’s no known path to them from A yet.

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:

Start Anullnullnullnull8ABCDEFGH9A1A

So the next step is to visit G:

3221131852AGHCEDF1983B

Now, look for G’s outgoing edges. It only has one, which goes to C, and the distance is 3. That means the total distance of the A to C path is 1 + 3 = 4. So write 4and G in the C column. Again, the reason you write G is that G is the previous vertex on this path before reaching C:

Start Anullnullnull8ABCDEFGH9A1A4G

The filled-in vertices, both in the table and in the graph, are the ones you’ve visited. You already know the shortest route’s to these vertices, so you don’t need to check them anymore.

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:

Start Anullnullnull8ABCDEFGH9A1A4G

So now you visit C:

3221131852AGHEDF1983BC

Look at all of C’s outgoing edges and add up the total cost it would take to get there from A:

C to E has a total cost of 4 + 1 = 5.
C to B has a total cost of 4 + 3 = 7.

It’s actually cheaper to take this route to B than it was to go directly from A to B. Because of that, update the B column with a new value of 7 by way of vertex C. Also fill in the E column since you know a route there now:

Start Anullnull7C5CBCDEFGH9A1A4G

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:

Start Anullnull7C5CBCDEFGH9A1A4G

Visit E and check its outgoing vertices. You’ve already visited C so you can ignore that one. However, B and D are still unvisited:

3221131852AGHDF1983BCE

These are the distances:

E to D has a total distance of 5 + 2 = 7.
E to B has a total distance of 5 + 1 = 6.

You didn’t know about D before, so you can fill in that column in the table. Also, when going to B, the path through E is even better than it was through C, so you can update the B column as well:

Start Anull6E7EBCDEFGH9A1A4G5C

Fifth Pass¶

Next, you continue the search from B since it has the next-lowest distance:

Start Anull6E7EBCDEFGH9A1A4G5C

Visit B and observe its edges:

3221131852AHCEDBFG1983

Of B‘s neighbors, the only one you haven’t visited yet is F. This has a total cost of 6 + 3 = 9. From the table, you can tell that the current path to F from A also costs 9. So, you can disregard this path since it isn’t any shorter:

Start Anull7EBCDEFGH9A1A4G6E5C

Sixth Pass¶

Of the remaining unvisited vertices, D is closest to A with a distance of 7:

Start Anull7EBCDEFGH9A1A4G6E5C

In this pass, continue the traversal from D:

3221131852AHCEDBFG1983

However, D has no outgoing edges, so it’s a dead end. You can just move on.

Seventh Pass¶

F is up next. It’s the only unvisited vertex that you have any information about:

Start AnullBCDEFGH9A1A4G6E5C7E

So visit F and observe its outgoing edges:

3221131852AHCEDBFG1983

F has one outgoing edge to A, but you can disregard this edge since A is the starting vertex. You’ve already visited it.

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:

3221131852AHCEDBFG1983

Because there’s no path, the column for H is null:

Start AnullBCDEFGH1A4G6E5C7E9A

This step completes Dijkstra’s algorithm since all the vertices that can be visited have been visited!

You can now check the table for the shortest paths and their distances. For example, the output tells you the distance you have to travel to get to D is 7. To find the path, you backtrack. Each column in the table records the previous vertex that the current vertex is connected to. For example, to find the path to D, you start at D and backtrack. D points to E, which points to C, which points to G, which points to A, the starting vertex. So the path is A-G-C-E-D:

3221131852AHCEDBFGStart Anull1A9A5C7E4G6EBCDEFGH1983Backtrack from D to A

It’s time to express these ideas in code now.

Implementation¶

The implementation of 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.

Open up the starter project for this chapter. The lib folder comes with an adjacency list graph and a priority queue.

You’ll use the priority queue to store the vertices that haven’t been visited. The queue uses a min-priority heap, which will allow you to dequeue the shortest known path in every pass.

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.

Create a new file in lib named dijkstra.dart and add the following code to it:

import 'graph.dart';

class Pair<T> extends 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)';
}

Pair extends Comparable because Dijkstra’s algorithm hands the distance-vertex pairs to a priority queue. The internal heap requires comparable elements so that it can sort them. The comparison here is performed solely on the distance. Dijkstra will be on the lookout for the shortest distances.

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;
}

Dijkstra allows you to pass in any graph that implements the Graph interface.

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';

Then add the following method to Dijkstra:

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;
}

This method takes in a source vertex and returns a map of all the paths. You begin the algorithm with the following content:

There are three data structures to help you out. The priority queue queue will allow you to visit the shortest route next in each pass. The setvisited isn’t strictly necessary, but using it will prevent you from unnecessarily checking vertices that you’ve already visited before. Finally, you’ll use the map paths to store the distance and previous vertex information for every vertex in the graph. Building paths is what this method is all about.
Initialize every vertex in the graph with a null distance-vertex pair.
Initialize the algorithm with the source vertex. This is where the search will start from, so the distance to this vertex is zero. queue holds the currentvertex, while paths stores a reference to the previous vertex. Since the source vertex doesn’t have a previous vertex, using Pair(0) causes the previous vertex to default to null.

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
}

This is how Dijkstra’s algorithm works here:

The queue holds the vertices that are known but haven’t been visited yet. As long as the queue isn’t empty, you’re not done exploring!
Later on, you’ll decrease the distances of certain paths as you find shorter routes. However, if you update the distance in paths, you should really update the same distance in queue. The problem is, your priority queue doesn’t have a way to do that. Don’t forget that the internal heap needs to maintain its min-heap property. Instead of implementing any new features in the priority queue, though, you’ll just add the same vertex again with a new distance. When the old, obsolete distance-vertex pair comes through, the code at // 2 will ignore it.
Add the current vertex to the visited set so that you can skip over it later. You already know the shortest route to this vertex.

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));
  }
}

Here’s what’s happening:

If you’ve previously visited the destination vertex, then ignore it and go on.
Find the total distance from the source to the neighboring vertex.
Compare the known distance to that vertex with the new total that you just calculated. Newly discovered vertices will get a default distance of infinity.
If you’ve found a shorter route this time around, then update paths and enqueue this vertex for visiting later. No worries if the same vertex is already enqueued. You’ll discard the obsolete one when it shows up.

Once all the discoverable vertices have been visited and the priority queue is empty, you return the map of the shortest paths. Dijkstra’s algorithm is complete.

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);
}

This recreates the graph that you saw in the example at the beginning of the chapter:

39282113185231HGCEBFAD

Now add the following code at the end of main:

final dijkstra = Dijkstra(graph);
final allPaths = dijkstra.shortestPaths(a);
print(allPaths);

Run that and you should see the following output:

{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}

This matches the results that the example described earlier.

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.

Return to lib/dijkstra.dart and add the following method to Dijkstra:

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();
}

After providing the source and destinations vertices to this method, here’s what happens:

You find all of the paths. Providing paths as an argument is an optimization if you need to call shortestPath multiple times on the same graph. No need to recalculate Dijkstra’s algorithm over and over.
Ensure that a path actually exists.
Build the path by working backward from the destination.
Since you built the list by starting from the back, you need to reverse the list before returning it.

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

Run your code again and you should see the ordered list of vertices showing the shortest path from A to D:

[A, G, C, E, D]

Just like in the example!

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

What about when you visited all of the vertices at the beginning of the algorithm to set the paths to null? That operation was O(V), so you could say the overall time complexity is O(V + E log E). However, you can assume that for a connected graph, V will be less than or approximately equal to E. That means you can replace O(V + E log E) with O(E + E log E). You can rearrange that as O(E × (1 + log E)). Then drop the 1 to again leave you with O(E log E). Remember that Big O notation is just a generalized way to talk about the complexity of an algorithm as the number of components increases. Constant values can be ignored.

Note

Special thanks to bradfieldcs.com for inspiration on the algorithm used in this chapter and to Google Engineer David Eisenstat on Stack Overflow for help analyzing the complexity. See the following links for details: https://bradfieldcs.com/algos/graphs/dijkstras-algorithm https://stackoverflow.com/a/70436868

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.

218211292BDECA

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.