Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Implementing Dijkstra's algorithm in Neo4j

Tags:

neo4j

cypher

I am very new to Neo4j. Could someone kindly explain to me (step-by-step please) how I could implement the Dijkstra's algorithm to find the shortest path between two nodes? Is it possible to simply do it using Cypher?

I already tried the shortestPath algorithm, but it is very slow:

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , path = (from)-[:CONNECTED_TO*1..5]->(to)
RETURN path AS shortestPath, 
    reduce(distance = 0, r in relationships(path)| distance+toInt(r.Distance)) 
AS totalDistance
    ORDER BY totalDistance ASC
    LIMIT 1

my nodes are: Location with properties LocationID and LocationName my relationships are: CONNECTED_TO with property Distance

I have more than 6000 relationships

please note in the code above that I have limited to 1..5 when I do not define this limit, the query does not give any results (keeps on executing)

thanks

like image 684
Shazu Avatar asked Dec 07 '14 19:12

Shazu


People also ask

How is Dijkstra's algorithm implemented?

Here's how the algorithm is implemented: Mark all nodes as unvisited. Mark the initially selected node with the current distance of 0 and the rest with infinity. Set the initial node as the current node.

Can we apply Dijkstra in directed graph?

You can use Dijkstra's algorithm in both directed and undirected graphs, because you simply add nodes into the PriorityQueue when you have an edge to travel to from your adjacency list.

Can I run Dijkstra on a non weighted graph?

As i realised from the comments, Dijkstra's algorithm doesn't work for unweighted graphs.

Can Dijkstra be implemented without priority queue?

Dijkstra's algorithm needs a priority queue to find the next node to explore. Nodes are added to the priority queue with their currently-known total distance — their distance acts as their“priority”. A node's priority can later be updated with a new total distance if we find a shorter path to the node.


1 Answers

Yes it is possible with Cypher or with a dedicated endpoint of the Neo4j ReST API.

BTW, the examples from the Cypher Neo4j documentation are self explaining :

http://neo4j.com/docs/milestone/query-match.html#_shortest_path

To get the shortestPath between two nodes :

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , 
path = shortestPath((from)-[:CONNECTED_TO*]->(to))
RETURN path

If you want to get all the shortest

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , 
paths = allShortestPaths((from)-[:CONNECTED_TO*]->(to))
RETURN paths

If you want to order by the length (number of hops) of the paths in descending order :

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , 
paths = allShortestPaths((from)-[:CONNECTED_TO*]->(to))
RETURN paths
ORDER BY length(paths) DESC

If you to to get the shortestPath + the sum of the relationship distance property :

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , 
path = shortestPath((from)-[:CONNECTED_TO*]->(to))
WITH REDUCE(dist = 0, rel in rels(path) | dist + rel.distance) AS distance, p
RETURN p, distance
like image 149
Christophe Willemsen Avatar answered Sep 30 '22 22:09

Christophe Willemsen