Mazes for Programmers

Dijkstra’s 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 at that point we chose. The longer it takes the flood to reach a cell, the farther that cell is from our starting point.

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

The algorithm begins when ...