如果我有一个通过 Java 中的 2D 数组迷宫类型的广度优先搜索返回的点列表，我如何才能找到该点列表中的最短路径？
例如，如果我的潜在目标点是 [2, 4] 和 [6, 0]，并且我有一个通往每个目标点的点列表，我如何找出哪条路线最短？
我想我可能必须使用 Djikstra 算法或其他算法，但我不确定。
非常感谢
最佳答案
您可以在此处使用 Dijkstra 算法。给定您提到的数组迷宫，第一步是获取迷宫中 2 个相邻节点之间的所有边以及边成本。对于节点，您需要知道每个节点是否已被访问，以及访问该节点的当前成本。
现在，如果您不关心获得最短路径，则可能不需要 Dijkstra。相反，您可以使用 DP/递归方法来获取从源坐标到目标坐标的可能路径。如果您想查看 Dijkstra 的实现，this是我写的。为了获得最短路径，您显然需要节点之间的距离。
为了找到两点之间的路径，我建议类似 this执行。它包括 DP 和递归实现，并比较两者的运行时间(对于大型数据集，递归可能需要很长时间才能运行)。
我觉得这些应该足以让你开始了。如果您需要其他信息，请告诉我。
关于java - 从点列表中查找最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35443077/