neo4j:具有最小关系属性方差的最短路径

Question

我创建了下图来模拟交通网络，其中停靠点通过服务节点连接到其他停靠点(服务节点定义特定的服务日期)。这些关系具有不同的类型和属性。具体来说，GOES_TO 关系有一个 id 属性，用于标识在站点之间行驶的行程(例如公共(public)汽车)。

我希望在路径上的所有 :GOES_TO 关系中找到具有最少数目的不同 id 值的最短路径。

在上面的例子中，最短路径应该是:

(A)-[:USES]-(1:Service)-[:GOES_TO {id:7}]->(B)-[:USES]-(2:Service)-[:GOES_TO {id: 7}]->(D)

此路径使用单个 id:7 从 A 到 D。

请注意，该条件仅适用于 :GOES_TO 关系。 :USES 关系根本没有 and id 属性。

我尝试了几种方法，但似乎无法用 cypher 解决这个看似简单的问题。

Answer 1

Cypher 还不能有效地执行加权最短路径(希望很快!)，但解决方法是使用 reduce 来聚合路径——需要注意的是它需要查看所有路径。也许是这样的:

MATCH p=(a:Stop)-[*]->(d:Stop)
WHERE a.name='A' and d.name='D'
RETURN p, 
  length(reduce(acc=[], r in rels(p)| acc + 
  case 
    when type(r) = "GOES_TO" 
     and NOT r.id IN acc 
    then r.id 
    else [] 
  end)) as distinctIds
ORDER BY distinctIds ASC;

如果它对您来说不够快，您可以通过 graphalgo 包(或嵌入式)在服务器上的非托管扩展中使用 dijskstra 算法非常容易地使其工作。