ShortestPathBFS

Find unweighted shortest paths using breadth-first search.

Find Unweighted Shortest Paths with BFS  

ShortestPathBFS uses breadth-first search to find the shortest path between nodes when all edges have equal weight. It’s the fastest algorithm for unweighted graphs and is ideal when you care about minimizing the number of hops rather than total distance or cost.

::ShortestPathBFS<EdgeType>
::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

BFS explores the graph level by level:

1. Start from the source node
2. Visit all neighbors at distance 1
3. Then visit all neighbors at distance 2
4. Continue until the target is found

This guarantees finding the path with the minimum number of edges (hops).

When to Use ShortestPathBFS

Use BFS when you want to:

• Minimize hop count: Find paths with the fewest edges
• Equal edge importance: All edges are equally significant
• Social network analysis: Find degrees of separation
• Network routing: Minimize number of router hops
• Fast performance: Need the fastest shortest path algorithm

If edges have different weights (distance, cost, time), use ShortestPathDijkstras instead.

Example 1: Basic shortest path by hop count

Query

QUERY FindShortestPath(start_id: ID, end_id: ID) =>
    result <- N<City>(start_id)
        ::ShortestPathBFS<Road>
        ::To(end_id)
    RETURN result

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

QUERY ConnectCities(from_id: ID, to_id: ID) =>
    road <- AddE<Road>::From(from_id)::To(to_id)
    RETURN road

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

Python

from helix.client import Client

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

# Create cities
cities = {}
for city_name in ["New York", "Boston", "Philadelphia", "Washington DC", "Baltimore"]:
    result = client.query("CreateNetwork", {"city_name": city_name})
    cities[city_name] = result["city"]["id"]

# Create road network
connections = [
    ("New York", "Boston"),
    ("New York", "Philadelphia"),
    ("Philadelphia", "Washington DC"),
    ("Philadelphia", "Baltimore"),
    ("Baltimore", "Washington DC"),
]

for from_city, to_city in connections:
    client.query("ConnectCities", {
        "from_id": cities[from_city],
        "to_id": cities[to_city]
    })

# Find shortest path
result = client.query("FindShortestPath", {
    "start_id": cities["New York"],
    "end_id": cities["Washington DC"]
})

print(f"Path from New York to Washington DC:")
print(f"Cities: {[node['name'] for node in result['path']]}")
print(f"Hop count: {result['hop_count']}")

---

Example 2: Social network degree of separation

Query

QUERY FindConnection(person1_id: ID, person2_id: ID) =>
    connection <- N<Person>(person1_id)
        ::ShortestPathBFS<Knows>
        ::To(person2_id)
    RETURN connection

QUERY CreatePerson(name: String) =>
    person <- AddN<Person>({ name: name })
    RETURN person

QUERY CreateFriendship(from_id: ID, to_id: ID) =>
    knows <- AddE<Knows>::From(from_id)::To(to_id)
    RETURN knows

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

Python

from helix.client import Client

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

# Create people
people = {}
for name in ["Alice", "Bob", "Carol", "Dave", "Eve", "Frank"]:
    result = client.query("CreatePerson", {"name": name})
    people[name] = result["person"]["id"]

# Create friendship network
friendships = [
    ("Alice", "Bob"),
    ("Bob", "Carol"),
    ("Carol", "Dave"),
    ("Alice", "Eve"),
    ("Eve", "Frank"),
    ("Frank", "Dave"),
]

for person1, person2 in friendships:
    client.query("CreateFriendship", {
        "from_id": people[person1],
        "to_id": people[person2]
    })

# Find shortest connection
result = client.query("FindConnection", {
    "person1_id": people["Alice"],
    "person2_id": people["Dave"]
})

print(f"Connection from Alice to Dave:")
print(f"Path: {' -> '.join([node['name'] for node in result['connection']['path']])}")
print(f"Degrees of separation: {result['connection']['hop_count']}")

---

Result Structure

ShortestPathBFS returns a result containing:

{
    path: [Node],           // Ordered list of nodes from start to end
    edges: [Edge],          // Ordered list of edges connecting the nodes
    total_weight: F64,      // Always equals hop_count for BFS
    hop_count: I64          // Number of edges in the path
}

Performance Characteristics

• Time Complexity: O(V + E) where V is vertices and E is edges
• Space Complexity: O(V) for tracking visited nodes
• Guarantee: Always finds the shortest path by hop count
• Best Case: Target is a direct neighbor (1 hop)
• Worst Case: Target requires exploring entire graph

BFS is the fastest shortest path algorithm for unweighted graphs. For weighted graphs, it may not find the optimal path.

Related Topics

ShortestPathDijkstras

Find weighted shortest paths with custom calculations

ShortestPathAStar

Heuristic-guided pathfinding

Overview

Compare all shortest path algorithms

Graph Traversals

Other traversal operations