背景: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
文章来源:https://www.toymoban.com/news/detail-437572.html
https://blog.csdn.net/GraphWay/article/details/120032403文章来源地址https://www.toymoban.com/news/detail-437572.html
到了这里,关于neo4j结合gds实现最短路径算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!