HelixDB Docs

Find Shortest Paths with A* Algorithm

ShortestPathAStar uses the A* (A-star) algorithm to find optimal shortest paths in weighted graphs. It combines the precision of Dijkstra’s algorithm with heuristic guidance to dramatically improve performance, especially for long-distance pathfinding in spatial graphs.

::ShortestPathAStar<EdgeType>(weight_expression, "heuristic_property")
::To(target_id)

When using the SDKs or curling the endpoint, the query name must match what is defined in the queries.hx file exactly.

How It Works

A* combines two costs:

g(n): Actual cost from start to current node (like Dijkstra)
h(n): Heuristic estimate from current node to goal

The algorithm prioritizes nodes with the lowest f(n) = g(n) + h(n), guiding search toward the target.

The heuristic must be admissible (never overestimate the true cost) to guarantee finding the optimal path. Common admissibles include straight-line distance for geographic routing.

When to Use A*

A* is ideal when:

Spatial graphs: Nodes have geographic or coordinate-based positions
Long paths: Target is far from source (A* excels here)
Goal-directed: You know the general direction to the target
Performance critical: Need faster results than Dijkstra
Admissible heuristic available: You have a property that estimates remaining cost

When A* Outperforms Dijkstra

A* can be significantly faster than Dijkstra when:

The heuristic effectively guides search toward the target
The graph is large and sparse
The path length is substantial
Node coordinates or positions are available

In these scenarios, A* can be 10-100x faster by avoiding exploration of irrelevant areas.

Heuristic Requirements

The heuristic property must:

Be stored on each node
Estimate cost to reach the target
Never overestimate (admissible)
Be consistent across the graph

Common heuristics:

Straight-line distance: For geographic graphs
Manhattan distance: For grid-based graphs
Euclidean distance: For coordinate-based graphs

Example 1: Geographic routing with straight-line distance heuristic

QUERY FindFastestRoute(start_id: ID, end_id: ID) =>
    result <- N<City>(start_id)
        ::ShortestPathAStar<Highway>(_::{distance}, "straight_line_distance")
        ::To(end_id)
    RETURN result

QUERY CreateCity(name: String, latitude: F64, longitude: F64, straight_line_dist: F64) =>
    city <- CREATE V<City> {
        name: name,
        latitude: latitude,
        longitude: longitude,
        straight_line_distance: straight_line_dist
    }
    RETURN city

QUERY CreateHighway(from_id: ID, to_id: ID, distance: F64) =>
    highway <- CREATE E<Highway>(from_id, to_id) { distance: distance }
    RETURN highway

Here’s how to run the query using the SDKs or curl

from helix.client import Client
import math

client = Client(local=True, port=6969)

# City coordinates (simplified for example)
city_coords = {
    "Seattle": (47.6, -122.3),
    "Portland": (45.5, -122.7),
    "San Francisco": (37.8, -122.4),
    "Los Angeles": (34.0, -118.2),
}

# Target city for heuristic calculation
target = "Los Angeles"
target_lat, target_lon = city_coords[target]

# Calculate straight-line distance heuristic
def calc_heuristic(lat1, lon1, lat2, lon2):
    # Simplified distance calculation (in practice, use haversine)
    return math.sqrt((lat2 - lat1)**2 + (lon2 - lon1)**2) * 69.0  # ~69 miles per degree

# Create cities with heuristic values
cities = {}
for name, (lat, lon) in city_coords.items():
    heuristic = calc_heuristic(lat, lon, target_lat, target_lon)
    result = client.query("CreateCity", {
        "name": name,
        "latitude": lat,
        "longitude": lon,
        "straight_line_dist": heuristic
    })
    cities[name] = result["city"]["id"]

# Create highway network with actual distances
highways = [
    ("Seattle", "Portland", 174.0),
    ("Portland", "San Francisco", 635.0),
    ("San Francisco", "Los Angeles", 383.0),
    ("Seattle", "San Francisco", 808.0),  # Alternative route
]

for from_city, to_city, distance in highways:
    client.query("CreateHighway", {
        "from_id": cities[from_city],
        "to_id": cities[to_city],
        "distance": distance
    })

# Find fastest route using A*
result = client.query("FindFastestRoute", {
    "start_id": cities["Seattle"],
    "end_id": cities["Los Angeles"]
})

print(f"A* route from Seattle to Los Angeles:")
print(f"Path: {' -> '.join([node['name'] for node in result['result']['path']])}")
print(f"Total distance: {result['result']['total_weight']:.1f} miles")
print(f"Hops: {result['result']['hop_count']}")

Example 2: Time-optimized routing with traffic-aware weights

QUERY FindQuickestRoute(start_id: ID, end_id: ID) =>
    result <- N<Junction>(start_id)
        ::ShortestPathAStar<Road>(MUL(_::{distance}, _::{traffic_multiplier}), "estimated_time_remaining")
        ::To(end_id)
    RETURN result

QUERY CreateJunction(name: String, est_time: F64) =>
    junction <- CREATE V<Junction> {
        name: name,
        estimated_time_remaining: est_time
    }
    RETURN junction

QUERY CreateRoad(from_id: ID, to_id: ID, distance: F64, traffic_mult: F64) =>
    road <- CREATE E<Road>(from_id, to_id) {
        distance: distance,
        traffic_multiplier: traffic_mult
    }
    RETURN road

Here’s how to run the query using the SDKs or curl

from helix.client import Client

client = Client(local=True, port=6969)

# Create junctions with time-to-destination heuristic
junctions = {}
junction_data = [
    ("J1", 45.0),  # 45 min estimated to destination
    ("J2", 30.0),
    ("J3", 20.0),
    ("J4", 10.0),
    ("Destination", 0.0),
]

for name, est_time in junction_data:
    result = client.query("CreateJunction", {
        "name": name,
        "est_time": est_time
    })
    junctions[name] = result["junction"]["id"]

# Create roads with distance and current traffic
# Weight = distance * traffic_multiplier (estimates time)
roads = [
    ("J1", "J2", 10.0, 1.5),  # Heavy traffic
    ("J1", "J3", 15.0, 1.0),  # Normal traffic
    ("J2", "J4", 12.0, 1.2),
    ("J3", "J4", 8.0, 1.0),
    ("J4", "Destination", 5.0, 1.0),
]

for from_junc, to_junc, distance, traffic in roads:
    client.query("CreateRoad", {
        "from_id": junctions[from_junc],
        "to_id": junctions[to_junc],
        "distance": distance,
        "traffic_mult": traffic
    })

# Find quickest route considering traffic
result = client.query("FindQuickestRoute", {
    "start_id": junctions["J1"],
    "end_id": junctions["Destination"]
})

print(f"Quickest route from J1 to Destination:")
print(f"Path: {' -> '.join([node['name'] for node in result['result']['path']])}")
print(f"Estimated time: {result['result']['total_weight']:.1f} minutes")

Admissible Heuristics

For A* to guarantee optimal results, the heuristic must be admissible:

Good Heuristics (Admissible)

Straight-line distance: Always ≤ actual road distance
Manhattan distance: For grid-based movement
Minimum theoretical time: Based on maximum speed limits

Bad Heuristics (Inadmissible)

Overestimated distances: May miss optimal path
Random values: No guarantee of optimality
Negative values: Breaks the algorithm

Using an inadmissible heuristic may cause A* to return suboptimal paths. Always ensure your heuristic never overestimates the true remaining cost.

Performance Comparison

Scenario	Dijkstra	A* with Good Heuristic
Small graph (< 100 nodes)	Fast	Similar
Large graph (> 10,000 nodes)	Slow	10-100x faster
Short paths	Fast	Similar
Long paths	Slow	Much faster
No spatial info	Only option	Not applicable
Spatial graph	Explores everything	Explores targeted area

Result Structure

A* returns the same structure as Dijkstra:

{
    path: [Node],           // Ordered list of nodes from start to end
    edges: [Edge],          // Ordered list of edges connecting nodes
    total_weight: F64,      // Total actual weight (not heuristic)
    hop_count: I64          // Number of edges in path
}

Best Practices

Pre-calculate Heuristics

For static targets, pre-calculate and store heuristic values:

// Pre-calculate straight-line distance to common destinations
V::City {
    distance_to_hub: F64,
    distance_to_airport: F64
}

Choose the Right Heuristic

Geographic graphs: Use haversine or Euclidean distance
Grid graphs: Use Manhattan distance
Time-based: Use minimum theoretical time

Verify Admissibility

Test that your heuristic never overestimates:

For all nodes n: h(n) ≤ actual_cost(n, target)

ShortestPathDijkstras

Learn about Dijkstra’s algorithm (A* without heuristic)

Custom Weights

Property contexts for weight calculations

Weight Expressions

Advanced mathematical weight expressions

Overview

Compare all shortest path algorithms

HelixQL

​Find Shortest Paths with A* Algorithm

​How It Works

​When to Use A*

​When A* Outperforms Dijkstra

​Heuristic Requirements

​Example 1: Geographic routing with straight-line distance heuristic

​Example 2: Time-optimized routing with traffic-aware weights

​Admissible Heuristics

​Good Heuristics (Admissible)

​Bad Heuristics (Inadmissible)

​Performance Comparison

​Result Structure

​Best Practices

​Pre-calculate Heuristics

​Choose the Right Heuristic

​Verify Admissibility

​Related Topics

ShortestPathDijkstras

Custom Weights

Weight Expressions

Overview

Find Shortest Paths with A* Algorithm

How It Works

When to Use A*

When A* Outperforms Dijkstra

Heuristic Requirements

Example 1: Geographic routing with straight-line distance heuristic

Example 2: Time-optimized routing with traffic-aware weights

Admissible Heuristics

Good Heuristics (Admissible)

Bad Heuristics (Inadmissible)

Performance Comparison

Result Structure

Best Practices

Pre-calculate Heuristics

Choose the Right Heuristic

Verify Admissibility

Related Topics