neo4j结合gds实现最短路径算法_neo4j 3.5 有 allshortestpaths

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

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

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

安装GDS

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

dbms.security.procedures.allowlist=gds.*
dbms.security.procedures.unrestricted=gds.*
dbms.security.procedures.whitelist=gds.*
1
2
3

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

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

使用GDS

1. 创建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) 

1
2
3
4
5
6
7
8
9
10
11
12
13

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

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

3. 迪杰斯特拉计算最短路径

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
1
2
3
4
5

4. 返回节点信息

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
1
2
3
4
5

上述返回的数据是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

1
2
3
4
5
6
7
8

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
1
2
3
4
5
6

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
1
2
3
4
5
6
7
8

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
1
2
3
4

https://blog.csdn.net/GraphWay/article/details/120032403