Search code examples
neo4jcyphershortest-patha-star

Is there a Neo4j A* Cypher query?

I'm currently using Neo4j's built-in Dijkstra to find the shortest path and it works.

START start=node(123), end=node(203454)
MATCH p=(start)-[:CONNECTS]->(end)
RETURN p as shortestPath,
REDUCE(distance=0, r in relationships(p) | distance+r.distance) AS totalDistance
ORDER BY totalDistance ASC
LIMIT 1

I want to be able to use A* algorithm as my nodes have Latitude and Longitude. Is there a Cypher query for that?

Solution

  • There is an A* algorithm in the APOC library's graph algorithms.

    run A* with relationship property name as cost function

    apoc.algo.aStar(
    startNode, endNode, 'KNOWS|<WORKS_WITH|IS_MANAGER_OF>', 
    'distance','lat','lon'
) YIELD path, weight

    run A* with relationship property name as cost function

    apoc.algo.aStar(
  startNode, endNode, 'KNOWS|<WORKS_WITH|IS_MANAGER_OF>',
  {weight:'dist',default:10, x:'lon',y:'lat'}
) YIELD path, weight