java - 用 Java 实现 Dijkstra 算法

Question

我已经对此进行了大量阅读，并且知道有关 Java 中该算法的讨论并不频繁。我在 Java 中实现 Dijkstra 算法的问题很简单，就是我不确定如何准备数据。

我在数组中有一组坐标，在矩阵中有一组 1 和 0，表示坐标表示的点之间是否存在路径。我的问题是，如何呈现这些信息，以便我可以使用 Dijkstra 搜索最佳路径？我见过很多人创建一个“Node”类，但他们似乎从未在该 Node 中存储坐标。是否有一些标准化的方法来创建这种结构(我想这是一个图表？)，我只是缺少？

如有任何帮助，我们将不胜感激。

Answer 1

有两个主要选项: 1. 您可以使用邻接矩阵，其中行和列代表节点。值矩阵[x, y]必须是从x到y的权重(例如距离/成本等)。您可以使用欧几里德距离从坐标数组中计算这些值； 2.您可以实现几个类(Node、Edge - 或者只是具有到另一个节点的内部映射的节点，并将权重作为映射值) - 它确实是一个图。