使用JGrapht找到有向边权图中的负周期

是否可以使用JGrapht在有向边权图中找到负周期？我浏览过Javadocs，发现我可以使用CycleDetector来检测周期，但不是特别的负周期。 CycleDetector找到周期，但是不知道如何以其他方式探索它们，却无法判断它们是否为负值。谢谢！使用JGrapht找到有向边权图中的负周期

来源

2016-08-03 Julian A.

一般而言，您可以使用BellmanFordShortestPath检查图表中的负循环，尽管不存在最短路径只会告诉您是否至少存在一个负循环。我没有正确的看看JgraphT中的BellmanFordShortestPath实现，所以我不能为你提供代码。

除此之外，在https://cs.stackexchange.com/questions/6919/getting-negative-cycle-using-bellman-ford有一个整洁的纸张链接。的有效链接的文件应该是：

https://www.semanticscholar.org/paper/Negative-Weight-Cycle-Algorithms-Huang/dc1391024d74f736aa7a9c24191a35e822589516/pdf

所以，如果一切都失败了，你至少可以实现一个工作算法本身，使用像DefaultDirectedWeightedGraph

来源

2016-08-05 11:41:40

我已经为我参加的课程编写了一个Bellman-Ford的实现。但我想要生成一些随机图，并将我的实现结果与能够专门检测负循环的其他实现进行比较。为此，我想我可以使用其他人的Bellman-Ford实现，或者自己写一些非Bellman-Ford的替代方案。 –

一个JgraphT图你可以尝试使用BellmanFordShortestPath，但是如果您查找从一个顶点到它自己的路径，则它不会找到循环，因为每个顶点都通过权重0隐式连接到它自己。

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

... 

BellmanFordShortestPath<String, DefaultWeightedEdge> algorithm = new BellmanFordShortestPath(graph); 

GraphPath<String, DefaultWeightedEdge> path = algorithm.getPath(node1, node1); 

int length = path.getLength(); // returns 0 
double weight = path.getWeight(); // returns 0.0

我能找到的最好的是org.jgrapht.alg.cycle的算法，给你所有周期，那么你必须计算周期周围的路径的总重量。

private boolean hasNegativeLoop(DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> graph){ 
    SzwarcfiterLauerSimpleCycles<String, DefaultWeightedEdge> cycleDetector = new SzwarcfiterLauerSimpleCycles<>(graph); 

    List<List<String>> cycles = cycleDetector.findSimpleCycles(); 

    for (List<String> cycle : cycles){ 
     double cycleWeight = getCycleWeight(graph, cycle); 

     if(cycleWeight < 0) return true; 
    } 

    return false; 
} 

private double getCycleWeight(DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> graph, List<String> cycle) { 
    double totalWeight = 0; 

    for(int i = 1; i < cycle.size(); i++){ 
     double weight = graph.getEdgeWeight(graph.getEdge(cycle.get(i-1), cycle.get(i))); 

     totalWeight += weight; 
    } 

    double weightBackToStart = graph.getEdgeWeight(graph.getEdge(cycle.get(cycle.size()-1), cycle.get(0))); 

    return totalWeight + weightBackToStart; 
}

与贝尔曼福特负循环检测相比，这样做效率更低，但可以作为实施的参考。

来源

2017-01-24 12:52:57

使用JGrapht找到有向边权图中的负周期

回答

相关问题