JGraphT避免循環（Bellman Ford）

Question

我正在使用JGraphT在Java中實現Bellman Ford最短路徑算法。 由於存在一些邊緣，因此應優先選擇邊緣權重爲-1。

例如：

甲< - > B：10

甲< - > C：10

Ç< - > B：-1

乙< - > d ：10

所以在這種情況下，路徑應該看起來像A→C→B→D。 子路徑A- > C-> B應優於A-> B。

現在問題是：算法找到C和B之間的循環，以便C→B和B→C路徑被添加幾次（以減少總路徑成本，因爲B < - > C是否定的）。

現在的問題：是否有可能避免這種循環？我在API中找不到任何選項。 Graph對象的isAllowingLoops（）方法返回「false」。

你能告訴我一些提示該怎麼做嗎？

在此先感謝！

Answer 1

構建如下圖會告訴你，你要尋找的路徑：

DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> g; 
g = new DefaultDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class); 

g.addVertex("a"); 
g.addVertex("b"); 
g.addVertex("c"); 
g.addVertex("d"); 

DefaultWeightedEdge edge1 = g.addEdge("a", "b"); 
g.setEdgeWeight(edge1, 10); 
DefaultWeightedEdge edge1a = g.addEdge("b", "a"); 
g.setEdgeWeight(edge1a, 10); 


DefaultWeightedEdge edge2 = g.addEdge("a", "c"); 
g.setEdgeWeight(edge2, 10); 
DefaultWeightedEdge edge2a = g.addEdge("c", "a"); 
g.setEdgeWeight(edge2a, 10); 


DefaultWeightedEdge edge3 = g.addEdge("b", "c"); 
g.setEdgeWeight(edge3, -1); 
DefaultWeightedEdge edge3a = g.addEdge("c", "b"); 
g.setEdgeWeight(edge3a, -1); 


DefaultWeightedEdge edge4 = g.addEdge("b", "d"); 
g.setEdgeWeight(edge4, 10); 
DefaultWeightedEdge edge4a = g.addEdge("d", "b"); 
g.setEdgeWeight(edge4a, 10); 


List<DefaultWeightedEdge> path = BellmanFordShortestPath.findPathBetween(g, "a", "d"); 
System.out.println(path); 

上面會輸出：

[(a : c), (c : b), (b : d)]