程序员经验分享-hwhale

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

2023-05-16

背景：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. 重启neo4j 服务
  2. 验证gds安装成功
RETURN gds.version()
CALL gds.list()

使用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. 计算A-E最短路径，首先创建投影图
call gds.graph.create("ellis","Line","LINKED_TO")
  1. 迪杰斯特拉计算最短路径
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. 返回节点信息

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://blog.csdn.net/GraphWay/article/details/120032403

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

neo4j结合gds实现最短路径算法 的相关文章

随机推荐

  • 移动机器人运动规划(四)--动力学约束下的路径规划

    本节课主要介绍动力学约束下的路径规划 xff0c 还是有些难度的 xff01 首先依然是课程大纲 xff1a 五个部分 xff0c 重点是中间的三个部分 xff0c ppt上的顺序错了 xff0c 课程先讲的Hybrid A xff0c 其

  • Linux系统使用putty连接时报错：Server unexpectedly closed network connection

    写在前面 xff1a 本次是处理Linux系统的问题 xff1b Linux系统不能远程连接 前段时间遇到一个小问题 xff0c 客户反应我们的软件无法打开 xff0c 在集团侧内网操作 xff0c 在浏览器内输入IP地址 xff0c 无法

  • Docker的安装与使用

    1 xff0e Window10 1 1 docker安装 https www runoob com docker windows docker install html 1 2 centos7 vnc安装 拉取镜像centos7 span

  • 深度学习——数据之间的形式转化

    一 简介 在深度学习中 xff0c 会用到各种各样的数据类型 有python中常用的list xff0c 使用numpy这个科学计算库时的numpy ndarray xff0c 还有使用pytorch框架时的torch Tensor 使用数

  • 有哪些国外常用的论文网站

    经常需要查阅论文时 xff0c 除了知网还有下面这些外文网站方便我们查阅 数据库中的论文一般是比较高质量的 xff0c 有的更需要购买才可浏览下载 推荐论文下载网站 xff1a http sci hub tw 个人常用 xff1a 深度学术

  • 【经典配对解析】双子vs.天蝎：致命玩火冤家

    原创 xff1a 珊珊树 转载请注明 xff1a xff09 最近开辟一个话题专栏 xff1a 星座经典配对分析 把我们身边看到最多的 欢笑冤家 写出来 说明 xff1a 这里说的A星座vs B星座 xff0c 不一定是讲太阳星座 也可以说

  • Python爬虫项目之NBA球员可视化分析

    Python爬虫学习之NBA球员可视化分析 前言 最近刚上完Python选修课 一直挺喜欢Python的 觉得Python的简洁优美的代码像是在写诗一样让人看了赏心悦目 其次就是他强大的第三方库是其他语言所不能媲美的 有很多你需要用的功能

  • postgresql时间戳与时间的转换

    日期转时间戳 span class token keyword select span EXTRACT span class token punctuation span epoch span class token keyword FRO

  • python xml文件解析

    1 解析 1 1 解析方式 Python 有三种 XML 解析方式 xff1a SAX xff08 simple API for XML xff09 DOM xff08 Document Object Model xff09 Element

  • python输出列表去掉中括号

    可以使用 join的方法进行输出 xff0c 因为 join处理的是字符串 xff0c 所以需要进行类型转换 list1 span class token operator 61 span span class token punctuat

  • postgresql取出分组的第一条数据

    span class token comment 根据编号分组后取第一条数据 span span class token keyword SELECT span span class token operator span span cla

  • git 清空本地修改

    span class token function git span checkout span class token keyword span span class token comment 本地所有修改的 没有的提交的 xff0c

  • 关于Ubuntu卸载Python导致的终端没了

    解决方式 sudo upgrade fix missing sudo apt install ubuntu desktop

  • elasticsearch wildcard查询取消大小写

    https stackoverflow com questions 51107349 elasticsearch wildcard case sensitive 添加case insensitive 参数即可 GET test 005 se

  • window VNC Viewer设置屏幕分配率

    问题 xff1a 远程时 xff0c 显示的界面不会跟着本机屏幕大小而自动调节 xff0c 导致无法在页面中完全显示屏幕的内容 解决1 xff1a 打开VNC Viewer xff0c 选择Options xff0c 在Scale to w

  • .net core 中使用MongoDB

    https www thecodebuzz com exception filters in net core https www mongodb com docs drivers csharp https www mongodb com

  • 使用代理下载国外源registry.k8s.io镜像，并传到docker hub私有镜像库

    日常的生产开发中 xff0c 免不了从国外拉取镜像 xff0c 但有个问题 xff0c 我们可能访问不到那个镜像源 xff0c 因此需要使用代理 https labs play with docker com 具体步骤 使用docker h

  • python 操作neo4j

    安装依赖包 pip span class token function install span neo4j 使用 span class token keyword class span span class token class nam

  • neo4j获取不同维度关联关系

    插入数据 CREATE span class token punctuation span 小北 朋友圈 span class token punctuation span 姓名 span class token string 34 小北

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

    背景 xff1a Neo4j自带的cypher语句中的 shortestpath allShortestPaths 返回值内容非常有限 xff0c 不易处理 在实际生产环境中可用性极低 xff0c 且若带where条件查询时 xff0c 查

热门标签