From b1a2cc66bb29a04ca61d09c65355bcd18efad2d9 Mon Sep 17 00:00:00 2001 From: Sadeep Madurange Date: Fri, 28 Nov 2025 20:49:46 +0800 Subject: Improve neo4j write-up. --- _site/archive/neo4j-a-star-search/index.html | 46 +++++++++++++++------------- 1 file changed, 25 insertions(+), 21 deletions(-) (limited to '_site/archive') diff --git a/_site/archive/neo4j-a-star-search/index.html b/_site/archive/neo4j-a-star-search/index.html index 826ea2c..700630d 100644 --- a/_site/archive/neo4j-a-star-search/index.html +++ b/_site/archive/neo4j-a-star-search/index.html @@ -43,27 +43,30 @@

NEO4J A* SEARCH

14 SEPTEMBER 2025

-

Back in 2018, we used the Neo4J graph database -to track the movement of marine vessels. We were interested in the shortest -path a ship could take through a network of about 13,000 route points. -Performance issues with Neo4J’s shortest-path algorithms limited our search to -about 4,000 route points.

- -

A graph is a finite set of vertices, and a subset of vertex pairs known as -edges. Edges can have weights. In the case of vessel tracking, the route points -can be modeled as a graph with the distances between them as weights. For -different reasons, people are interested in minimizing (or maximizing) the -weight of a path through a set of vertices. For instance, we may want to find -the shortest path between two ports.

- -

Dijkstra’s algorithm is one such algorithm that finds the shortest path between -two vertices. The one drawback of this algorithm is that it computes all the -shortest paths from the source to all other vertices before terminating at the -destination vertex.

- -

The following enhancement, also known as the A* search, employs spherical -distance between route points (which are on the earth’s surface) as a heuristic -to steer the search in the direction of the destination far more quickly:

+

Back in 2018, we used Neo4J graph database to track the +movement of marine vessels. We were interested in the shortest path a ship +could take through a network of about 13,000 route points. Algorithms based on +graph theory, such as A* search, provide an optimal solution to this +problem. Therefore, it was useful to model the set of route points as a graph.

+ +

A graph is a finite set of vertices, and a subset of vertex pairs (edges). +Edges can have weights. In the case of vessel tracking, the route points form +the vertices of a graph; the routes between them, the edges; and the distances +between them are the weights. For different reasons, people are interested in +minimizing (or maximizing) the weight of a path through a set of vertices. For +instance, we may want to find the shortest path between two ports.

+ +

Given such a graph, an algorithm like Dijkstra’s search could compute the +shortest path between two vertices. In fact, this was the algorithm the Neo4J +project shipped with at the time. One drawback of Dijkstra’s algorithm is that +it computes all the shortest paths from the source to all other vertices before +terminating at the destination vertex. The exhaustive nature of this search +limited our search to about 4,000 route points.

+ +

The following enhancement to Dijkstra’s search, also known as the A* search, +employs a heuristic to steer the search in the direction of the destination +more quickly. In the case of our network of vessels, which are on the earth’s +surface, spherical distance is a good candidate for a heuristic:

package org.neo4j.graphalgo.impl;
 
@@ -341,6 +344,7 @@ public class ShortestPathAStar extends Algorithm<ShortestPathAStar> {
     }
 }
+

The heuristic function is domain-specific. If chosen wisely, it can significantly speed up the search. In our case, we achieved a 300x speedup, enabling us to expand our search from 4,000 to 13,000 route points. The v3.4.0 of the -- cgit v1.2.3