Bare-metal ARM Cortex M3 chips

BARE-METAL ARM CORTEX M3 CHIPS

+ +

05 OCTOBER 2024

+ +
+ +

This post is about programming bare metal SAM3X8E Arm Cortex M3 chips found on +Arduino Due boards. I had to learn how to do this because none of the +high-level tools for programming Arduino Dues are available for OpenBSD, which +I use for much of my personal computing.

+ +

Toolchain

+ +

Since we will not be using pre-packaged development tools, we need to assemble +our own toolchain. As usual, we need a compiler toolchain to build programs for +the target chip. As we will be bypassing the embedded bootloader, we will also +need a hardware programmer and an on-chip debugger to flash programs to the +chip. I used the following toolchain.

+ +

Arm GNU compiler +toolchain.
OpenOCD on-chip debugger.
ST-LINK/V2 +programmer.

+ +

Electrical connections

+ +

The following diagram outlines the electrical connections between the different +components necessary to move a compiled program from a PC to the MCU.

+ + + + + + +

Wiring

Arduino Due

+ +

Arduino Due exposes the SAM3X8E’s Serial Wire Debug (SWD) interface via its +DEBUG port. The ST-LINK/v2 programmer uses the SWD protocol to communicate with +the chip.

+ +

Uploading the program

+ +

Follow the steps below to upload a program to the SAM3X8E chip. The +source.tar.gz tarball at the end of the page contains a sample program with a +OpenOCD config file and a linker script.

+ +

Start OpenOCD: +
```
$ openocd -f openocd-due.cfg
+
```
+

Open a telnet session and check that the GPNVM1 bit is set. Otherwise +set it to 1:

+ +

$ telnet localhost 4444
+  > halt
+  > at91sam3 gpnvm show
+  > at91sam3 gpnvm set 1
+  > at91sam3 gpnvm show
+

Build the program using the custom linker script. +

$ arm-none-eabi-gcc -mcpu=cortex-m3 -mthumb -T script.ld \
+    -nostartfiles \
+    -nostdlib \
+    -o a.elf main.c
+

Upload the program using OpenOCD: +

$ openocd -f openocd-due.cfg -c "program a.elf verify reset exit"
+

+ +

Refer to the OpenOCD manual (AT91SAM3 flash driver section) for a complete list +of commands supported for the ATSAM3X8E.

+ +

GPNVM bits and the linker script

+ +

By design, ARM chips boot into address 0x00000. ATSAM3X8E’s memory consists of +a ROM and a dual-banked flash (flash0 and flash1), residing in different +locations of the chip’s address space.

+ +

The GPNVM bits control which of them maps to 0x00000. When GPNVM1 is cleared +(default), the chip boots from the ROM, which contains Atmel’s SAM-BA +bootloader. So, the chip runs the embedded bootloader instead of our program.

+ +

When the GPNVM1 bit is 1 (and the GPNVM2 bit is 0), flash0 at address 0x80000 +maps to 0x00000. When both GPNVM bits are 0, flash1 maps to 0x00000. Since we +place our program in flash0 using the linker script, we set the GPNVM1 bit and +leave the GPNVM2 bit as it is.

+ +

The linker script places the vector table at the first address of the flash. +ARM chips expect this unless we relocate the vector table using the VTOR +register. The first entry of the vector table must be the stack pointer, and +the second must be the reset vector.

+ +

Finally, the ATSAM3X8E uses a descending stack. So, in the linker script, we +initialize the stack pointer to the highest memory location available. In the +reset vector, we zero out memory, initialize registers, and perform other tasks +before passing control to the main program.

+ +

Files: source.tar.gz

+ +

by W. D. Sadeep Madurange

NOTES ON PROGRAMMING ATMEGA328P CHIPS

+ +

10 APRIL 2025

+ +
+ +

This post is a step-by-step guide for wiring up ATmega328P ICs to run at 5 V +with a 16 MHz crystal and 3.3 V with an 8 MHz crystal. While the 5 V +configuration is common, the 3.3 V configuration can be advantageous in +low-power applications and when interfacing with parts that run at 3.3 V.

+ +

5 V - 16 MHz configuration

+ +

The steps that follow refer to the following pinout.

+ + + + + + +

Pinout

Breadboard

+ +

Connect pin 1 to 5 V via a 10 kΩ resistor.
Connect a 16 MHz crystal oscillator across pins 9 and 10.
Connect each pin of the crystal to ground via 22 pF capacitors.
Connect pins 7, 20, and 21 to 5 V.
Connect pins 8 and 22 to ground.

+ +

In addition to the connections described above, it’s a good idea to add 0.1 μF +decoupling capacitors between pins 7, 20, and 21 and ground. +Here’s a sample Makefile for avr-gcc and avrdude.

+ +

3.3 V - 8 MHz configuration

+ +

The following steps use Arduino Uno as an ISP and Arduino utilities to program +ATmega328P’s bootloader and the fuses (e.g., BOD level) for a 3.3 V supply.

+ +

Upload the ‘ArduinoISP’ sketch to the Uno.
Wire up the ATmega328P as described in the previous section. Replace the 5 V +supply with a 3.3 V supply and use an 8 MHz crystal instead of the 16 MHz +crystal.
Connect the SPI ports (SCK, MISO, and MOSI) of the two MCUs.
Connect Uno’s SS pin to the IC’s pin 1 (RESET).
The IC can be powered by the Arduino Uno’s 5 V pin.
Burn the bootloader to the ATmega328P: +
- Select ‘ATmega328P (3.3 V, 8 MHz)’ from Tools > Processor.
- Select ‘Arduino as ISP’ from Tools > Programmer.
- Select Tools > Burn Bootloader.
+

+ +

The ATmega328P is now ready to run at 8 MHz with a 3.3 V power supply. You can +upload programs to the ATmega328P as you usually would using avrdude. +Here’s a sample Makefile with adjusted parameters (e.g., baud +rate) for an 8 MHz clock.

+ +

In both configurations, if you intend to use the ATmega328P’s analog-to-digital +converter with the internal 1.1 V or AV_cc voltage as reference, do +not connect AREF (pin 21) to V_cc. Refer to section 23.5.2 ADC +Voltage Reference in the datasheet for more information.

+ +

by W. D. Sadeep Madurange

AWESOME BOOKS

+ +

20 APRIL 2025

+ +
+ +

This article contains a list of my favourite books.

+ +

Cloud Atlas

+ +

This highly creative novel rekindled my love of fiction. Cloud Atlas is a +collection of six tales linked across time. As the novel unfolds, each story +riffles over the previous ones, like a pack of playing cards.

+ +

Ender’s Game

+ +

In this sci-fi novel, Andrew “Ender” Wiggin, a young boy, is drafted to lead a +squad of young children in an offensive against an alien race. It’s a complex +story that touches upon various political and philosophical issues. Those +perceived as gifted by others (and alienated for it) will likely connect with +Ender.

+ +

Flowers for Algernon

+ +

This novel, written as a series of progress reports, tells the story of Charlie +Gordon, a developmentally disabled man who acquires superhuman cognitive +abilities through an experimental medical procedure. For some reason, I felt a +deep connection with Charlie. If I had to pick a favourite book on this list, +that would be this.

+ +

Dead Souls

+ +

Nikolai Gogol is one of the most original authors I’ve read. Dead Souls is the +story of Ivanovich Chichikov, a traveling merchant who trades dead serfs. +Instead of simply describing them, Gogol develops realistic characters in +minute detail by employing theatrical clashes between them.

+ +

The Overcoat

+ +

Gogol’s The Overcoat is one of the finest short stories I’ve read. Akaky +Akakievich, an impoverished government clerk, must buy a new overcoat. I +recommend reading Gogol before Dostoyevsky. What Gogol invented, Dostoyevsky +perfected.

+ +

Demons

+ +

After reading Demons, a story about an attempted revolution, I realized that +Dostoevsky’s reputation is well-deserved. Dostoyevsky was a great observer of +the human psyche. The depth with which he depicts his characters is +unparalleled. Demons is a book that anyone aspiring to bring about change +through revolution must read.

+ +

The Outsider

+ +

Camus’s quote, “In our society, any man who doesn’t cry at his mother’s funeral +is liable to be condemned to death,” summarizes the book quite well. To +appreciate the philosophical elements of this absurdist novel, you may also +want to check out The Myth of Sisyphus.

+ +

Frankenstein

+ +

I’m not sure why I found this story so charming. Perhaps it’s a deep-felt +empathy for Victor Frankenstein. Maybe it’s the rustic descriptions of places +I’d never seen. After reading the book, I traveled Frankenstein’s trail from +Germany through Lucerne, Geneva, and Scotland.

+ +

Strange Case of Dr Jekyll and Mr Hyde

+ +

The story of Dr Jekyll and Mr Hyde needs no introduction. I’m drawn to +Stevenson’s writing style the same way I am to Mary Shelley’s. Both writers +evoke deep feelings and paint vivid images using simple language. The economy +of their language lacks neither precision nor power. If I could write like any +author, I would choose Mary Shelley or Stevenson.

+ +

Brave New World and Nineteen Eighty-Four

+ +

Huxley’s Brave New World and Orwell’s 1984 are inseparable, visionary novels +that depict dystopian futures from two extremes. For some reason, I felt Brave +New World lacked something despite being the more prescient of the two. It may +be Orwell’s eloquence overshadowing Huxley’s brilliance. In any event, these +two books are more relevant today than they’ve ever been.

+ +

Memoirs of a Madman

+ +

Another one of Gogol’s brilliant short stories. Presented in the form of +Aksenty Ivanovich’s diary, the story documents the government clerk’s descent +into madness. His obsession with social status and self-aggrandizement leads +him on a trajectory of envy, wounded pride, and outright insanity.

+ +

by W. D. Sadeep Madurange

MOSFETS

+ +

22 JUNE 2025

+ +
+ +

Recently, I needed a low-power circuit for one of my battery-operated projects. +Much of the system’s power savings depended on its ability to switch off power +to components, such as servos, electronically when not needed. That’s how I +stumbled upon MOSFETs, transistors capable of controlling circuits operating at +voltages far above their own.

+ +

Acknowledgments

+ +

This article is a summary of what I learnt about using transistors as switches. +I’m not an electronics engineer, and this is not an authoritative guide. The +circuits in this post must be considered within the context in which I’ve used +them. All credits for the schematics belong to Simon Fitch.

+ +

Preamble

+ +

For a typical MOSFET-based switch, we can connect a GPIO pin of a +microcontroller to the gate of a logic-level N-channel MOSFET placed on the low +side of the load and tie the gate and the drain pins of the MOSFET with a +pull-down resistor. This would work as long as the power supplies of the +microcontroller and the load don’t share a common ground. Things become more +complicated when they do (e.g., controlling power to a component driven by the +same microcontroller).

+ +

In that scenario, the source potential visible to the load is the difference +between the gate and the threshold potentials of the MOSFET. For example, when +the gate and the threshold potentials are 3.3 V and 1.5 V, the potential the +load sees is 1.8 V. So, to use a low-side N-channel MOSFET, we need the gate +potential to be higher than the source potential, which may not always be +practical. The alternative would be a hide-side switch.

+ +

P-channel high-side switch

+ +

The following schematic shows how a high-side P-channel MOSFET (M1) could +switch power to a 6 V servo driven by a 3.3 V MCU.

+ +

P-channel high-side switching circuit

+ +

When the microcontroller outputs low, the M2 N-channel MOSFET stops conducting. +The R1 resistor pulls the gate of the M1 P-channel MOSFET up to +6 V, switching +the servo off. When the microcontroller outputs high on the GPIO pin, M2’s +source-drain connection starts conducting, causing M1’s gate potential to drop +to 0 V, which switches on power to the servo.

+ +

N-channel high-side switch

+ +

The P-channel high-side switch would be the typical architecture for our use +case. However, if we have access to a potential high enough to safely raise the +gate potential above the threshold such that their difference outputs the source +potential required to drive the load, we can switch on the high side using an +N-channel MOSFET:

+ +

N-channel high-side switching circuit

+ +

In the schematic, both M1 and M2 are N-channel MOSFETs. When the +microcontroller output is low, M2 stops conducting. This causes the M1’s gate +potential to rise above the threshold, turning the servo on. Conversely, a high +output on the GPIO line switches M2 on, which lowers M1’s gate potential. This +switches the servo off. The R2 pull-up resistor prevents the high impedance of +the output pins at power-up from switching the servo on.

+ +

Both topologies require M2 to act as a level converter between circuits +containing the microcontroller and the servo, converting between 0 V and +6 V +or +9 V. M2 is a low-power signal converter carrying less than a milliamp of +current. The gate-source threshold voltage of M2 must be lower than the MCU’s +supply voltage. 2N7000, 2N7002, and BSS138 are popular choices for M2.

+ +

The D1 flyback diodes used in the two topologies safeguard the MOSFET from +voltage spikes caused by inductive loads such as servos.

+ +

A BJT alternative

+ +

A Bipolar Junction Transistor (BJT) is a simpler, cheaper, and more widely +available type of transistor that can be used as a switch.

+ +

BJT architecture

+ +

In the schematic, when the MCU outputs high, Q2 starts conducting. Q2 amplifies +Q1’s base current. Unlike MOSFETs, which are voltage-driven, BJTs are driven by +base current. Resistors R3 and R4 must be chosen carefully to output the +desired base currents. “How to choose a +transistor as a switch” is an excellent guide on using BJTs as electronic +switches.

+ +

Which topology to choose?

+ +

The professional community appears to prefer MOSFETs over BJTs. MOSFETs are +more efficient when the switch is on. However, they are more challenging to +drive, especially with a 3.3 V MCU, due to the V_GS potentials +required to achieve specified R_DS(on) values (i.e., to turn them on +fully).

+ +

N-channel MOSFETs have lower on-resistance values, making them more efficient +than P-channel ones. They are also cheaper. However, they are harder to drive +on the high side as their gate potential must be higher than the source +potential. This often requires extra circuitry such as MOSFET drivers.

+ +

MY FIRST PCB

+ +

14 JULY 2025

+ +
+ +

In 2023, I started tinkering with DIY electronics as a hobby. Until now, I’ve +been using development boards like the Arduino Uno and ESP-32-WROOM so that I +can focus on the software. Recently, I decided to step outside of my comfort +zone and design a PCB from scratch for a door lock I’m working on.

+ +

The lock comprises two subsystems: a fingerprint sensor in front of the door +and a servo connected to the physical lock behind the door. The fingerprint +sensor authenticates the person and signals the servo behind the door to unlock +the door over an encrypted RF channel.

+ + + + + + + + + + +

+ + Footprint (front) +	+ + PCB (front) +
+ + Footprint (back) +	+ + PCB (back) +

+ +

The PCBs have two layers. A copper region serves as the ground plane. The 0.3 +mm wide 1 oz/ft² copper traces can carry up to 500 mA (the tracks +connecting the power source and the linear regulators have a width of 0.5 mm). +Both subsystems were functional. I was able to control the servo reliably using +the fingerprint sensor.

+ +

The designs aren’t without flaws, however. The main shortcoming of the circuits +is that they draw significant amounts of quiescent currents despite employing +sleep modes. The linear regulators were a poor choice as they dissipate too +much heat. The fingerprint sensor and the servo draw 13.8 mA (3.3 V) and 4.6 mA +(5 V) respectively, as long as they are connected to the power supply.

+ +

Although the circuit didn’t draw more than 200 mA without a load, the servo +under load could draw up to 600 mA. I’m sailing too close to the wind with 0.3 +mm copper traces. Instead, 0.4 mm wide 2 oz/ft² traces would have +been safer.

+ +

I’m working on improving the design to reduce idle current consumption and +extend the battery life. Despite its deficiencies, this was my first PCB +design, and I’m glad that it worked as well as it did. Custom PCB design marks +an important milestone in my DIY electronics journey.

+ +

Files: gerber_back.zip, gerber_front.zip, + source.tar.gz

+ +

by W. D. Sadeep Madurange

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 then-available shortest-path algorithms limited +our search to about 4,000 route points.

+ +

The fix led to my first contribution to an open-source project:

+ +

package org.neo4j.graphalgo.impl;
+
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+
+import org.neo4j.graphalgo.api.Graph;
+import org.neo4j.graphalgo.core.utils.ProgressLogger;
+import org.neo4j.graphalgo.core.utils.queue.IntPriorityQueue;
+import org.neo4j.graphalgo.core.utils.queue.SharedIntPriorityQueue;
+import org.neo4j.graphalgo.core.utils.traverse.SimpleBitSet;
+import org.neo4j.graphdb.Direction;
+import org.neo4j.graphdb.Node;
+import org.neo4j.kernel.internal.GraphDatabaseAPI;
+
+import com.carrotsearch.hppc.IntArrayDeque;
+import com.carrotsearch.hppc.IntDoubleMap;
+import com.carrotsearch.hppc.IntDoubleScatterMap;
+import com.carrotsearch.hppc.IntIntMap;
+import com.carrotsearch.hppc.IntIntScatterMap;
+
+public class ShortestPathAStar extends Algorithm<ShortestPathAStar> {
+    
+    private final GraphDatabaseAPI dbService;
+    private static final int PATH_END = -1;
+    
+    private Graph graph;
+    private final int nodeCount;
+    private IntDoubleMap gCosts;
+    private IntDoubleMap fCosts;
+    private double totalCost;
+    private IntPriorityQueue openNodes;
+    private IntIntMap path;
+    private IntArrayDeque shortestPath;
+    private SimpleBitSet closedNodes;
+    private final ProgressLogger progressLogger;
+    
+    public static final double NO_PATH_FOUND = -1.0;
+    
+    public ShortestPathAStar(
+        final Graph graph,
+        final GraphDatabaseAPI dbService) {
+
+        this.graph = graph;
+        this.dbService = dbService;
+
+        nodeCount = Math.toIntExact(graph.nodeCount());
+        gCosts = new IntDoubleScatterMap(nodeCount);
+        fCosts = new IntDoubleScatterMap(nodeCount);
+        openNodes = SharedIntPriorityQueue.min(
+            nodeCount,
+            fCosts,
+            Double.MAX_VALUE);
+        path = new IntIntScatterMap(nodeCount);
+        closedNodes = new SimpleBitSet(nodeCount);
+        shortestPath = new IntArrayDeque();
+        progressLogger = getProgressLogger();
+    }
+    
+    public ShortestPathAStar compute(
+        final long startNode,
+        final long goalNode,
+        final String propertyKeyLat,
+        final String propertyKeyLon,
+        final Direction direction) {
+
+        reset();
+
+        final int startNodeInternal = 
+            graph.toMappedNodeId(startNode);
+        final double startNodeLat =
+            getNodeCoordinate(startNodeInternal, propertyKeyLat);
+        final double startNodeLon = 
+            getNodeCoordinate(startNodeInternal, propertyKeyLon);
+
+        final int goalNodeInternal =
+            graph.toMappedNodeId(goalNode);
+        final double goalNodeLat = 
+            getNodeCoordinate(goalNodeInternal, propertyKeyLat);
+        final double goalNodeLon = 
+            getNodeCoordinate(goalNodeInternal, propertyKeyLon);
+
+        final double initialHeuristic = 
+            computeHeuristic(startNodeLat,
+                startNodeLon,
+                goalNodeLat,
+                goalNodeLon);
+
+        gCosts.put(startNodeInternal, 0.0);
+        fCosts.put(startNodeInternal, initialHeuristic);
+        openNodes.add(startNodeInternal, 0.0);
+
+        run(goalNodeInternal,
+            propertyKeyLat,
+            propertyKeyLon,
+            direction);
+
+        if (path.containsKey(goalNodeInternal)) {
+            totalCost = gCosts.get(goalNodeInternal);
+            int node = goalNodeInternal;
+            while (node != PATH_END) {
+                shortestPath.addFirst(node);
+                node = path.getOrDefault(node, PATH_END);
+            }
+        }
+        return this;
+    }
+    
+    private void run(
+        final int goalNodeId,
+        final String propertyKeyLat,
+        final String propertyKeyLon,
+        final Direction direction) {
+
+        final double goalLat = 
+            getNodeCoordinate(goalNodeId, propertyKeyLat);
+        final double goalLon =
+            getNodeCoordinate(goalNodeId, propertyKeyLon);
+
+        while (!openNodes.isEmpty() && running()) {
+            int currentNodeId = openNodes.pop();
+            if (currentNodeId == goalNodeId) {
+                return;
+            }
+
+            closedNodes.put(currentNodeId);
+
+            double currentNodeCost = 
+                this.gCosts.getOrDefault(
+                    currentNodeId, 
+                    Double.MAX_VALUE);
+
+            graph.forEachRelationship(
+                currentNodeId,
+                direction,
+                (source, target, relationshipId, weight) -> {
+                    double neighbourLat = 
+                        getNodeCoordinate(target, propertyKeyLat);
+                    double neighbourLon = 
+                        getNodeCoordinate(target, propertyKeyLon);
+                    double heuristic = 
+                        computeHeuristic(
+                            neighbourLat, 
+                            neighbourLon, 
+                            goalLat,
+                            goalLon);
+
+                    updateCosts(
+                        source,
+                        target,
+                        weight + currentNodeCost,
+                        heuristic);
+
+                    if (!closedNodes.contains(target)) {
+                        openNodes.add(target, 0);
+                    }
+                    return true;
+                });
+
+            progressLogger.logProgress(
+                (double) currentNodeId / (nodeCount - 1));
+        }
+    }
+    
+    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));
+        final double distance = earthRadius * c * kmToNM;
+        return distance;
+    }
+    
+    private double getNodeCoordinate(
+        final int nodeId,
+        final String coordinateType) {
+
+        final long neo4jId = graph.toOriginalNodeId(nodeId);
+        final Node node = dbService.getNodeById(neo4jId);
+        return (double) node.getProperty(coordinateType);
+    }
+    
+    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);
+        }
+    }
+    
+    private void reset() {
+        closedNodes.clear();
+        openNodes.clear();
+        gCosts.clear();
+        fCosts.clear();
+        path.clear();
+        shortestPath.clear();
+        totalCost = NO_PATH_FOUND;
+    }
+    
+    public Stream<Result> resultStream() {
+        return StreamSupport.stream(
+            shortestPath.spliterator(), false)
+                .map(cursor -> new Result(
+                    graph.toOriginalNodeId(cursor.value),
+                    gCosts.get(cursor.value)));
+    }
+
+    public IntArrayDeque getFinalPath() {
+        return shortestPath;
+    }
+    
+    public double getTotalCost() {
+        return totalCost;
+    }
+
+    public int getPathLength() {
+        return shortestPath.size();
+    }
+    
+    @Override
+    public ShortestPathAStar me() {
+        return this;
+    }
+
+    @Override
+    public ShortestPathAStar release() {
+        graph = null;
+        gCosts = null;
+        fCosts = null;
+        openNodes = null;
+        path = null;
+        shortestPath = null;
+        closedNodes = null;
+        return this;
+    }
+    
+    public static class Result {
+
+        /**
+         * the neo4j node id
+         */
+        public final Long nodeId;
+
+        /**
+         * cost to reach the node from startNode
+         */
+        public final Double cost;
+
+        public Result(Long nodeId, Double cost) {
+            this.nodeId = nodeId;
+            this.cost = cost;
+        }
+    }
+}
+

+ +

If you are new to them, a graph is a finite set of vertices (such as ports +ships are known to travel through), and a subset of vertex pairs (such as +origin and destination ports) known as edges.

+ +

Edges can have weights. In the case of ships and ports, the weights could be +the distances between ports. For various 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.

+ +

There’s nothing spectacular about the code. It is, for the most part, a patch +over Dijkstra’s algorithm that employs spherical distance between vertices as a +heuristic to steer the search in the right direction. Dijkstra’s algorithm, on +the other hand, explores all possible paths from the source, which is what +makes it slower.

+ +

The heuristic function is domain-specific. I planned to make it configurable, +but didn’t get around to it. With the help of my A* algorithm, we scaled our +search to include all the route points of interest. <a +href=”https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0” +class=”external” target=”_blank” rel=”noopener noreferrer>Here’s</a> a link to +the now-archived official release.

+ +

by Wickramage Don Sadeep Madurange