Skip to main content

​
Shortest Path Algorithms

HelixDB provides multiple algorithms for finding shortest paths between nodes:

​
::ShortestPath (BFS - Default)

Breadth-first search finds the minimum number of hops between nodes along a specific edge type. This is the default algorithm for backward compatibility. 
::ShortestPath<EdgeType>::To(to_id: ID)
::ShortestPath<EdgeType>::From(from_id: ID)

​
::ShortestPathBFS (Explicit BFS)

Explicitly use breadth-first search to find the path with minimum hops. 
::ShortestPathBFS<EdgeType>::To(to_id: ID)
::ShortestPathBFS<EdgeType>::From(from_id: ID)

​
::ShortestPathDijkstras (Weighted)

Dijkstra’s algorithm finds the path with minimum total weight by summing edge weights. Requires specifying which edge property to use as weight. 
::ShortestPathDijkstras<EdgeType>(_::{weight_property})::To(to_id: ID)
::ShortestPathDijkstras<EdgeType>(_::{weight_property})::From(from_id: ID)
Note: Edge weights must be numeric (integers or floats) and non-negative. Future Enhancement: In upcoming releases, you will be able to specify custom formulas for weight calculation instead of just property names. This will enable complex weighting based on traversals, calculations, or combinations of multiple properties.

​
Algorithm Selection

Choose the appropriate algorithm based on your use case:
AlgorithmUse CaseOptimizes ForEdge Weights
ShortestPath (BFS)Social networks, network hops, simple routingMinimum number of edges/hopsIgnored
ShortestPathBFSSame as above (explicit)Minimum number of edges/hopsIgnored
ShortestPathDijkstrasGPS routing, cost optimization, weighted graphsMinimum total weight/costRequired

​
Examples

​
Example 1: BFS vs Dijkstra comparison

This example demonstrates the difference between BFS (minimum hops) and Dijkstra’s algorithm (minimum weight). 
// BFS finds path with minimum hops (default behavior)
QUERY GetShortestPathBFS (from_id: ID, to_id: ID) =>
    path <- N<City>(from_id)::ShortestPath<Road>::To(to_id)
    RETURN path

// Explicit BFS (same as above)
QUERY GetShortestPathBFSExplicit (from_id: ID, to_id: ID) =>
    path <- N<City>(from_id)::ShortestPathBFS<Road>::To(to_id)
    RETURN path

// Dijkstra finds path with minimum total distance
QUERY GetShortestPathDijkstra (from_id: ID, to_id: ID) =>
    path <- N<City>(from_id)::ShortestPathDijkstras<Road>(_::{distance_km})::To(to_id)
    RETURN path

QUERY CreateCity (name: String) =>
    city <- AddN<City>({name: name})
    RETURN city

QUERY ConnectCities (from_id: ID, to_id: ID, distance_km: F64) =>
    road <- AddE<Road>({
        distance_km: distance_km,
    })::From(from_id)::To(to_id)
    RETURN road
Consider this graph:
  • City A → City B (distance: 100km, 1 hop)
  • City A → City C → City B (distance: 30km + 40km = 70km, 2 hops)
BFS will choose A → B (1 hop, shorter path by hop count) Dijkstra will choose A → C → B (70km total, shorter path by weight)

​
Example 2: Finding routes between locations

QUERY GetShortestPath (from_id: ID, to_id: ID) =>
    path <- N<Location>(from_id)::ShortestPath<Road>::To(to_id)
    RETURN path

QUERY CreateLocation (name: String) =>
    location <- AddN<Location>({
        name: name,
    })
    RETURN location

QUERY ConnectLocations (from_id: ID, to_id: ID, distance_km: U32) =>
    road <- AddE<Road>({
        distance_km: distance_km,
    })::From(from_id)::To(to_id)
    RETURN road

from helix.client import Client

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

central = client.query("CreateLocation", {"name": "Central Station"})
market = client.query("CreateLocation", {"name": "Market Square"})
harbor = client.query("CreateLocation", {"name": "Harbor"})

central_id = central[0]["location"]["id"]
market_id = market[0]["location"]["id"]
harbor_id = harbor[0]["location"]["id"]

client.query("ConnectLocations", {
    "from_id": central_id,
    "to_id": market_id,
    "distance_km": 2,
})
client.query("ConnectLocations", {
    "from_id": market_id,
    "to_id": harbor_id,
    "distance_km": 3,
})

result = client.query("GetShortestPath", {
    "from_id": central_id,
    "to_id": harbor_id,
})
print(result)

​
Return Type

[([Nodes], [Edges])]
The shortest-path result is an array of tuples because multiple equally short routes can be returned.
⌘I