如何在Neo4j中使用Cypher实现Dijkstra算法

Question

我的问题是：是否可以使用Cypher实现Dijkstra算法？Neo4j网站上的解释只涉及REST API，对于像我这样的初学者来说非常难以理解。

请注意，我想找到两个节点之间最短距离的最短路径，而不是涉及最少关系的最短路径。我知道可以使用Cypher轻松实现shortestPath算法，但这并不能满足我的要求。

如果我有一个具有节点的图形数据库，并且节点之间的关系具有属性“distance”，请指导我如何继续操作。我想编写一段代码，借助它我们将能够在数据库中找到两个节点之间的最短距离。或者如果我需要改变我的方法并使用其他程序，请给我一些提示？

- Shazu

---

这里有一个相关的最近问题（https://dev59.com/rIXca4cB1Zd3GeqPOdgN），或许可以帮到你。 - zaboco

是的，我曾经提过这个问题，我收到的回答在某种意义上是正确的，因为我可以获得最短路径（最少关系数量）和节点之间距离的总和......但我要找的是最短路径（最小“距离”），所以我必须再提一个问题来澄清。 - Shazu

这里的“distance”是什么意思？你的关系中是否有一些属性代表两个节点之间的一个关系“跳”所需的距离？ - FrobberOfBits

是的，没错。每个关系都有一个名为“距离”的属性。 - Shazu

Answer 1

在这种情况下，您可以实现allShortestPaths，基于关系的距离属性按升序对路径进行排序，并仅返回一个路径。根据您上一篇文章的内容，它可能类似于以下内容：

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , 
paths = allShortestPaths((from)-[:CONNECTED_TO*]->(to))
WITH REDUCE(dist = 0, rel in rels(paths) | dist + rel.distance) AS distance, paths
RETURN paths, distance
ORDER BY distance
LIMIT 1

- Christophe Willemsen

---

请问您能否编辑您的代码： 将第四行中的path改为paths，将第五行中的p改为paths，这样如果未来有其他人看到这段代码，就不会感到困惑了。谢谢！ - Shazu

好的，当然没问题。对不起，这是本地测试中混杂在一起的 :) - Christophe Willemsen

Neo4j中的Dijkstra实现也可以作为服务器扩展的一部分或通过REST API使用：http://neo4j.com/docs/stable/rest-api-graph-algos.html#rest-api-execute-a-dijkstra-algorithm-with-equal-weights-on-relationships - Michael Hunger

注意 - 上述解决方案首先根据关系数量过滤所有最短路径。 然后使用距离属性来找到最短路径。在第一步中，我们可能已经错过了具有更多关系但总距离较短的路径。 - Prashant Deep

它们将被返回，所有最短路径的意义 - Christophe Willemsen

Answer 2

不，除非您使用事务并基本重写算法，否则没有合理的方法可以实现。 之前的答案是错误的，因为更长但更便宜的路径不会被allShortestPaths子集返回。您将过滤一组已选择的路径子集，而这些路径子集在考虑关系成本时未被考虑。

- Pempo