如何在Neo4j中找到最短路径并保证跳数最少？

Question

我正在建模一个图形，其中节点是地点，边缘表示您可以从一个地方到另一个地方。

这是为了拥有您可以从一个地方到另一个地方的所有路线， 而且您可以通过不同的路径从一个地方到另一个地方，因此我想要一个查询，返回最短路径和最小路线更改。

例如，我想从A到D，我有两条可能的路径：

(place {name: "A"})-[:FOLLOWS{route:""R1}]->(place{name: "B" })-[:FOLLOWS{route:""R4}]->(place{name:"C"})-[:FOLLOWS{route:""R2}]->(place{name:"D"})

(place {name: "A"})-[:FOLLOWS{route:""R1}]->(place{name: "B" })-[:FOLLOWS{route:""R1}]->(place{name:"F"})-[:FOLLOWS{route:""R2}]->(place{name:"D"})

在前两条路径中，它们的大小相同，但我想要第二条路径，即具有最小路线更改的路径。

谢谢。

- Kimy BF

---

这是一个很好的问题，我从答案中学到了不少东西。 - Tim Kuehn

Answer 1

@DevBennett的答案可以得到最短路径和最少的路线更改。

要获得最短路径和最少不同路线的答案，这正是问题所要求的（但可能不是提问者实际想要的），您可以使用以下查询：

MATCH p=ALLSHORTESTPATHS((a:Place {name: "A"})-[:FOLLOWS*]->(d:Place{name:"D"}))
UNWIND RELATIONSHIPS(p) AS rel 
WITH p, COUNT(DISTINCT rel.route) AS nRoutes 
RETURN p, nRoutes 
ORDER BY nRoutes 
LIMIT 1;

- cybersam

---

我实际上想要最少的路径更改，因为在一条路径中，我可以有2个路线，但在每个边缘都要进行更改。无论如何，我意识到我两个问题都提出了:) 对于误解我感到抱歉。这真的很有帮助。谢谢。 - Kimy BF

Answer 2

类似这样的：

MATCH 
    (a:place {name: "A"}) WITH a
MATCH
    (d:place {name: "D"}) WITH a,d 
MATCH
    p = allShortestPaths  ( (a)-[:FOLLOWS*..100]->(d) )
WITH 
    nodes(p) as places, relationships(p) as paths
UNWIND
    paths as path
WITH
    places, paths, collect(distinct path.route) as segments
RETURN
    places, paths, segments, size(segments) as cost
ORDER BY
    cost ASC
LIMIT 1

- stdob--

---

只有当我更改这个时，它才按照我想要的方式工作： p = allShortestPaths((a)-[:FOLLOWS*]->(d)). 谢谢。 - Kimy BF

Answer 3

加油，只有三个答案你不可能满意的 :)

MATCH (a:Place {name:"A"}), (d:Place {name:"D"})
MATCH p=allShortestPaths((a)-[*]->(d))
RETURN p, 
size(filter(x in range(0, size(rels(p))) 
       WHERE (rels(p)[x]).route <> (rels(p)[x-1]).route)) + length(p) as score
ORDER BY score ASC

- Christophe Willemsen

---

我喜欢它 - 希望我能想到那个。 - Dave Bennett

Answer 4

我认为这会满足你的需求。它找到所有最短路径，然后处理每个路径以计算路线变更次数。然后按照路线变更最少的顺序对结果集进行排序，并将结果集限制为第一个出现。

// find all of the shortest paths that match the beginning and ending nodes
match p=allShortestPaths((a:Place {name: 'A'})-[:FOLLOWS*]->(d:Place {name: 'D'}))

// carry forward the path, the relationships in the path and a range that represents the second to last relationships in the path 
with p,relationships(p) as rel, range(1,length(p)-1) as index

// use reduce to process the route attribute on the relationship to accumulate the changes
with p, rel, index, reduce (num_chg = 0, i in index | num_chg + 
    case when (rel[i]).route = (rel[i-1]).route then 0 else 1 end ) as changes

// return the path and the number of route changes
return p, changes

// only return the path with the fewest route change
order by changes
limit 1

- Dave Bennett

Answer 5

使用"AllShortestPaths"的答案是错误的。

如果图形看起来像下面的图片呢？

图形示例 那么，使用AllShortestPaths函数查询的结果将是"A-E-D"而不是"A-B-C-D"...

- Kubilay Toker

---

抱歉，我刚刚登录，还没有足够的“声望”来发表评论 :p - Kubilay Toker