2

好的，我是 Java 新手，我问这个问题是因为我确信有更好的简单方法来处理这个问题，更有经验的人可能会给我一些指示。

我有一张城市图，它们之间的路径长度。我正在尝试使用 Java 构建一个算法，从起始城市到目的地城市，找到最短路径。每个城市都会有一个名称和地图坐标。更具体地说，我将使用 A* 算法，但这（可能）对我的问题并不重要。

我的问题是我试图找出一种用长度表示节点和它们之间的路径的好方法。

我能想到的最简单的方法是创建一个巨大的二维方形数组，每个城市由一个索引表示，其中连接的城市可以通过它们在数组中的相交位置来表示。我为每个城市分配了一个索引#。在数组值中，0 会去没有连接的地方，距离会去有连接的地方。

我还将有一个带有“索引”属性的城市子类，其索引值在数组中。这样做的缺点是要找出哪些城市有连接，必须有额外的步骤来查找数组中的城市索引，并且还必须查找哪个连接城市有连接索引。

有没有更好的方法来表示这一点？

4

2 回答 2

2

另一种方法是使用 Node 结构来存储所有指向相邻节点的指针。

例如

如果你的数据结构中有这样的东西

   A   B   C

A  /   0   1

B  0   /   1

C  1   1   /

在新结构中

A: [C]
B: [C]
C: [AB]

与您的二维数组方法相比，这种方法需要更长的时间来检查两个节点是否连接，但使用的空间更小

于 2012-06-08T04:19:14.953 回答
1

考虑...

class Node {
  List<Link> link;
  String cityName;
}
class Link {
  Node destinationCity;
  Long distance;
}
于 2012-06-08T05:06:14.850 回答