# Shortest path through a maze

I recently learned something fun: how to solve maze puzzles by using shortest path algorithms in graphs! First step is to convert the maze into a graph. Let me take this simple maze as an example.

(Pardon my awkward looking drawing. I can never seem to get these right.)

To convert this maze into a graph, we have find the vertices and edges. This is fairly easy once you imagine the maze to be made up of some small cells, like a mesh. Start numbering from any corner, and continue giving the consecutive cells the same number as long as there is just one way to go forward. When you reach a point where you have a choice, give different numbers to all those choices. Like how I just incremented 1 to 2 and 3 when there was a choice in the figure below. Do this until you have numbered all the cells.

Now these numbers represent the vertices of the graphs. If there are any two cells with different numbers adjacent to each other, add an edge between those two vertices. So this is the graph we’ll get:

In this case we want to get from 1 to 4 and there’s only one path 1-3-4, which is the solution. With a more complicated maze, the graph may have multiple possible paths and in that case shortest path algorithms can be used to find the optimal solution.