Come trovare il percorso più breve con il numero minimo di hop in Neo4j?

Question

Im modellando un grafico in cui i nodi sono posti e bordi indicano che è possibile passare da un luogo a un altro.

Questo è per avere tutti i percorsi che è possibile effettuare da un luogo all'altro, e si può passare da un luogo all'altro per percorsi diversi, quindi voglio una query che mi restituisca il percorso più breve con le modifiche minime del percorso .

Per esempio, voglio andare da A a D, ho due possibili percorsi:

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

Nei due percorso precedente, entrambi sono le stesse dimensioni, ma vorrei ottenere il secondo , che è colui che ha il cambio di percorso minimo.

Grazie.

Answer 1

Penso che questo soddisferà le vostre esigenze. Trova tutti i percorsi più brevi. Quindi elabora ognuno per contare il numero di cambi di percorso. Ordina quindi il risultato impostato dal minor numero di cambi di percorso e limita il set di risultati alla prima occorrenza.

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

@ risposta di DevBennett ottiene il percorso più breve con il minimo numero di percorso cambia.

per ottenere il percorso più breve con il numero minimo di diversi percorsi, che è ciò che la questione letteralmente chiesto (ma che non può essere stato quello che il richiedente ha in realtà voleva), è possibile utilizzare questa query:

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

Qualcosa di simile a questo:

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

Dai, non poteva essere felice con solo 3 risposte :)

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 

Answer 5

Le risposte che utilizzano "AllShortestPaths" sono errate.

Cosa succede se il grafico è simile all'immagine qui sotto?

Example of Graph Ebbene, il risultato delle query utilizzando la funzione AllShortestPaths sarà "A-E-D" e non "A-B-C-D" ...