0

我正在使用 JGraphT 在 Java 中实现 Bellman Ford 最短路径算法。由于有一些边缘，应优先考虑，它们的边缘权重设置为-1。

例如：

A <-> B：10

A <-> C: 10

C <-> B：-1

B <-> D：10

所以在这种情况下，路径应该看起来像 A -> C -> B -> D。子路径 A->C->B 应该优先于 A->B。

现在问题来了：算法在 C 和 B 之间找到循环，因此 C->B 和 B->C 路径被多次添加（以减少总路径成本，因为 B<->C 的权重为负） .

现在的问题是：是否有可能避免这样的循环？我在 API 中没有找到任何选项。Graph 对象的 isAllowingLoops() 方法返回“false”。

你能给我一些提示吗？

提前致谢！

4

1 回答 1

0

如下构建图表将为您提供您正在寻找的路径：

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)]
于 2016-04-30T06:10:01.877 回答