使用TraversalDescription查找所有最短路径

我需要使用TraversalDescription查找两个节点之间的所有最短路径。使用TraversalDescription查找所有最短路径

（我不能用暗号程序allShortestPaths（），因为我需要一些具体的评估以后添加： Neo4J: shortest paths with specific relation types sequence constrain ）

Node startNode = ...; 
Node endNode = ...; 
TraversalDescription td = graphDb.traversalDescription() 
    .breadthFirst() 
    .evaluator(Evaluators.endNodeIs(Evaluation.INCLUDE_AND_PRUNE, 
            Evaluation.EXCLUDE_AND_CONTINUE, 
            endNode)); 

for (Path path : td.traverse(startNode)) { 
    // only 1 path found 
}

我只得到1路。

但是，如果我运行的Cypher查询：

MATCH (startNode{...}) 
MATCH (endNode{...}) 
MATCH path = allShortestPaths((startNode)-[*]-(endNode)) 
RETURN path;

找到了相同的StartNode和终端节点多于一个路径。

如何设置TraversalDescription来查找所有（最短）路径？

来源

2017-04-07 Kit

几点建议：

看看shortestpath和allshortestpths如何actually implemented。您可能可以修改代码的副本以执行您想要的操作。根本不使用 TraversaDescription。
还有一个“实验”BidirectionalTraversalDescription，似乎更接近shortestpath和实现的设计。您也许可以使用它。

来源

2017-04-07 20:45:46 cybersam

谢谢你的建议。我试图使用'BidirectionalTraversalDescription'，甚至得到了结果，但遭受了显着的性能问题： http://stackoverflow.com/questions/43526585/neo4j-set-up-bidirectionaltraversaldescription-for-shortest-paths-search – Kit

问题的根源是“修剪”。当您使用endPoint找到第一条路径时，停止遍历。所以试试这个：

TraversalDescription td = graphDb.traversalDescription() 
    .breadthFirst() 
    .evaluator(Evaluators.endNodeIs(Evaluation.INCLUDE_AND_CONTINUE, 
            Evaluation.EXCLUDE_AND_CONTINUE, 
            endNode));

来源

2018-02-28 13:21:32

使用TraversalDescription查找所有最短路径

回答

相关问题