获取两个节点之间的所有路径neo4j

Question

获取两个节点之间的所有路径neo4j

neo4jcypher

10

我正在处理一个项目，需要处理图表...我使用图表来获取两个站点之间的公交车和自行车路线。

事实上，我所有的关系都包含从关系起点到终点所需的时间。

为了获得两个节点之间的最短路径，我使用Cypher的最短路径函数。但有时候最短路径并不是最快的...

有没有办法获取两个没有关系连接的节点之间的所有路径？

谢谢！

编辑：

实际上，我改变了我的图表，使它更容易一些。现在，关系类型对应于从一个节点到另一个节点所需的时间。

Cypher的shortestPath函数返回包含最少关系的路径。我希望它返回所有类型（时间）相加最小的路径..这可能吗？

谢谢！

- Guillaume le Floch

你必须使用Cypher吗？我可以想到一些Gremlin脚本，可以打印出非常漂亮的结果。 - Nicholas

实际上我正在使用Node.js。。。我有一个库来查询我的neo4j图，允许我执行一些Cypher查询...而不是Gremlin查询... - Guillaume le Floch

2个回答

4

你可以使用Dijkstra/Astar算法，这似乎非常适合你。看一下http://api.neo4j.org/1.8.1/org/neo4j/graphalgo/GraphAlgoFactory.html 不幸的是，你不能在Cypher中使用它们。

- Mattias Finné

是的，我考虑过这样做... 我只是想知道是否有一种方法可以使用Cypher获取两个节点之间的所有路径，因为在获取所有可能的路径之后，我可以解析它们并获取最快的路径.. 使用Cypher获取这些路径对我来说更容易，因为我正在使用Neo4j和Node.js。 - Guillaume le Floch

1

尽管首先获取两个节点之间的所有路径，然后再进行过滤可能会慢得多，因为算法无法聪明地立即选择最佳路径，即无法“捷径”。 - Mattias Finné

6

我们可能需要以某种方式将更多的算法暴露给 Cypher。 - Eve Freeman

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eve Freeman · Accepted Answer

在Cypher中，要获取两个没有关系连接的节点之间的所有路径，并按权重总和排序，可以使用1.9版本引入的reduce函数：

start a=node(...), b=node(...) // get your start nodes
match p=a-[r*2..5]->b // match paths (best to provide maximum lengths to prevent queries from running away)
where not(a-->b) // where a is not directly connected to b
with p, relationships(p) as rcoll // just for readability, alias rcoll
return p, reduce(totalTime=0, x in rcoll: totalTime + x.time) as totalTime
order by totalTime

如果你只需要最短的，可以在结尾加上限制为1。