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