背景：Neo4j自帶的cypher語句中的 shortestpath allShortestPaths 返回值內容非常有限，不易處理, 在實際生產環(huán)境中可用性極低， 且若帶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.*

4. 重啟neo4j 服務
5. 驗證gds安裝成功

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

使用GDS

1. 創(chuàng)建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) 

2. 計算A-E最短路徑，首先創(chuàng)建投影圖

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

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

4. 返回節(jié)點信息

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計算過程中默認行為是計算從一個節(jié)點到另一個節(jié)點的跳數，而不考慮邊相關聯(lián)的任何權重。
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. 單源最短路徑
單源最短路徑是計算給定節(jié)點到其他所有節(jié)點的距離
其中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://blog.csdn.net/GraphWay/article/details/120032403文章來源地址http://www.zghlxwxcb.cn/news/detail-437572.html

到了這里，關于neo4j結合gds實現最短路徑算法的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！