Contributed A* search to Neo4J

Written in 2026, backdated to 2018.

Before v3.4.0, Neo4J shipped with Dijkstra’s shortest path search. The algorithm was too slow for our marine vessel tracking application.

Forked and added A* search. Used the haversine function to steer the search:

private double computeHeuristic(
    final double lat1, final double lon1,
    final double lat2, final double lon2) {
    final int earthRadius = 6371;
    final double kmToNM = 0.539957;

    final double latDistance = Math.toRadians(lat2 - lat1);
    final double lonDistance = Math.toRadians(lon2 - lon1);

    final double a = Math.sin(latDistance / 2) 
        * Math.sin(latDistance / 2)
        + Math.cos(Math.toRadians(lat1)) 
        * Math.cos(Math.toRadians(lat2))
        * Math.sin(lonDistance / 2) 
        * Math.sin(lonDistance / 2);

    final double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
    return earthRadius * c * kmToNM;
}

Core search loop updates costs when a better path is found:

private void updateCosts(
    final int source, final int target,
    final double newCost, final double heuristic) {
    final double oldCost = gCosts.getOrDefault(target, Double.MAX_VALUE);
    if (newCost < oldCost) {
        gCosts.put(target, newCost);
        fCosts.put(target, newCost + heuristic);
        path.put(target, source);
    }
}

Upstreamed the changes.

GitHub release: Neo4J v3.4.0 | Full source.