neo4j：具有最小关系属性差异的最短路径

Question

我创建了以下图表来建模运输网络，其中车站通过服务节点（服务节点定义特定的服务日期）连接到其他车站。关系具有不同的类型和属性。具体而言，GOES_TO关系具有标识在车站之间行驶的trip（例如公交车）的id属性。

我希望找到最短路径，在所有: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关系根本没有id属性。

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

- 100grams

---

你解决了你的问题吗？你能描述一下你是怎么解决的吗？ - user3566301

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包在服务器上通过未托管的扩展和迪杰斯特拉算法轻松地实现此功能（或者在嵌入式中实现）。

- Eve Freeman

---

谢谢你的回答，但是我已经尝试过在我的图表上使用这个方法，但是它并没有起作用。查询执行了大约一分钟，然后失败并显示“未知错误”。显然，Cypher 不是解决这个问题的方法。我该如何在 Java 中使用 graphalgo 来解决这个问题？有什么有用的资源或示例可以提供吗？ - 100grams

如果将关系类型 / 深度更改为 -[:USES|GOES_TO*1..10]-，是否会有所不同？ 如果您使用2.0-RC1版本，还可以使用属性进行匹配，例如 (a: Stop {name：'A'})。 可能执行引擎已经为您执行了此操作，但这值得一试。 - jjaderberg

是的，我正在使用节点属性来匹配初始节点，并且在关系上也使用了深度限制，但是对于这个图来说，深度为10实在太小了，因为你很容易就会有一次旅程跨越25-50个站点，这就需要50-100个关系（每个跳跃都是停靠服务停靠）。 我想跟进@WesFreeman的建议并用Java编写它。我查看了org.neo4j.graphalgo.GraphAlgoFactory，但找不到如何通过不同的:GOES_TO.id值来限制dijkstra的方法。我真的很感激一些示例Java代码。 - 100grams