C Programming: How to find the shortest path?

Question

Imagine I have a 6x6 square consisting of 36 vertexes (i.e. 6 vertexes per row and 6 vertexes per column), looks something like this:

•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •

Every vertex is either connected with 1, 2, 3 or 4 close-by vertexes - so we basically get a graph with vertexes and edges. My problem is the following: I want a robot to get through that 'maze' of edges until it finds a certain object placed on some vertex. As soon as it has found that object, it should return to its starting point, using the quickest way back.

Now, I'm not quite sure how to realize this, so my question is: What is the best structure to save information about those vertexes and edges in C? (An adjacency matrix seems inefficient to me as 36x36 is quite large). And, using this information, how can I find the quickest way back to the start?

Answer 1

You seem to need four bits per vertex, to express that any of { up, right, down, left } are "open" directions, i.e. valid to move in.

So, you would need a grand total of:

6 * 6
----- = 18 bytes
  2

to save all of your connectivity data. It's hard to imagine it getting a lot more efficient than that.

Answer 2

I would recommend you look into the A* algorithm which is often used in Pathfinding solutions.

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html