24. Dijkstra’s Algorithm

Written by Jonathan Sande

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:

1. Communicable disease transmission: Discovering where biological diseases are spreading the fastest.
2. Telephone networks: Routing calls to the highest-bandwidth paths available in the network.
3. 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.

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 null values:

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

1. The shortest known distance from A to this vertex.
2. 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.

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

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 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:

So the next step is to visit G:

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 4 and G in the C column. Again, the reason you write G is that G is the previous vertex on this path before reaching C:

The filled-in vertices, both in the table and in the graph, are the ones you’ve visited. You already know the shortest routes 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:

So now you visit C:

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:

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:

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:

These are the distances from A:

• 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:

Fifth Pass

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

Visit B and observe its edges:

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:

Sixth Pass

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

In this pass, continue the traversal from D:

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:

So visit F and observe its outgoing edges:

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:

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

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:

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

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.

Open up the starter project for this chapter. The lib folder has 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 allows 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> 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)';
}

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:

1. 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 set visited 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.

2. Initialize every vertex in the graph with a null distance-vertex pair.

3. 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 current vertex, 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:

1. 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!
2. 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.
3. Add the current vertex to the visited set so 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:

1. If you’ve previously visited the destination vertex, then ignore it and go on.
2. Find the total distance from the source to the neighboring vertex.
3. Compare the known distance to that vertex with the new total you just calculated. Newly discovered vertices will get a default distance of infinity.
4. 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:

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:

1. 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.
2. Ensure that a path actually exists.
3. Build the path by working backwards from the destination.
4. 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.

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.