最短路径算法:从一个点到相邻点的均匀距离

Question

我正在尝试开发一种算法,其中我有一个位置类.在每个类中,我创建一个相邻位置的列表.我想知道,我怎样才能获得从一个位置到另一个位置的最短路径.我试图寻找不同的算法,但似乎他们没有回答我的问题.

例如,我有一个A点,我想去B点,

A - - C - - H - - J
      |
      F- - K- -B 

我的想法是,如果B位于A的相邻位置列表中,那么这是最短路径.如果没有,它应该搜索A的相邻位置的相邻位置.但是我不知道如何在代码中实现它或者它是一个好的算法.我还想显示A - C - F - K - B作为最短路径的路线.我也在j2me上开发这个,所以我对我可以使用的java功能有点限制.如果有人可以帮助我,我将不胜感激.谢谢

Answer 1

你走在正确的轨道上.你所描述的是BFS的开始.BFS是一种最短路径算法,对于未加权的图形而言,它是最优的 [找到最短路径]并且完成 [总是找到一条存在的路径] - 因此它可能是正确的选择.

BFS适用于图表.在这里你的图是G = (V,E)这样V = {all locations} [节点/顶点/位置]和E = {(u,v),(v,u) | u and v are neighbors}[边缘/链接/邻居]

BFS的想法与您的建议完全相同:首先检查起始节点是否也是目标.然后检查起始节点的一个邻居是否是目标,然后搜索他们的邻居....

关于从BFS 获取实际路径:看看这篇文章.
我们的想法是维护一张地图 - 对于每个节点[位置] - 地图将指示你是如何到达那里的？哪个节点发现了它？BFS完成后 - 按照从目标到源的地图,然后获得实际路径[逆转当然].提供的链接提供了有关此想法的更多详细信息