# Projected pathfinding

[Wiki](../README.md) / [Graph data science](README.md)

## Projected pathfinding

Use an existing [projection](projections.md); the source and targets must be
selected projected nodes. See [modes](algorithms.md) for write/mutate configuration.

- `gds.shortestPath.dijkstra`
- `gds.shortestPath.astar`
- `gds.shortestPath.yens`
- `gds.allShortestPaths.dijkstra` (single-source distances/paths)
- `gdb.shortestPath.hourglass` (Galactus; see [Hourglass](#hourglass))

Each has `stream`, `stats`, `write` and `mutate` entry points. Specify
`sourceNode`, `targetNode` or `targetNodes`, and optionally
`relationshipWeightProperty`. The single-source procedure visits every reachable
target using a single Dijkstra tree, also reused for multi-target Dijkstra.
Dijkstra with a single `targetNode` stops as soon as it reaches the target, and
each projection keeps the weighted adjacency it builds for later calls (from
version 2.1.8).
Returned paths still require memory proportional to their total length.
Yen additionally takes positive `k` and enumerates distinct simple node
paths in cost order. Parallel edges with the same endpoints are not treated as
separate Yen paths. A* needs a location for every projected node: either numeric
`latitudeProperty` and `longitudeProperty`, or `pointProperty` naming a
`Point`, `Geometry` or `Geography` POINT property (one or the other, not both;
all geographic or all cartesian; `pointProperty` from version 1.6.2). Its
straight-line heuristic is scaled to the
cheapest cost per unit of distance over all edges, so weights in any unit
cannot invalidate shortest-path correctness.

Stream columns are `index, sourceNode, targetNode, totalCost, nodeIds, costs,
path`. Paths use virtual `PATH` relationships with per-step costs. Unreachable
targets return no row. A source equal to its target returns a zero-cost path.
Write/mutate create source-to-target summary relationships, with the property
defaulting to `totalCost`; they do not rewrite the traversed relationships.

## Hourglass

`gdb.shortestPath.hourglass` is Ian Knowles's exact point-to-point algorithm
([paper and reference code](https://github.com/ikcore/hourglass-research), MIT).
It searches from both ends at once, leans both searches towards each other
with whole-number potentials built from the straight-line distance, and keeps
its frontiers in bucket rings instead of a sorted heap. It has the same
`stream`, `stats`, `write` and `mutate` modes, configuration and columns as A*. From
version 1.6.2.

```cypher
MATCH (a:City {name:'Exeter'}), (b:City {name:'Newcastle'})
CALL gdb.shortestPath.hourglass.stream('roads', {
  sourceNode: a, targetNode: b,
  relationshipWeightProperty: 'km', pointProperty: 'loc'
})
YIELD totalCost, nodeIds
RETURN totalCost, nodeIds;
```

- Relationship weights must be whole numbers from 0 to 2^40. Use Dijkstra or
  A* for fractional weights.
- A location (`pointProperty`, or `latitudeProperty` with `longitudeProperty`)
  is optional. Without one it is a bidirectional bucket search, still exact.
- Directed projections are supported: the backward search follows the
  relationships in reverse.
- When `4 × max weight + 1` exceeds 65,536 buckets, the frontiers use a heap
  instead of a ring; the answer is the same.
- `nodeIds` are plain IDs. To get the nodes back, for example to draw the
  route, use `gds.util.asNodes(nodeIds)`.

## Related articles

[Graph projections and catalogue](projections.md) · [GDS algorithms and execution modes](algorithms.md) · [GDS resources and cancellation](resources.md) · [Graph data science](README.md)
