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中的樹圖（用於最短路徑算法）

回答

相關問題