在 Neo4j 中，2 个节点之间通过航点的最短路径

Question

我在neo4j中有一个图表，其中节点代表城市，关系代表连接城市的道路。这些关系是加权的，并具有称为"距离"的属性。 我想找到两个城市 A 和 B 之间的最短(最小权重路径(。使用Dijkstra的算法可以轻松完成此操作。棘手的部分是，我有一组城市，这些城市将在从A到B的路径中覆盖。换句话说，从A到B的路径应该覆盖所有的航点，顺序无关紧要。 比如在Google API中提供源，目的地和航点列表以及优化：true。 我已经通过以下查询使用Cypher尝试了这个 -

match(s:City{ID:"A"})
match(f:City{ID:"B"})
match (n:City) where n.name in ['City1','City2','City3','City4']
with collect(n) as wps 
match path=allshortestPaths((s)-[:ROADWAY*..9]->(f))
where ALL ( n in wps WHERE n in nodes(path) ) with path, 
reduce(d=0, rel IN relationships(path)| d+rel.displacement) as             
totaldistance,Extract (n in nodes(path)| n.name) as cities 
return cities, totaldistance, tofloat(totaldistance) as TD order by 
totaldistance

但这没有用。也许是因为路径没有通过所有的航点。 我也在尝试使用 A* 或 Dijkstra(使用 Neo4j Traversal(，但不确定如何访问所有航点。

提前感谢！！

Answer 1

尝试使用ANY而不是ALL。

来自 neo4j 文档

All- 测试谓词是否适用于此列表的所有元素。

而

Any- 测试谓词是否至少适用于 列表。

match(s:City{ID:"A"})
match(f:City{ID:"B"})
match (n:City) where n.name in ['City1','City2','City3','City4']
with collect(n) as wps 
match path=allshortestPaths((s)-[:ROADWAY*..9]->(f))
where ANY ( n in wps WHERE n in nodes(path) ) with path, 
reduce(d=0, rel IN relationships(path)| d+rel.displacement) as             
totaldistance,Extract (n in nodes(path)| n.name) as cities 
return cities, totaldistance, tofloat(totaldistance) as TD order by 
totaldistance

编辑 - 我们可以更改此设置，以确保通过在 where 子句中组合多个 ANY 来包含所有城市：

match(s:City{ID:"A"})
match(f:City{ID:"B"})
with collect(n) as wps 
match path=allshortestPaths((s)-[:ROADWAY*..9]->(f))
where ANY ( n in nodes(wps) WHERE n.name = 'City1' ) AND
ANY ( n in nodes(wps) WHERE n.name = 'City2) 
with path, 
reduce(d=0, rel IN relationships(path)| d+rel.displacement) as             
totaldistance,Extract (n in nodes(path)| n.name) as cities 
return cities, totaldistance, tofloat(totaldistance) as TD order by 
totaldistance