2

在询问了一些关于最短路径算法的一般建议（2D 航路点寻路：从 curLocation 到 targetLocation 的 WP 组合），然后询问更具体的实现（500 多个航路点/节点的最短路径算法（例如 Dijkstra 的）？）已决定使用 JUNG 库（http://jung.sf.net/）。

我现在的目标是通过使用点列表（大小〜1000）中的任意点组合来获得从点 A 到点 B 的最短路径，其中每个点都直接连接到 x 距离内的所有点。

为此，我需要设置一个树形图。我相信这是一个树图实现列表：http: //jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/class-use/Hypergraph.html#edu.uci.ics。 jung.algorithms.shortestpath

那是对的吗？现在，所有这些实现都仅限于稀疏树图，但我必须创建一个相当密集的树图。

那么，我应该在 JUNG 中使用什么树形图来实现我的目标？

4

1 回答 1

1

我认为您的主要目标可以通过 JUNG 实现，但恕我直言，您需要过滤给定的“x”距离（我的意思是所有可能的节点到节点组合）。但是，除了下面给出的示例之外，我没有使用 JUNG 的最短路径算法的经验。

JUNG Framework 2.x GUI 示例使用来自BFSDistanceLabeler的最短路径算法，该算法需要通用Hypergraph。它应用基于 BFS 距离的计算，而不是基于边缘权重的距离计算。不过，它是一种广度优先搜索 (BFS) 算法。

可以参考jung-samples-2.0.1.jar包edu.uci.ics.jung.samples下的源码ShortestPathDemo.class

我可以在此处找到有关其他 JUNG 最短路径算法的最佳参考（PDF）： www.groto-networking.com/JUNG/JUNG2-Tutorial.pdf

于 2011-03-10T07:28:31.710 回答