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

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

苏南大叔:neo4j图数据库,如何计算节点间路径?如何求最短路径? - 求最短路径
neo4j图数据库,如何计算节点间路径?如何求最短路径?(图9-1)

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

苏南大叔:neo4j图数据库,如何计算节点间路径?如何求最短路径? - 测试用数据集
neo4j图数据库,如何计算节点间路径?如何求最短路径?(图9-2)

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

match(n) return n

苏南大叔:neo4j图数据库,如何计算节点间路径?如何求最短路径? - 数据图集
neo4j图数据库,如何计算节点间路径?如何求最短路径?(图9-3)

计算所有路径

如果想获取所有路径的话,使用的方式是[*],但是这种方式太耗费资源,等很久也不能出结果。所以,一般来说,会加上路径长度限制,比如:

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

下面的是一些范例:

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

苏南大叔:neo4j图数据库,如何计算节点间路径?如何求最短路径? - 取得所有路径
neo4j图数据库,如何计算节点间路径?如何求最短路径?(图9-4)

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

苏南大叔:neo4j图数据库,如何计算节点间路径?如何求最短路径? - 最容易的查看形式
neo4j图数据库,如何计算节点间路径?如何求最短路径?(图9-5)

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

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

(n{name:'A'})-[*1..3]->(m{name:'E'})
注意:上述表述不但对路径进行了长度限制,而且还对方向进行了限制。

计算最短路径

最短距离shortestpath():

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

苏南大叔:neo4j图数据库,如何计算节点间路径?如何求最短路径? - 最短路径求解
neo4j图数据库,如何计算节点间路径?如何求最短路径?(图9-6)

所有的最短距离allshortestpaths():

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

苏南大叔:neo4j图数据库,如何计算节点间路径?如何求最短路径? - 所有的最短路径all
neo4j图数据库,如何计算节点间路径?如何求最短路径?(图9-7)

苏南大叔:neo4j图数据库,如何计算节点间路径?如何求最短路径? - 所有的最短路径all2
neo4j图数据库,如何计算节点间路径?如何求最短路径?(图9-8)

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))在当前情形下,是没有啥意义。

苏南大叔:neo4j图数据库,如何计算节点间路径?如何求最短路径? - 计算结果
neo4j图数据库,如何计算节点间路径?如何求最短路径?(图9-9)

相关文章

综述

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

助理微信

微信打赏码

微信公众号

微信小程序

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

 【福利】 腾讯云最新爆款活动!1核2G云服务器首年50元!

 【源码】本文代码片段及相关软件,请点此获取更多信息

 【绝密】秘籍文章入口,仅传授于有缘之人   neo4j    cypher