java - JUNG 中的 TreeMap (用于最短路径算法)

Question

在询问了关于最短路径算法的一些一般性建议 (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/)。

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

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

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

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

Answer 1

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

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

您可以引用jung-samples-2.0.1中package edu.uci.ics.jung.samples下的源码ShortestPathDemo.class。 jar

我能找到的其他 JUNG 最短路径算法的最佳引用资料可在此处找到 (PDF): www.grotto-networking.com/JUNG/JUNG2-Tutorial.pdf