如何在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"})

在前两个路径中,两者都是相同的大小,但我想获得第二个路径,即具有最小路由更改的路径.

谢谢.

Answer 1

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

// 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