C编程:如何找到最短路径？

Question

想象一下,我有一个由36个顶点组成的6x6正方形(即每行6个顶点和每列6个顶点),看起来像这样:

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

每个顶点都与1,2,3或4个近邻点连接 - 所以我们基本上得到一个带有顶点和边的图.我的问题如下:我想要一个机器人通过那个"迷宫"的边缘,直到找到某个顶点放置某个物体.一旦找到该对象,就应该以最快的方式回到起点.

现在,我不太清楚如何实现这一点,所以我的问题是:在C中保存有关顶点和边的信息的最佳结构是什么？(邻接矩阵对我来说似乎效率低,因为36x36非常大).而且,使用这些信息,我怎样才能找到最快的方式？

Answer 1

您似乎每个顶点需要四位，来表示 { up, right, down, left } 中的任何一个都是“开放”方向，即有效移动。

因此，您总共需要：

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

保存所有连接数据。很难想象它的效率会比这高得多。