最短路径算法：从一个点到相邻的点均匀的距离 [英] Shortest Path Algorithm : Uniform distances from one point to adjacent points

问题描述

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

I am trying to develop an algorithm wherein I have a Location Class. In each class, I create a list of its adjacent Locations. I want to know, how can I get the shortest path from one Location to another. I am trying to look for different algorithms but it seems that they doesn't answer my problem.

例如，我有一个A点，我要到B点，

For example, I have a point A and I want to go to point B,

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

我的想法是，如果B是A的相邻位置的列表，然后就是最短路径。如果不是，它应该寻找A的相邻位置的相邻位置，但我不知道如何在code实现这个，或者如果它是一个很好的算法。我也想显示一个 - C - 的F - 的K - B为路由的最短路径。我也发展得如此之我有点有限的，我可以使用的Java功能这一项就J2ME。 如果有人能帮助我，这将是更AP preciated。谢谢

My idea for this is if B is in the List of adjacent locations of A, then that is the shortest path. If not, it should search the adjacent locations of the adjacent locations of A. But I do not know how to implement this in code or if it is a good algorithm. I also want to display A - C - F - K - B as the route for the shortest path. I am also developing this one on j2me so I am a bit limited on the java features that I can use. If anyone can help me, it will be much appreciated. Thanks

推荐答案

您是在正确的轨道上。你描述的是 BFS 的开始。 BFS是最短路径算法被两个最佳的[找到最短路径]和完整 [总能找到，如果一个存在的路径]为加权图 - 所以它可能是正确的选择。

You are on the right track. What you describe is the start of BFS. BFS is a shortest-path algorithm that is both optimal [finds the shortest path] and complete [always finds a path if one exist] for unweighted graph - so it is probably the right choice.

BFS工程图。在这里你的图是 G =（V，E），使得 V = {所有地点} [节点/顶点/位置]和 E = {（U，V），（V，U）| u和v是邻居} [边缘/链路/邻居]

BFS works on graphs. In here your graph is G = (V,E) such that V = {all locations} [the nodes/vertices/locations] and E = {(u,v),(v,u) | u and v are neighbors} [the edges/links/neighbors]

BFS的想法是simpilar到你的建议是什么：首先检查起始节点也是目标。然后检查开始节点的邻居之一是目标，然后搜索自己的邻居......

The idea of BFS is simpilar to what you are suggesting: first check if the starting node is also the target. Then check if one of the neighbors of the starting node is the target, then search for their neighbors....

关于获得从BFS的实际路径：看看这个帖子。
的想法是要保持地图 - 为每个节点[位置] - 在地图上会显示你是如何到达那里？哪一个节点发现的呢？在BFS完成后 - 遵循目标映射到源，你得到的实际路径[逆转的。所提供的链接提供了有关这个想法的更多细节。

Regarding getting the actual path from BFS: have a look at this post.
The idea is to maintain a map - for each node [location] - the map will indicate how did you get there? which node discovered it? After the BFS finished - follow the map from target to source, and you get the actual path [reversed of course]. The link provided gives more details about this idea.

这篇关于最短路径算法：从一个点到相邻的点均匀的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！