neo4j - 是否有可能通过使用 Cypher 或 Gremlin 获得具有遍历成本的最短路径？

Question

我知道使用 Cypher 和 Gremlin 可以获得最少节点数的最短路径吗？如何获得具有最小遍历成本的路径？我能想到的例子之一是公交路线。有些路线可能有较少的公交车站（节点），但需要更长的时间（成本）从一个站点到另一个站点，有些是相反的。

是否有可能通过使用 Cypher 或 Gremlin 获得最短旅行时间的最短路径？

Answer 1

您可以查看并使用这个：

http://components.neo4j.org/neo4j-graph-algo/stable/apidocs/org/neo4j/graphalgo/GraphAlgoFactory.html#dijkstra(org.neo4j.graphdb.RelationshipExpander , org.neo4j.graphalgo.CostEvaluator)

---

以下是一些测试，展示了您可能可以使用的其他内置算法。

https://github.com/neo4j/neo4j/tree/master/community/graph-algo/src/test/java/org/neo4j/graphalgo/shortestpath

---

要推出自己的算法，您可以调用 neo4j java api 甚至 gremlin/groovy 管道，如下所示：

http://neo4j-contrib.github.io/gremlin-plugin/#rest-api-send-an-arbitrary-groovy-script---lucene-sorting

Answer 2

有关最短路径的更多信息，请参阅this other question。不过，在回答这个特定问题时，在计算路径的成本时，我首先更改了玩具图以使其权重marko to josh to lop低于marko to lop：

gremlin> g = TinkerGraphFactory.createTinkerGraph()
==>tinkergraph[vertices:6 edges:6]
gremlin> g.e(8).weight = 0.1f
==>0.1
gremlin> g.e(11).weight = 0.1f                                                        
==>0.1

然后计算 marko 和 lop 之间路径的“成本”：

gremlin> g.v(1).outE.inV.loop(2){it.object.id!="3" && it.loops< 6 }.path.transform{[it.findAll{it instanceof Edge}.sum{it.weight}, it]}
==>[0.4, [v[1], e[9][1-created->3], v[3]]]
==>[0.20000000298023224, [v[1], e[8][1-knows->4], v[4], e[11][4-created->3], v[3]]]

所以请注意，路径长度 3 throughmarko to josh to lop比 便宜marko to lop。无论如何，小鬼基本上说：

• g.v(1).outE.inV.loop(2){it.object.id!="3" && it.loops< 6 }.path- 抓住 marko 和 lop 之间的路径。
• .transform{[it.findAll{it instanceof Edge}.sum{it.weight}, it]}- 将每个路径转换为一个列表，其中第一个值是weight属性的总和，第二个值是路径列表本身。我通过查找路径中所有作为边缘的项目，然后将它们的权重值相加来计算路径列表本身的总权重。