如何在带有属性过滤器但没有GDS的neo4j中找到最短路径？

Question

我想在 Neo4j 中找到起始节点和结束节点之间的最短路径。该图表使用属性“costs”和“transit_time”进行加权。

我想找到运输时间方面最短的路径。然而，为此我只希望每个关系的成本低于 1000。要求是，我不能使用 GDS。事实上，我不能使用任何创建子图的东西（所以 apoc 子图也不是一个选项）。我用 APOC 尝试过这个

MATCH (start:Node {id: 'startId'}), (end:Node {id: 'endId'})
CALL apoc.algo.dijkstra(start, end, 'REL1|REL2', 'transit_time') YIELD path, weight
WHERE all(r in relationships(path) WHERE r.costs < 1000)
RETURN path, weight

但是，如果找到的最短路径与 WHERE 条件不匹配，我什么也得不到。如何告诉 Dijkstra 函数仅考虑符合条件的特定关系？

我在 GitHub 上找到了这个讨论：https://github.com/neo4j/apoc/issues/136

但是，APOC 内部似乎没有解决方案（截至 2022 年 9 月）。所以我继续寻找解决方法。

诚挚的问候并感谢您的帮助！

Answer 1

您可能得不到答案的一个原因是，按权重计算的最短路径

transit_time

返回一条与

cost >= 1000

至少有一种关系的路径。

如果您能够使用 GDS，您可以在投影过程中消除与

cost >= 1000

的关系，然后使用

gds.shortestPath.dijkstra

。

但正如你所说，这不是一个选项，另一种方法是使用 apoc.algo.dijkstra 的最后一个参数返回

N

最短路径，用

cost >= 1000

过滤掉任何路径，并使用

 选择最短路径ORDER BY weight LIMIT 1

：

MATCH (start:Node {id: 'startId'}), (end:Node {id: 'endId'})
CALL apoc.algo.dijkstra(start, end, 'REL1|REL2', 'transit_time', NaN, 10) 
YIELD path, weight
WHERE all(r IN relationships(path) WHERE r.costs < 1000)
RETURN path, weight ORDER BY weight LIMIT 1

这里我设置了

N = 10

。问题是，为

N

选择一个值是任意的，所有 N 个最短路径仍然可能无法通过测试，并且算法可能会做超出必要的工作。

暴力方法肯定会返回结果（如果有路径），但可能会非常昂贵：

MATCH path = (start:Node {id: 'startId'})-[rel:REL1|REL2 WHERE rel.costs < 1000]-+
             (end:Node {id: 'endId'})
WITH path, reduce(acc = 0, r IN relationships(path) | acc + r.transit_time) AS weight
RETURN path, weight ORDER BY weight LIMIT 1