Path Finding Algorithms

Overview

Path finding algorithms discover routes between nodes. Different algorithms optimize for different criteria:

Note: GQL also provides native path syntax using SHORTEST/ALL SHORTEST in MATCH patterns.

BFS & DFS Traversal

Breadth-First Search (BFS) explores neighbors level by level, finding shortest paths by hop count. Depth-First Search (DFS) explores as deep as possible before backtracking.

BFS shortest path (unweighted):

GQL
CALL algo.bfs('Person', 'KNOWS', {
  sourceNode: 'Alice',
  targetNode: 'Eve'
})
YIELD path, distance
RETURN path, distance

Native GQL shortest path (preferred):

GQL
MATCH p = SHORTEST 1 (a:Person WHERE a.name = 'Alice')
          -[:KNOWS]-{1,10}
          (e:Person WHERE e.name = 'Eve')
RETURN p, LENGTH(p) AS hops

DFS to find all paths:

GQL
CALL algo.dfs('Person', 'KNOWS', {
  sourceNode: 'Alice',
  targetNode: 'Eve',
  maxDepth: 5
})
YIELD path
RETURN path
LIMIT 10

BFS with max depth:

GQL
CALL algo.bfs.stream('Person', 'KNOWS', {
  sourceNode: 'Alice',
  maxDepth: 3
})
YIELD nodeId, distance
MATCH (p:Person) WHERE id(p) = nodeId
RETURN p.name, distance
ORDER BY distance

Dijkstra Shortest Path

Dijkstra's algorithm finds the shortest weighted path between nodes. Essential for routing, logistics, and network optimization.

Shortest weighted path:

GQL
MATCH (start:City {name: 'New York'})
MATCH (end:City {name: 'Los Angeles'})
CALL algo.dijkstra(start, end, 'distance')
YIELD path, totalCost
RETURN [n IN NODES(path) | n.name] AS route, totalCost AS miles

Multiple weighted paths:

GQL
MATCH (start:City {name: 'Boston'})
MATCH (end:City {name: 'Seattle'})
CALL algo.dijkstra.stream(start, end, 'travelTime', {
  pathCount: 3
})
YIELD path, totalCost
RETURN [n IN NODES(path) | n.name] AS route,
       totalCost AS hours

Single source shortest paths (to all nodes):

GQL
MATCH (start:City {name: 'Chicago'})
CALL algo.dijkstra.singleSource(start, 'distance')
YIELD nodeId, totalCost
MATCH (city:City) WHERE id(city) = nodeId
RETURN city.name, totalCost AS distanceFromChicago
ORDER BY totalCost

With edge filter:

GQL
MATCH (start:City {name: 'Miami'})
MATCH (end:City {name: 'Seattle'})
CALL algo.dijkstra(start, end, 'distance', {
  relationshipTypes: ['HIGHWAY', 'INTERSTATE'],
  direction: 'BOTH'
})
YIELD path, totalCost
RETURN path, totalCost

Cost-optimized routing:

GQL
MATCH (warehouse:Location {type: 'warehouse'})
MATCH (customer:Location {type: 'customer', id: 'C123'})
CALL algo.dijkstra(warehouse, customer, 'deliveryCost')
YIELD path, totalCost
RETURN warehouse.name, totalCost AS cost,
       LENGTH(path) AS stops

All Shortest Paths

When multiple paths have the same length, you may want all of them. Native GQL syntax and algorithms both support this.

Native GQL all shortest paths:

GQL
MATCH p = ALL SHORTEST (a:Person WHERE a.name = 'Alice')
          -[:KNOWS]-{1,10}
          (e:Person WHERE e.name = 'Eve')
RETURN p, LENGTH(p) AS hops

Algorithm-based all shortest paths:

GQL
MATCH (start:Person {name: 'Alice'})
MATCH (end:Person {name: 'Eve'})
CALL algo.allShortestPaths(start, end, 'KNOWS')
YIELD path
RETURN [n IN NODES(path) | n.name] AS route
LIMIT 10

All weighted shortest paths:

GQL
MATCH (start:City {name: 'Boston'})
MATCH (end:City {name: 'Phoenix'})
CALL algo.dijkstra.allShortestPaths(start, end, 'distance')
YIELD path, totalCost
RETURN [n IN NODES(path) | n.name] AS route, totalCost

K shortest paths (allowing longer alternatives):

GQL
MATCH (start:City {name: 'Seattle'})
MATCH (end:City {name: 'Miami'})
CALL algo.kShortestPaths(start, end, 'distance', {k: 5})
YIELD path, totalCost, rank
RETURN rank, [n IN NODES(path) | n.name] AS route, totalCost

A* Algorithm

A* is an informed search algorithm that uses a heuristic to guide the search toward the target, making it faster than Dijkstra for geographic routing.

A* with geographic heuristic:

GQL
MATCH (start:City {name: 'New York'})
MATCH (end:City {name: 'San Francisco'})
CALL algo.astar(start, end, 'distance', {
  latitudeProperty: 'lat',
  longitudeProperty: 'lon'
})
YIELD path, totalCost
RETURN [n IN NODES(path) | n.name] AS route, totalCost

A* for game pathfinding (grid-based):

GQL
MATCH (start:Tile {x: 0, y: 0})
MATCH (end:Tile {x: 10, y: 10})
CALL algo.astar(start, end, 'movementCost', {
  heuristic: 'manhattan',
  xProperty: 'x',
  yProperty: 'y'
})
YIELD path, totalCost
RETURN LENGTH(path) AS steps, totalCost