java - 代表这种情况的想法

Question

我正在设计一个飞行模拟程序，并且正在寻找有关如何正确实现此类要求的想法。

请看下面我的照片。点代表位置。

这个想法是这样的，我想正确地创建一个数据结构来最好地代表java中的这种场景，这样

• 当我在第 1 点时，我离最后的第 8 点还有多远？

  • 点 2、3 和 5 与点 8 的距离相同
  • 从第 1 点，我可以遍历到第 3 点到第 6 点，然后是第 7 点，然后是第 8 点，这相当于 4 个步骤。

• 当我在第 0 点时

  • 我可以遍历到第 4 点，然后到第 5 点，然后到第 7 点，然后到达第 8 点，这也相当于 4 步。

我只是想帮助用户帮助他们找到不同的路线。

这可能吗？哪种 java 数据结构最适合这个要求？还有任何设计想法如何实现这一点？

抱歉，如果我的问题可能含糊不清，我只是想尽可能多地获取信息以正确处理此类要求。

Answer 1

您所拥有的是一个加权图，其中权重表示节点之间的距离（这很常见）。您可以自己轻松地实现它（这是一种很好的学习方式！），但是那里有很多 Java 源代码。

当然，这不是java数据结构。它只是一种数据结构（或概念），每个人、任何地方都可以使用。

一旦您实现了加权图，计算步数和距离就非常容易。

有大量关于这一切的文档，尤其是在Stackoverflow上。

Answer 2

这是一个最短路径问题，一个常见的图问题。表示数据的常用方法是邻接列表或矩阵：

邻接列表为每个节点保留所有 1 步可达目的地。这通常作为链接列表实现。如果您的图表相对稀疏（即每个节点的目的地很少），这是正确的选择。

邻接矩阵用于（非常）密集的图。基本上，您保留一个 NxN 值矩阵（权重/成本，或是/否布尔值）。然后，distances[i][j] 表示从 i 到 j 的成本。不可用弧的成本为 INF（或某个错误值）。

问题本身通常由Dijkstra 算法解决。