---
title: 'Neo4J path traversal: A* optimization'
date: 2018-03-06
layout: post
---

Work project. Marine vessel tracking with Neo4J hit a limit. Need to store
13,000 route points; Dijkstra's shortest path search slows after 4,000.

Replaced Dijkstra's algorithm with A* search using haversine function as
heuristic:

```
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 better path 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);
    }
}
```

Outcome: 300x speedup. Scaled to 13,000 route points. 

Upstreamed changes: <a
href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0"
class="external" target="_blank" rel="noopener noreferrer">Neo4J v3.4.0</a> | 
[Full
source](https://github.com/neo4j-contrib/neo4j-graph-algorithms/blob/bd9732d9a690319552e134708692acb5a0d6b37c/algo/src/main/java/org/neo4j/graphalgo/impl/ShortestPathAStar.java)