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)]