From 9ac8970b08550a83e9ba686d0e9357654373a047 Mon Sep 17 00:00:00 2001 From: Sadeep Madurange Date: Fri, 19 Dec 2025 21:32:28 +0800 Subject: Neo4J. --- _site/blog/neo4j-a-star-search/index.html | 31 +++++++++++++++---------------- _site/feed.xml | 2 +- _site/posts.xml | 2 +- 3 files changed, 17 insertions(+), 18 deletions(-) (limited to '_site') diff --git a/_site/blog/neo4j-a-star-search/index.html b/_site/blog/neo4j-a-star-search/index.html index 0d918c7..1fca4b6 100644 --- a/_site/blog/neo4j-a-star-search/index.html +++ b/_site/blog/neo4j-a-star-search/index.html @@ -46,24 +46,23 @@

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 optimal solutions to such problems. -In other words, the set of route points lends itself well to a model based on -graphs.

+could take through a network of about 13,000 route points. Graph theoretic +algorithms provide optimal solutions to such problems, and the set of route +points lends itself well to graph-based modelling.

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 Neo4J -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 vertices of a graph; the routes between them the edges; and the distances +between them the weights. For various reasons, people are interested in +minimizing (or maximizing) the weight of a path through a set of vertices, such +as the shortest path between two ports to predict a vessel’s arrival time.

+ +

Given a graph, an algorithm like Dijkstra’s search could compute the shortest +path between two vertices. In fact, this was the algorithm Neo4J 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 time complexity of this exhaustive search prevented our +database from scaling beyond 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 @@ -350,7 +349,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 -Neo4J graph algorithms shipped with the A* search algorithm.

+Neo4J graph algorithms shipped with our A* search algorithm.

by W. D. Sadeep Madurange

diff --git a/_site/feed.xml b/_site/feed.xml index 0309c54..5d6b137 100644 --- a/_site/feed.xml +++ b/_site/feed.xml @@ -1 +1 @@ -Jekyll2025-12-18T22:22:36+08:00/feed.xmlASCIIMX | BlogW. D. Sadeep MadurangeHow I manage Suckless software installations2025-11-30T00:00:00+08:002025-11-30T00:00:00+08:00/blog/suckless-softwareW. D. Sadeep MadurangeNeo4J A* search2025-09-14T00:00:00+08:002025-09-14T00:00:00+08:00/blog/neo4j-a-star-searchW. D. Sadeep MadurangeMOSFETs as electronic switches2025-06-22T00:00:00+08:002025-06-22T00:00:00+08:00/blog/mosfet-switchesW. D. Sadeep MadurangeHow to configure ATmega328P microcontrollers to run at 3.3V and 5V2025-04-10T00:00:00+08:002025-04-10T00:00:00+08:00/blog/arduino-unoW. D. Sadeep MadurangeHow to set up ATSAM3X8E microcontrollers for bare-metal programming in C2024-10-05T00:00:00+08:002024-10-05T00:00:00+08:00/blog/arduino-dueW. D. Sadeep Madurange \ No newline at end of file +Jekyll2025-12-19T21:32:14+08:00/feed.xmlASCIIMX | BlogW. D. Sadeep MadurangeHow I manage Suckless software installations2025-11-30T00:00:00+08:002025-11-30T00:00:00+08:00/blog/suckless-softwareW. D. Sadeep MadurangeNeo4J A* search2025-09-14T00:00:00+08:002025-09-14T00:00:00+08:00/blog/neo4j-a-star-searchW. D. Sadeep MadurangeMOSFETs as electronic switches2025-06-22T00:00:00+08:002025-06-22T00:00:00+08:00/blog/mosfet-switchesW. D. Sadeep MadurangeHow to configure ATmega328P microcontrollers to run at 3.3V and 5V2025-04-10T00:00:00+08:002025-04-10T00:00:00+08:00/blog/arduino-unoW. D. Sadeep MadurangeHow to set up ATSAM3X8E microcontrollers for bare-metal programming in C2024-10-05T00:00:00+08:002024-10-05T00:00:00+08:00/blog/arduino-dueW. D. Sadeep Madurange \ No newline at end of file diff --git a/_site/posts.xml b/_site/posts.xml index 3aed0d0..3be03f1 100644 --- a/_site/posts.xml +++ b/_site/posts.xml @@ -1 +1 @@ -Jekyll2025-12-18T22:22:36+08:00/posts.xmlASCIIMXW. D. Sadeep Madurange \ No newline at end of file +Jekyll2025-12-19T21:32:14+08:00/posts.xmlASCIIMXW. D. Sadeep Madurange \ No newline at end of file -- cgit v1.2.3