neo4j - 必须包含某些航路点的最短路径

Question

我试图找到连接任意节点集合的最短路径。 start 和 end 都可以是集合中的任何节点，只要它们不相同即可。
标准密码函数 shortestPath() 或 allShortestPaths() 失败，因为它们找到了从开始到结束的最短路径并且不包括航点。
以下密码有效，但有更快的方法吗？

//some collection of nodeids, as waypoints the path has to include
match (n) where id(n) IN [24259,11,24647,28333,196] 
with collect(n) as wps

// create possible start en endpoints
unwind wps as wpstart
unwind wps as wpend
with wps,wpstart,wpend where id(wpstart)<id(wpend)

// find paths that include all nodes in wps
match p=((wpstart)-[*..6]-(wpend))
where ALL(n IN wps WHERE n IN nodes(p))

// return  paths, ordered by length
return id(wpstart),id(wpend),length(p) as lp,EXTRACT(n IN nodes(p) | id(n)) order by lp asc

2015 年 10 月 23 日更新:
使用最新的 Neo4j 版本 2.3.0，可以将 shortestPath() 与在评估过程中拉入某处的 WHERE clasue 结合起来。然后你会得到一个这样的结构，其中 {wps} 是一个 nodeIds 的集合。

// unwind the collection to create combinations of all start-end points
UNWIND {wps} AS wpstartid
UNWIND {wps} AS wpendid
WITH wpstartid,wpendid WHERE wpstartid<wpendid

// for each start-end combi,calculate shortestPath() with a WHERE clasue
MATCH (wpstart) WHERE id(wpstart)=wpstartid
MATCH (wpend) WHERE id(wpend)=wpendid
MATCH p=shortestPath((wpstart)-[*..5]-(wpend))
WHERE ALL(id IN {wps}  WHERE id IN EXTRACT(n IN nodes(p) | id(n))   )

//return the shortest of the shortestPath()s
WITH p, size(nodes(p)) as length order by length limit 1
RETURN EXTRACT(n IN nodes(p) | id(n))

这种方法并不总是有效，因为有一个内部优化来确定在哪个阶段应用 WHERE 子句。所以要小心，并准备好在项目开始时退回到更暴力的方法。

Answer 1

这将是一个非常不令人满意的答案，但这里有:

我强烈怀疑您提出的问题可以简化为 Hamiltonian Paths 的问题.这是一个经典的图算法问题，结果证明是 NP 完全的。所以实际上，这意味着虽然有可能实现这一点，但性能可能会很糟糕。

如果你真的必须实现这一点，我可能会建议不要使用 cypher，而是使用 neo4j 遍历框架构建一些东西。您可以在线找到示例代码和算法，它们至少可以完成其中的一部分。但更广泛地说，如果您的数据大小不一，那么这个答案令人不满意的部分是我可能根本不会这样做。

更好的选择可能是将您的图形分解为您可以独立工作的更小的子问题，或者提出另一种启发式方法来让您接近您想要的结果，但不是通过这种方法。