0

在实现我的 Dijkstra 算法时，我对如何初始化我的指针（边缘）类感到困惑。Node 类包含一个 Pointer 的 ArrayList，称为邻居，它们表示 Node 任意一侧的 4 个邻居。我的 Pointer 类将目标节点（它指向的位置）作为构造函数中的参数。它们都被添加到 36x25 二维节点数组中。

到目前为止，我正在使用 setNeighbors() 方法遍历在 36x25 网格上构建的每个节点，一旦所有节点都构建完成，它会根据每个可能的节点在网格中的相关性搜索多达 4 次（一个角落有 2 个邻居)，并在通过比较 (x,y) 坐标找到邻居后中断。

这个初始化过程对于我的目的来说太长了，所以我想知道是否有人可以向我展示一种更有效的初始化方式。

我有一个类节点：

import java.util.ArrayList;

public class Node implements Comparable<Node>
{
     public int x;
     public int y;
     public ArrayList<Pointer> neighbors = new ArrayList<Pointer>();
     public double minDistance = Double.POSITIVE_INFINITY;
     public Node previous;

     public Node(int xPos, int yPos) 
     { 
        x = xPos;
        y = yPos;
     }

     public int compareTo(Node other)
     {
        return Double.compare(minDistance, other.minDistance);
     }
}

还有一个类指针：

public class Pointer
{
     public final Node target;
     public final double weight = 1;
     public Pointer(Node targ)       
     { 
       target = targ;
     }
}
4

1 回答 1

0

好吧，您可以让网格表示类似于在 x 和 y 上都有下限和上限的方形网格，然后您可以创建一个递归方法，在该方法中在 (x,y) 处初始化一个节点，并且该初始化的节点将初始化它的北/west/south/east 邻居，如果这些节点 x,y 位置仍在网格内，否则你已经撞到了墙，你不能再在那个方向初始化。这里的问题是什么Pointer，它似乎是一个使事情复杂化的类。如果网格是方形的，你可以保持

Node north;
Node west
Node south
Node east

Node 类中的字段。

如果网格不是方形的，你仍然可以保持

List<Node> connectedTo
于 2013-11-07T02:14:21.513 回答