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.

Image

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

Image

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:

Image

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.

Advertisements

4 thoughts on “Shortest path through a maze

  1. I think this types of problem can be solved using union-find algorithm.
    I have seen your graph code in github those code I like those codes : ). would you please tell me why you choose C to write those code, I have written some code of graph in Cpp it seems to me more easy to implement graph in Cpp

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s