使用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查找所有最短路徑

回答

相關問題