jgrapht库中有向无环图的最长路径

Question

我希望找到有向（无环）图中的最长路径。假设我知道起始节点-汇点。路径应从此点开始。 我考虑将边的权重设置为-1。有许多查找所有最短路径的方法，但必须通过结束点。是否可能获得最短路径（无论结束节点如何）？

DirectedAcyclicGraph graph = new DirectedAcyclicGraph<Integer, DefaultEdge>(DefaultEdge.class);
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
graph.addVertex(5);
graph.addVertex(6);
graph.addVertex(7);
graph.addVertex(8);
try {
    graph.addDagEdge(1, 2);
    graph.addDagEdge(2, 3);
    graph.addDagEdge(3, 4);
    graph.addDagEdge(5, 6);
graph.addDagEdge(2, 7);
graph.addDagEdge(7, 8);
} catch(Exception e) {

}
//????????????????

假设我想要找到节点1（汇点）的最长路径。这个算法应该给我返回1-2-3-4-5-6。

- peter robens

Answer 1

我在寻找一个类似的问题的答案，该问题是如何从一组Git存储库的DAG中计算Jenkins的并行构建分组。为了解决这个问题，我应用了这里和这里描述的算法。下面的代码是用Groovy编写的，所以你需要将其转换为Java。结果是一个顶点到它们各自的最大深度的映射。从那里，你可以得到单个最大值。如果你想知道图中特定顶点的最大深度，你可以首先将图修剪成以你所需的源顶点为根的子图，然后在子图上运行下面的方法。

def calcDepths(g) {    

    Map<String, Integer> vertexToDepthMap = new HashMap<>()

    Iterator<String> iterator = new TopologicalOrderIterator<String, DefaultEdge>(g)
    iterator.each { v ->

        Set<String> predecessors = Graphs.predecessorListOf(g, v).toSet()
        Integer maxPredecessorDepth = -1
        predecessors.each { predecessor ->

            maxPredecessorDepth = Math.max(maxPredecessorDepth, vertexToDepthMap.get(predecessor))
        }

        vertexToDepthMap.put(v, maxPredecessorDepth + 1)
    }

    return vertexToDepthMap
}

- John Michelau

Answer 2

您可以使用AllDirectedPaths算法来解决所有路径问题，将结果按照路径长度的倒序排序并获取第一个：

    AllDirectedPaths<String, DefaultEdge> paths = new AllDirectedPaths<String, DefaultEdge>(graph);
    GraphPath<String, DefaultEdge> longestPath = paths.getAllPaths(source, target, true, null)
        .stream()
        .sorted((GraphPath<String, DefaultEdge> path1, GraphPath<String, DefaultEdge> path2)-> new Integer(path2.getLength()).compareTo(path1.getLength()))
        .findFirst().get();
    System.out.println(longestPath.getLength() +  " " + longestPath);

- Gonzalo Gómez García

---

这让我感到困扰，因为对于大型图形来说效率非常低下... - Arthur Attout

是的，这个解决方案只适用于深度较短的图。 - Gonzalo Gómez García