在图表中查找最长路径

Question

我一直在努力寻找复杂网络中最长的路径.我在StackOverflow和Internet上经历了很多问题,但没有人可以帮助我.我写了一个CQL

start n=node(*)
match p = (n)-[:LinkTo*1..]->(m)
with n,MAX(length(p)) as L
match p = (n)-[:LinkTo*1..]->(m)
where length(p) = L
return p,L

我没有得到任何解决方案.Neo4J会继续寻找答案,我也尝试在Neo4J Cloud Hosting中执行它.我没有任何解决方案,但有一个错误"错误未定义 - 未定义"我迫切需要一个解决方案.这个答案的结果将帮助我完成我的项目.所以,有人请帮我纠正查询.

Answer 1

好吧,如果你只需要做一次,你就会做两次非常昂贵的操作.

此外,您至少会为数据库中的每个节点返回一个路径(因为可能存在多个路径,这些路径是该节点可用的最长路径).但是从您的问题来看,您似乎想要图中的单个最大路径,而不是每个节点都有一个路径.

我们还可以通过仅在路径头部的节点上执行最长路径匹配来改进匹配,而不是在中间的某个位置.

也许试试这个？

match (n)
where (n)-[:LinkTo]->() and not ()-[:LinkTo]->(n)
match p = (n)-[:LinkTo*1..]->(m)
return p, length(p) as L
order by L desc
limit 1

Answer 2

您要解决的问题是NP难题。在较小的稀疏图上，诸如InverseFalcon建议的蛮力方法可能会在合理的时间内成功，但是在任何合理的较大和/或紧密连接的图上，您将很快遇到时间和空间问题。

如果具有加权图，则可以通过取反所有边缘权重并在修改后的图上运行最短加权路径算法来找到2个节点之间的最长路径。但是，如果要在整个图中找到最长的路径，则可以有效地尝试解决旅行商问题，但具有-ve边缘权重。您无法使用Cypher做到这一点。

如果您的图形未加权，我会发现一个更简单的问题，或者看看您是否可以将图形转换为加权后的图形并按照上述方法解决。或者，查看是否可以以不需要最长路径的方式来构造需求。