Dijkstra在Java中的算法与障碍矩阵

Question

我试图实现Dijkstra的算法，以找到网格（x，y）中2点之间的最短路径，但问题是，我只能上移，下移，右边和左边。

我有一个ArrayList包含我需要传递的点的x和ys以及另一个网格上障碍点的ArrayList，我试图编写一个返回需要的运动的ArrayList的函数为了完成所有的路径。

例如：1,1,1,2,3,4,1 .. 1是右边2左边，3上来，最后是4下来。

您能否给我提供一些提示和/或示例。

Answer 1

首先，知道Dijkstra的算法是传统的加权图。它仍可以使用单位边缘（全部为1），但它可能不是最有效的解决方案。

无论哪种方式，无论使用哪种算法，都需要将网格视为图形。为此，请制作一组边。如果“无对角线”之外没有任何限制，那么您的边将成为每个点与其邻居之间，之下和旁边的连接。您可以通过遍历图上的边和点来对图进行操作。