Neo4jの最小ホップ数で最短経路を見つけるには？

Question

グラフをモデリングするノードが場所と辺であるということは、ある場所から別の場所に移動できることを示しています。

これは、ある場所から別の場所に移動することができるすべてのルートを持っています（ ）。別のルートで別の場所に移動することができます。したがって、ルートの変更が最小限の最短パスを返します。

例えば、私はAからDに行きたい、私は2つの可能なパスを持っている：前の2回のパスで

(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"}) 

を、両方が同じ大きさですが、私は2番目のいずれかを取得したいと思いますこれは、ルートの変更が最小限の人物です。

ありがとうございます。

Answer 1

これはあなたのニーズを満たすと思います。それは最短経路のすべてを見つける。次に、それぞれを処理してルート変更の数をカウントします。次に、結果セットを最も少ないルート変更で順序付けし、結果セットを最初のオカレンスに限定します。 DevBennettの答え@

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

Answer 2

はルートを変更する最小数の最短パスを取得します。

質問は、文字通りを求めた（しかし、アスカーが実際に何を望むかされていない可能性がある）ものです異なる経路、最小限の数の最短パスを取得するには、このクエリを使用することができますが：

このような

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; 

Answer 3

何か：

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 

Answer 4

さあ、あなただけの3答え:)

と幸せになることができませんでした

Answer 5

"AllShortestPaths"を使用した回答が間違っています。

グラフが下の画像のように見える場合はどうなりますか？

Example of Graph まあ、AllShortestPaths機能を使用して、クエリの結果は "A-E-D" ではなく "A-B-C-D" になります...