Come implementare l'algoritmo di Dijkstra in Neo4j usando Cypher

La mia domanda è: è possibile implementare l'algoritmo di Dijkstra usando Cypher? la spiegazione sul sito Neo4j parla solo di REST API ed è molto difficile da capire per un principiante come meCome implementare l'algoritmo di Dijkstra in Neo4j usando Cypher

prega di notare che voglio trovare il percorso più breve con il più breve distanza tra due nodi, e non il percorso più breve (che coinvolge il minor numero di relazioni) tra due nodi. Sono a conoscenza dell'algoritmo ShortestPath che è molto semplice da implementare con Cypher, ma non è funzionale al mio scopo.

Gentilmente guidami su come procedere se ho un database grafico con nodi e le relazioni tra i nodi che hanno la proprietà 'distanza'. Tutto quello che voglio è scrivere un codice con l'aiuto del quale saremo in grado di scoprire la distanza più breve tra due nodi nel database. O qualche consiglio se ho bisogno di cambiare il mio approccio e utilizzare qualche altro programma per questo?

fonte

2014-12-08 Shazu

c'è una [domanda recente] (http://stackoverflow.com/questions/27346686/implementing-dijkstras-algorithm-in-neo4j) correlata a questa, forse questo aiuta. – zaboco

sì, ho posto questa domanda, la risposta che ho ricevuto era corretta nel senso che avrei potuto ottenere il percorso più breve (il minor numero di relazioni) e la somma delle distanze tra i nodi .... ma quello che sto cercando è il più breve percorso (minimo 'distanza') quindi devo fare un'altra domanda per chiarire che – Shazu

Cosa significa qui "distanza"? Hai qualche attributo sulla tua relazione che rappresenta la distanza su una relazione "hop" tra due nodi? – FrobberOfBits

In questo caso è possibile implementare le allShortestPaths, ordinando i percorsi in un ordine crescente sulla base di vostra proprietà distanza delle relazioni e restituire solo uno, sulla base di tuo ultimo post, sarebbe qualcosa di simile:

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , 
paths = allShortestPaths((from)-[:CONNECTED_TO*]->(to)) 
WITH REDUCE(dist = 0, rel in rels(paths) | dist + rel.distance) AS distance, paths 
RETURN paths, distance 
ORDER BY distance 
LIMIT 1

fonte

2014-12-08 21:25:13

grazie !! puoi modificare il tuo codice: percorsi invece di percorso nella quarta linea e percorsi invece di p nella quinta riga in modo che se qualcun altro lo vede in futuro, non sono confusi. – Shazu

sì sicuro, mi dispiace, mescolato con alcuni test in locale :) –

L'implementazione dijkstra in Neo4j può anche essere usata come parte di un'estensione server o tramite l'API REST: http://neo4j.com/docs/stable/ rest-api-graph-algos.html # rest-api-execute-a-dijkstra-algoritmo-con-uguali-pesi-su relazioni –

No, non è possibile in modo ragionevole a meno che non si utilizzino le transazioni e in pratica si riscriva l'algoritmo. La risposta precedente è errata poiché i percorsi più lunghi ma meno costosi non verranno restituiti dal sottoinsieme allShortestPaths. Sarai filtrando un sottoinsieme di percorsi che sono stati scelti senza considerare il costo della relazione.

fonte

2016-05-18 17:26:26 Pempo

Come implementare l'algoritmo di Dijkstra in Neo4j usando Cypher

risposta

Problemi correlati