Dijkstra's Algorithm

Introduction

As fun as it is to generate maze after maze, eventually, someone’s going to ask us how to actually solve these puzzles. Once or twice is fine, but the last thing we want to do is perpetually put pencil to paper and manually work out the solution to each one, case by case. We’d never have time for making more mazes! Since the computer has generated these, surely it can solve them, too, right?

You bet it can.

It turns out that we can choose from among an entire host of algorithms to solve mazes. Some, like the Pledge or Trémaux algorithms, are useful when we can’t see the entire maze. Others, like dead-end filling and the shortest-path algorithms, require a more omniscient view. In the scope of this course, we’ll concentrate on just one, the most all-rounder algorithm amongst the path-finding algorithms: Dijkstra’s.

However, it may not always be the best fit for the job. Other algorithms might solve some mazes faster or more efficiently, but Dijkstra’s algorithm has a lot going for it in spite of that. First, it’s not picky about the mazes we give it. Some algorithms only work on certain kinds of mazes, but Dijkstra’s will solve anything we apply it to. Second, the byproducts of Dijkstra’s algorithm will let us do some fun things, like increase the difficulty of our mazes or give us insight into their textures and the biases of the algorithms we’re using to generate them.

Who is "Dijkstra?"

Edsger Dijkstra (1930–2002) was a Dutch computer scientist. Aside from inventing his eponymous algorithm, he was active in many different areas within computer science, fields like formal verification and distributed computing. He also wrote many papers and articles, including a well-known letter from the late 1960s called “Go To Statement Considered Harmful.”

We’ll look at a simplified version of Dijkstra’s algorithm in this chapter, walking through it step by step, and then we’ll see how it’s implemented in code. We’ll also see some of these byproducts in action when we try to find longer paths through our mazes or color them to better visualize textures.

Dijkstra's shortest path algorithm

Dijkstra’s algorithm measures the shortest distance between some starting point (which we specify) and every other cell in the maze. In a nutshell, it works by flooding the maze, starting from the point we chose.

The version of the algorithm that follows is a bit simplified. The full algorithm can find the shortest path through any configuration of cells and passages, regardless of how those cells are connected. For now, the simplified version is all we need.

Dijkstra's algorithm explained and illustrated

The algorithm can be better understood by looking at the steps and the slides side by side.

1. The algorithm begins when it is given a starting point. This is usually the cell at the start of the path we want to find, like the entrance to the maze. The algorithm marks it with 0 because the path from that cell to itself is exactly zero cells long. Dijkstra’s hasn’t yet figured out the distance between this cell and every other cell in the grid, so it sets the distance for all other cells to blank or undefined. We use the northwest corner as the starting point.

2. Next, it looks at all of the unvisited (white, unnumbered) neighbors linked to that cell. We’ll call this set of cells the frontier. The algorithm assigns the value 1 to each of the cells in the frontier because they are all exactly one cell away from the starting point. The first cell has only a single accessible neighbor, so the new frontier set contains only that cell.

3. The algorithm does it all again for that cell in the new frontier set, the one just marked with 1. It visits each of the cell’s unvisited, accessible neighbors and makes the distance for each of them 2 because they are each one step farther from our starting point. Those cells now become the new frontier set.

4. The process repeats until every cell in the maze has been visited (that is, assigned a distance). What we're left with is a matrix showing the distance of every cell in the maze relative to that initial (starting) cell.

5. With this matrix, we can do a lot of really neat things, like finding the path from any cell in the maze back to the starting cell. To do so, we position ourselves at the endpoint of our path—we’ll call it the goal—and then look at neighboring cells. The cell whose distance is one less than the current cell will be the next stepping stone on our path. We make that cell the current cell, repeat the process until we reach the initial cell (the one with distance 0), and we’re done! The figure in the last slide below shows one such path if the southeast corner was selected as the goal.