Neo4J algorithms contribution

Written in 2026, backdated to 2018.

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

Forked the project and added the A* search algorithm.

Haversine function steers 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;
}

When a better path is found, the core search loop updates the costs:

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-contrib v3.4.0 | Full source.