neo4j结合gds实现最短路径算法

news/2024/7/5 1:58:06

背景：Neo4j自带的cypher语句中的 shortestpath allShortestPaths 返回值内容非常有限，不易处理, 在实际生产环境中可用性极低，且若带where条件查询时，查询效率极低
因此，使用Neo4j自带的插件如apoc来进行最短路径查询

Neo4j有对应的算法包， alog.* , 但是对应Neo4j的版本要和alog的大版本一直，如都是3.5.* ,

在3.5之后，neo4j弃用alog，改用 GDS (Graph data science)工具包 GDS安装及版本依赖

安装GDS

安装gds插件
查看neo4j版本对应的gds版本
我用的是3.5.12 所以选择的gds版本是1.1.0
下载gds jar包
将jar包放入plugins文件夹
修改neo4j.conf文件
添加如下

dbms.security.procedures.allowlist=gds.*
dbms.security.procedures.unrestricted=gds.*
dbms.security.procedures.whitelist=gds.*

重启neo4j 服务
验证gds安装成功

RETURN gds.version()
CALL gds.list()

使用GDS

创建Line

create (A:Line{name:"A"}) 
create (B:Line{name:"B"}) 
create (C:Line{name:"C"}) 
create (D:Line{name:"D"}) 
create (E:Line{name:"E"}) 
create (A)-[:LINKED_TO{weight:10}]->(B) 
create (A)-[:LINKED_TO{weight:33}]->(C) 
create (A)-[:LINKED_TO{weight:35}]->(D) 
create (B)-[:LINKED_TO{weight:20}]->(C) 
create (C)-[:LINKED_TO{weight:28}]->(D) 
create (C)-[:LINKED_TO{weight:6}]->(E) 
create (D)-[:LINKED_TO{weight:40}]->(E)

计算A-E最短路径，首先创建投影图

call gds.graph.create("ellis","Line","LINKED_TO")

迪杰斯特拉计算最短路径

MATCH(a:Line{name:"A"})
MATCH(e:Line{name:"E"})
call gds.alpha.shortestPath.stream("ellis",{startNode:a,endNode:e})
yield nodeId,cost
return nodeId,cost

返回节点信息

gds提供了gds.util.asNode函数，可以从nodeId转换成node

MATCH(a:Line{name:"A"})
MATCH(e:Line{name:"E"})
call gds.alpha.shortestPath.stream("ellis",{startNode:a,endNode:e})
yield nodeId,cost
return gds.util.asNode(nodeId),cost

上述返回的数据是A->D->E，但实际上考虑权重的情况下A->B->C->E才是最短的路径。这是因为shortestPath计算过程中默认行为是计算从一个节点到另一个节点的跳数，而不考虑边相关联的任何权重。
5. 迪杰斯特拉使用边的权重计算最短路径

call gds.graph.create("ellisweight","Line","LINKED_TO",{relationshipProperties:[{weight:"weight"}]})

MATCH(a:Line{name:"A"})
MATCH(e:Line{name:"E"})
call gds.alpha.shortestPath.stream("ellisweight",{startNode:a,endNode:e,relationshipWeightProperty:"weight"})
yield nodeId,cost
return gds.util.asNode(nodeId).name,cost

在这里插入图片描述
6. 计算totalCost


MATCH(a:Line{name:"A"})
MATCH(e:Line{name:"E"})
call gds.alpha.shortestPath.write("ellisweight",{startNode:a,endNode:e,relationshipWeightProperty:"weight"})
yield totalCost
return totalCost

在这里插入图片描述
7. k条最短路径算法
迪杰斯特拉以及A*算法只会返回一条路径，如果你对第二第三等路径感兴趣，则需要使用k条最短路径算法

MATCH(a:Line{name:"A"})
MATCH(e:Line{name:"E"})
call gds.alpha.kShortestPaths.stream("ellisweight",{startNode:a,endNode:e,relationshipWeightProperty:"weight",k:2})
yield index,sourceNodeId,targetNodeId,nodeIds
return index,
gds.util.asNode(sourceNodeId).name as source,
gds.util.asNode(targetNodeId).name as target,
gds.util.asNodes(nodeIds)  as path

在这里插入图片描述
8. 单源最短路径
单源最短路径是计算给定节点到其他所有节点的距离
其中delta是控制并行度的

MATCH(a:Line{name:"A"})
call gds.alpha.shortestPath.deltaStepping.stream('ellisweight',{startNode:a,relationshipWeightProperty:"weight",delta:1})
yield nodeId,distance
return gds.util.asNode(nodeId).name,distance