JUNG中的树图（用于最短路径算法）

在询问关于最短路径算法（2D waypoint pathfinding: combinations of WPs to go from curLocation to targetLocation）的一些通用建议并询问更具体的实现（Shortest path algorithm (eg. Dijkstra's) for 500+ waypoints/nodes?）之后，我决定使用JUNG库（http://jung.sf.net/）。JUNG中的树图（用于最短路径算法）

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

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

这是正确的吗？现在，所有这些实现都将自己限制为稀疏树形图，但我必须创建一个相当密集的树形图。

那么，我应该用什么树图来实现我的目标？

来源

2011-03-09 Tom

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

JUNG框架2.x的GUI的示例使用从BFSDistanceLabeler需要一个通用超图最短路径算法。它应用基于BFS距离的计算，而不是基于边缘权重的距离计算。不过，这是一个广度优先搜索（BFS）算法。

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

最佳参考值I可以寻找其他JUNG的最短路径算法可以在这里找到（PDF）： www.grotto-networking.com/JUNG/JUNG2-Tutorial.pdf

来源

2011-03-10 07:28:31 eee

0123，如果我失去了一些东西，但这是如何回答JUNG树映射实现适用于密集而不是稀疏的树映射？ – Tom 2011-03-10 12:57:15

只要硬件和JVM能够处理大小，一个约1000个节点的列表在JUNG中就不是问题。我在我的JUNG实现中注意到了这个约束。考虑到您的意图是用于二维航点数据，为什么选择一棵树？您可以在JUNG通用图，超图或树类中指定自己的数据类型。尽管如此，它对树木（（定向，扎根）树）的支持有限，我还没有尝试过。如果你还没有看到JUNG常见问题解答：http://jung.sourceforge.net/faq.html – eee 2011-03-11 02:12:05

我认为一个图是一棵树。但你说得对，这是一个2D环境。我之前看过这个样本，但对我来说它确实没什么意义。例如，他们在哪里实际构造并填充图形？如果你可以在代码中给出一个小例子来说明在jung中的非gui最短路径实现，那将是很棒的。 – Tom 2011-03-11 10:43:21

JUNG中的树图（用于最短路径算法）

回答

相关问题