多点两两之间的最短路径且经过某一个特定节点
发布于 25 天前 作者 crazyyanchao 214 次浏览 来自 问答

原始查询(需要优化):

WITH [2842,18446,51149,63373,87863,101324,230869,25,69710] AS id_list
MATCH (v) WHERE id(v) IN id_list
  WITH collect(v) AS nodes
  UNWIND nodes AS source
  UNWIND nodes AS target
  WITH source,target WHERE id(source)<id(target)
MATCH paths = (source)-[*..3]-(n)-[*..3]-(target) WHERE id(n)=1053 WITH paths LIMIT 10
  RETURN paths

这种查询效率特别差:

MATCH p=allShortestPaths((source)-[*..6]-(target))
WHERE all(x in nodes(p) where id(x)=1231) return p LIMIT  10

论坛中有人说可以用下面(算法包)的方式优化,请教一下根据我的原始查询如何优化?返回需要是P路径

(1)可以使用neo4j图算法库的方法:
> 用The Dijkstra Shortest Path algorithm :  
MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.shortestPath.stream(start, end, 'cost')
YIELD nodeId, cost
MATCH (other:Loc) WHERE id(other) = nodeId
RETURN other.name AS name, cost

(2)也可以把结果写回:
> MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.shortestPath(start, end, 'cost',{write:true,writeProperty:'sssp'})
YIELD writeMillis,loadMillis,nodeCount, totalCost
RETURN writeMillis,loadMillis,nodeCount,totalCost
12 回复

MATCH p=allShortestPaths((source)-[*…6]-(target))–这句效果很差吗? 你这个数据有多少条? 我也用的这个效率还行 WHERE all(x in nodes§ where id(x)=1231) return p LIMIT 10

我执行下面的CYPHER根本跑不动啊,并且报:Neo.ClientError.Transaction.TransactionTimedOut

WITH [2842,18446,51149,63373,87863,101324,230869,25,69710] AS id_list
MATCH (v) WHERE id(v) IN id_list
  WITH collect(v) AS nodes
  UNWIND nodes AS source
  UNWIND nodes AS target
  WITH source,target WHERE id(source)<id(target)
MATCH paths = allShortestPaths((source)-[*..6]-(target))
WHERE all(x in nodes(paths) where id(x)=1053) WITH paths LIMIT 10
  RETURN paths

1、两点最短路径,且要求经过一个固定的点 image.png 这个效率将会很差,建议用allShortestPaths 2、image.png 这里的all(),应该改为any,是包括一个固定点,不是全部是这个点 3、allShortestPaths:6层查询最短路径,基本是10ms级别的 可以自己程序中,开多线程,单个线程查一对组合的最短路径,最后将多线程的查询结果合并,时间很快的

4、待探究:algo.shortestPath.stream,看到文档对这个算法的描述是支持多个节点间查询最短路径的,但是还没尝试成功,并且缺点是返回的是三元组 sourceId-targetId-distance的三元组,并不是路径。 image.png

@daydayup 查询超时~ :) 执行的查询:

MATCH p=allShortestPaths((source)-[*..6]-(target))
WHERE id(source)=1059 AND id(target)=63373 AND any(x in nodes(p) where id(x)=1053) return p LIMIT  10

测试报错怕65030.png

我最后的查询方法是这样,因为固定距离上的节点已经查询出来了,只需要保证路径可达即可(最长查询6层关系) 至于上面那个问题还没解决,如果有测试过的朋友请留下个脚印(测试好几遍上面的all/any函数查询没法用太慢),下面的查询看起来简陋但是目前暂时满足了需求 另外[…3]-()-[…3],[…3]-()-[…2],[…5],路径的不同设置效率是不一样的([…3]-()-[*…3]满足需求且效率还可以接受百万级节点),具体测试用PROFILE查看一下

MATCH p = (n:Label1)-[*..3]-()-[*..3]-(f:Label2)-[*..3]-()-[*..3]-(m:Label3) WHERE id(n)=2842 AND id(f)=51172 AND id(m)=51149  RETURN p LIMIT 10

@crazyyanchao 可以先去掉where条件,确定是allShortestPaths慢,还是where条件慢

@crazyyanchao 并且用allShortestPaths的一个问题,如果你的需求是:必须经过这三点的最短路径,那么allShortestPaths不一定能满足你,这个是先找出source和target两点的所有最短路径,再判断,这些路径里,有没有包含中间点。 这样不能保证找到经过3个点的最短路径

@daydayup 我是已经用allShortestPaths找到了最短路径,然后这些点放在一个地方,已知开始结束点,然后用中间那些点再查一次,相当于再把最短路径过滤一遍。 试过了去掉WHERE挺快的。

这种查询查不出东西我也是很奇怪(巨慢无比)~:)

MATCH p=allShortestPaths((source)-[*..6]-(target))
WHERE all(x in nodes(p) where id(x)=1231) return p LIMIT  10

@crazyyanchao 如果allShortestPaths没问题,速度还可以的话, 那么就不是问题了,where条件很慢的话, 可以将where条件里的逻辑放到自己解析的代码里做,会比neo4j计算快很多

@crazyyanchao 不过讲道理来说,这个where条件不应该很慢,即使遍历所有的最短路径中的节点也不至于这么慢。 你设置的Transaction的TimedOut时间为多少?

@daydayup 问题就在这里,为啥用WHERE之后巨慢无比,不用WHERE速度还可以接受

dbms.transaction.timeout=180s
回到顶部