42. Dijkstra’s Algorithm

Written by Vincent Ngo

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 isolation. It misses solutions where some steps might cost more, but the overall cost is lower. Nevertheless, it usually arrives at a pretty good solution very quickly.

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:

1. Communicable disease transmission: Discover where biological diseases are spreading the fastest.
2. Telephone networks: Routing calls to highest-bandwidth paths available in the network.
3. Mapping: Finding the shortest and fastest paths for travelers.

Example

All the graphs you have looked at thus far have been undirected. 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 represent one-way paths of a given cost between locations.

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 outgoing edges. In this case, you have three edges:

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

The remainder of the vertices will be marked as nil since there is no direct path to them from A.

As you work through this example, the table on the right of the graph will represent the history, or record, of Dijkstra’s algorithm at each stage. Each pass of the algorithm will add a row to the table. The last row in the table will be the final output of the algorithm.

Second pass

In the next cycle, Dijkstra’s algorithm looks at the lowest-cost path you have thus far. A to G has the smallest cost of 1 and the shortest path to get to G. This path is marked with a dark fill in the output table.

Now, from the lowest-cost path, vertex G, look at all the outgoing edges. There is only one edge from G to C, and its total cost is 4. This is because the cost from A to G to C is 1 + 3 = 4.

Every value in the output table has two parts: the total cost to reach that vertex and the last neighbor on the path to that vertex. For example, the value 4 G in the column for vertex C means that the cost to reach C is 4, and the path to C goes through G. A value of nil indicates that no path has been discovered to that vertex.

Third pass

In the next cycle, you look at the next-lowest cost. According to the table, the path to C has the smallest cost, so that the search will continue from C. You fill column C because you’ve found the shortest path to get to C.

Look at all of C’s outgoing edges:

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

You’ve found a lower-cost path to B, so you replace the previous value for B.

Fourth pass

Now, in the next cycle, ask yourself what the next-lowest cost path is? According to the table, C to E has the smallest total cost of 5, so the search will continue from E.

You fill column E because you’ve found the shortest path. Vertex E has the following outgoing edges:

• E to C has a total cost of 5 + 8 = 13. Since you have found the shortest path to C already, disregard this path.
• E to D has a total cost of 5 + 2 = 7.
• E to B has a total cost of 5 + 1 = 6. According to the table, the current shortest path to B has a total cost of 7. You update the shortest path from E to B since it has a smaller cost of 6.

Fifth pass

Next, you continue the search from B.

B has these outgoing edges:

• B to E has a total cost of 6 + 1 = 7, but you’ve already found the shortest path to E, so disregard this path.
• B to F 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. You can disregard this path since it isn’t any shorter.

Sixth pass

In the next cycle, you continue the search from D.

However, D has no outgoing edges, so it’s a dead end. You record that you’ve found the shortest path to D and move on.

Seventh pass

F is next up.

F has one outgoing edge to A with a total cost of 9 + 2 = 11. You can disregard this edge since A is the starting vertex.

Eighth pass

You have covered every vertex except for H. H has two outgoing edges to G and F. However, there is no path from A to H. Because there is no path, the whole column for H is nil.

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

You can now check the final row for the shortest paths and their costs. For example, the output tells you the cost to get to D is 7. To find the path, you backtrack. Each column records the previous vertex the current vertex is connected to. You should get from D to E to C to G and finally back to A. Let’s look at how you can build this in code.

Implementation

Open up the starter playground for this chapter. This playground comes with an adjacency list graph and a priority queue, which you will use to implement Dijkstra’s algorithm.

The priority queue is used to store vertices that have not been visited. It’s a min-priority queue so that every time you dequeue a vertex, it gives you vertex with the current tentative shortest path.

Open up Dijkstra.swift and add the following:

public enum Visit<T: Hashable> {
  case start // 1
  case edge(Edge<T>) // 2
}

Here, you defined an enum named Visit. This type keeps track of two states:

1. The vertex is the starting vertex.
2. The vertex has an associated edge that leads to a path back to the starting vertex.

Now, define a class called Dijkstra. Add the following after the code you added above:

public class Dijkstra<T: Hashable> {

  public typealias Graph = AdjacencyList<T>
  let graph: Graph

  public init(graph: Graph) {
    self.graph = graph
  }
}

As in the previous chapter, Graph is defined as a type alias for AdjacencyList. You could, in the future, replace this with an adjacency matrix if needed.

Helper methods

Before building Dijkstra, let’s create some helper methods that will help create the algorithm.

Tracing back to the start

You need a mechanism to track the total weight from the current vertex back to the start vertex. To do this, you will keep track of a dictionary named paths that stores a Visit state for every vertex.

Add the following method to class Dijkstra:

private func route(to destination: Vertex<T>,
                   with paths: [Vertex<T> : Visit<T>]) -> [Edge<T>] {
  var vertex = destination // 1
  var path: [Edge<T>] = [] // 2

  while let visit = paths[vertex], case .edge(let edge) = visit { // 3
    path = [edge] + path // 4
    vertex = edge.source // 5
  }
  return path // 6
}

This method takes in the destination vertex along with a dictionary of existing paths, and it constructs a path that leads to the destination vertex. Going over the code:

1. Start at the destination vertex.

2. Create an array of edges to store the path.

3. As long as you have not reached the start case, continue to extract the next edge.

4. Add this edge to the path.

5. Set the current vertex to the edge’s source vertex. This assignment moves you closer to the start vertex.

6. Once the while loop reaches the start case, you have completed the path and return it.

Calculating total distance

Once you have the ability to construct a path from the destination back to the start vertex, you need a way to calculate the total weight for that path. Add the following method to class Dijkstra:

private func distance(to destination: Vertex<T>,
                      with paths: [Vertex<T> : Visit<T>]) -> Double {
  let path = route(to: destination, with: paths) // 1
  let distances = path.compactMap { $0.weight } // 2
  return distances.reduce(0.0, +) // 3
}

This method takes in the destination vertex and a dictionary of existing paths and returns the total weight. Going over the code:

1. Construct the path to the destination vertex.
2. compactMap removes all the nil weights values from the paths.
3. reduce sums the weights of all the edges.

Now that you have established the helper methods, you can implement Dijkstra’s algorithm.

Generating the shortest paths

After the distance method, add the following:

public func shortestPath(from start: Vertex<T>) -> [Vertex<T> : Visit<T>] {
  var paths: [Vertex<T> : Visit<T>] = [start: .start] // 1

  // 2
  var priorityQueue = PriorityQueue<Vertex<T>>(sort: {
    self.distance(to: $0, with: paths) <
    self.distance(to: $1, with: paths)
  })
  priorityQueue.enqueue(start) // 3

  // to be continued
}

This method takes in a start vertex and returns a dictionary of all the paths. Within the method you:

1. Define paths and initialize it with the start vertex.
2. Create a min-priority queue to store the vertices that must be visited. The sort closure uses the distance method you created to sort the vertices by their distance from the start vertex.
3. Enqueue the start vertex as the first vertex to visit.

Complete your implementation of shortestPath with:

while let vertex = priorityQueue.dequeue() { // 1
  for edge in graph.edges(from: vertex) { // 2
    guard let weight = edge.weight else { // 3
      continue
    }
    if paths[edge.destination] == nil ||
       distance(to: vertex, with: paths) + weight <
       distance(to: edge.destination, with: paths) { // 4
      paths[edge.destination] = .edge(edge)
      priorityQueue.enqueue(edge.destination)
    }
  }
}

return paths

Going over the code:

1. You continue Dijkstra’s algorithm to find the shortest paths until all the vertices have been visited. You know you are complete when the priority queue is empty.
2. For the current vertex, you go through all its neighboring edges.
3. You make sure the edge has a weight. If not, you move on to the next edge.
4. If the destination vertex has not been visited before or you’ve found a cheaper path, you update the path and add the neighboring vertex to the priority queue.

Once all the vertices have been visited, and the priority queue is empty, you return the dictionary of shortest paths to the start vertex.

Finding a specific path

Add the following method to class Dijkstra:

public func shortestPath(to destination: Vertex<T>,
                         paths: [Vertex<T> : Visit<T>]) -> [Edge<T>] {
  return route(to: destination, with: paths)
}

This method takes the destination vertex and the dictionary of shortest paths and returns the path to the destination vertex.

Trying out your code

Navigate to the main playground, and you will notice the graph above has been already constructed using an adjacency list—time to see Dijkstra’s algorithm in action.

Add the following code to the playground page:

let dijkstra = Dijkstra(graph: graph)
let pathsFromA = dijkstra.shortestPath(from: a) // 1
let path = dijkstra.shortestPath(to: d, paths: pathsFromA) // 2
for edge in path { // 3
  print("\(edge.source) --|\(edge.weight ?? 0.0)|--> \(edge.destination)")
}

Here, you create an instance of Dijkstra by passing in the graph network and do the following:

1. Calculate the shortest paths to all the vertices from the start vertex A.
2. Get the shortest path to D.
3. Print this path.

This outputs:

A --|1.0|--> G
G --|3.0|--> C
C --|1.0|--> E
E --|2.0|--> D

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 process has an overall time complexity of O(log V). The heap operations of extracting the minimum element or inserting an element both take O(log V) respectively.

If you recall from the breadth-first search chapter, it takes O(V + E) to traverse all the vertices and edges. Dijkstra’s algorithm is somewhat similar to breadth-first search because you have to explore all neighboring edges. This time, instead of going down to the next level, you use a min-priority queue to select a single vertex with the shortest distance to traverse down. That means it is O(1 + E) or simply O(E). So, combining the traversal with operations on the min-priority queue, it takes O(E log V) to perform Dijkstra’s algorithm.

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.
• Visit state is used to track the edges back to the start vertex.
• The priority queue data structure ensures returning the vertex with the shortest path.
• Because it chooses the shortest path at each step, it is said to be greedy!