Geek asks and answers

C Programming: How to find the shortest path?

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

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

Each vertex is either connected with 1, 2, 3, or 4 close vertices, so we basically get a graph with vertices and edges. My problem is this: I want the robot to go through this “maze” of edges until it finds a specific object placed at some vertex. As soon as he discovers this object, he must return to the starting point using the fastest way back.

Now I'm not quite sure how to implement this, so my question is: what is the best structure to store information about these vertices and edges in C? (The adjacency matrix seems ineffective to me, since 36x36 is quite large). And using this information, how can I find a quick way to get back to the beginning?

+5
source share
2 answers

It seems you need four bits to the top to express that any of the {up, right, down, left} are "open" directions, i.e. valid for moving.

So, you will need a total of:

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

to save all connection data. It is hard to imagine that this is becoming much more effective than that.

+1
source

More articles:


All Articles