neo4j图数据库，如何计算节点间路径？如何求最短路径？

我们相信：世界是美好的，你是我也是。平行空间的世界里面，不同版本的生活也在继续...

neo4j图数据库中，两个节点之间使用关系进行联系的。那么，两个节点之间究竟怎么样才能扯上关系呢？要靠多少层关系才能建立联系呢？这个就是节点之间的路径计算问题。两个节点之间的路径可能有很多步，但是一定有个最短的路径。如何找到这个最短路径呢？

大家好，这里是苏南大叔的程序如此灵动博客，这里记录苏南大叔和计算机代码的故事。本文讲述，如何在图数据库中，找寻两个节点之间的路径。其实，本文的内容很具有实用价值。比如：在某某娱乐新闻中，经常会出现：某某明星和某某明星之间是怎么一个八竿子打不着的关系。这样的场景，都是可以使用这种最短路径计算进行的。本文测试环境：win10，neo4j社区版@4.4.6，java@11.0.14。

测试数据集

这个数据集也是官方文档里面给出的例子，这个数据集中给出了两个节点之间cost的概念。在本文中，并不是很合适。所以，本文的计算中，并没有考虑两个节点之间的cost的情况，或者说，认为任意的路径（关系）都是一样的。

CREATE (a:Location {name: 'A'}),
       (b:Location {name: 'B'}),
       (c:Location {name: 'C'}),
       (d:Location {name: 'D'}),
       (e:Location {name: 'E'}),
       (f:Location {name: 'F'}),
       (a)-[:ROAD {cost: 50}]->(b),
       (a)-[:ROAD {cost: 50}]->(c),
       (a)-[:ROAD {cost: 100}]->(d),
       (b)-[:ROAD {cost: 40}]->(d),
       (c)-[:ROAD {cost: 40}]->(d),
       (c)-[:ROAD {cost: 80}]->(e),
       (d)-[:ROAD {cost: 30}]->(e),
       (d)-[:ROAD {cost: 80}]->(f),
       (e)-[:ROAD {cost: 40}]->(f);

因为路径计算的问题，节点数据多的时候，就会非常耗时。所以，找个合适的例子也不是很容易。下图是相关的数据情况一览。

match(n) return n

计算所有路径

如果想获取所有路径的话，使用的方式是[*]，但是这种方式太耗费资源，等很久也不能出结果。

MATCH p=(n{name:'A'})-[*]->(m{name:'E'}) RETURN p

一般来说，会加上路径长度限制。比如：

• 1..7，路径长度1到7。
• 6..，路径长度6开始。
• ..10，路径最长10。
• 3，长度为3的路径。

MATCH p=(n{name:'A'})-[*2]->(m{name:'E'}) RETURN p

MATCH p=(n{name:'A'})-[*1..3]->(m{name:'E'}) RETURN p

MATCH p=(n{name:'A'})-[*3..]->(m{name:'E'}) RETURN p

MATCH p=(n{name:'A'})-[*..10]-(m{name:'E'}) RETURN p

由于节点之间的链接复杂性，计算这些路径的时候，可能会返回的节点结果视图，最好选择text的表现形式。
由于这个路径结果比较烧脑，苏南大叔选择a到e两步可达的路径作为本文的例子。

(n{name:'A'})-[*1..3]->(m{name:'E'})

注意：上述表述不但对路径进行了长度限制，而且还对方向进行了限制。

计算最短路径

最短距离shortestpath():

MATCH p=shortestpath((n{name:'A'})-[*1..3]->(m{name:'E'})) RETURN p

所有的最短距离allshortestpaths():

MATCH p=allshortestpaths((n{name:'A'})-[*1..3]->(m{name:'E'})) RETURN p

对p进行计算：

MATCH p=(n{name:'A'})-[*1..3]-(m{name:'E'}) RETURN p,length(p),count(p),Max(length(p)),Min(length(p))

从结果上来看，只有length(p)有意思，是当前关系路径的长度。而其它的count(p),Max(length(p)),Min(length(p))在当前情形下，是没有啥意义。

相关文章

• https://neo4j.com/docs/graph-data-science/current/algorithms/pathfinding/
• https://newsn.net/say/neo4j-match-node.html
• https://newsn.net/say/neo4j-match-relationship.html

综述

在neo4j图数据库中寻找路径的这个过程中，可真是那句老话：“条条大路通罗马”。如果使用默认的节点视图去查看结果的时候，就很有无从下手的感觉。如果切换到text模式，还是比较清晰的。

• https://newsn.net/tag/neo4j/

如果本文对您有帮助，或者节约了您的时间，欢迎打赏瓶饮料，建立下友谊关系。
本博客不欢迎：各种镜像采集行为。请尊重原创文章内容，转载请保留作者链接。