3

我想在有向（非循环）图中找到最长的路径。假设我知道起始节点 - 接收器。路径应该从这一点开始。我在想我可以将边的权重设置为-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) {

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

假设我想找到节点 nr 1（接收器）的最长路径。所以这个算法应该给我1-2-3-4-5-6。

4

2 回答 2

0

我正在寻找类似问题的答案，以从 Git repos 的 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
}
于 2020-05-02T21:20:15.557 回答
0

您可以使用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);
于 2019-10-29T14:49:37.687 回答