Pathfinding

Pathfinding

BFS, Dijkstra, A* — graph routing built into the database.

Why it matters

Pathfinding is the canonical first GDS algorithm — once you can compute shortest paths inside the DB you can answer routing, supply-chain and fraud questions without exporting.

Going deeper

Pick by what 'shortest' means and what you know:

MATCH (a:Stop {name:$from}), (b:Stop {name:$to})
CALL gds.shortestPath.dijkstra.stream('transit', {
  sourceNode: a, targetNode: b, relationshipWeightProperty: 'minutes'
}) YIELD totalCost, nodeIds
RETURN totalCost;

Doing this inside the database answers routing, supply-chain and fraud questions without exporting the topology. A* only beats Dijkstra when you have a heuristic that never overestimates the remaining cost — otherwise it can return a wrong path.

Pathfinding algorithms are three kinds of navigator. BFS is a tourist counting streets to the museum (fewest hops, all streets equal). Dijkstra is a taxi meter minimizing fare (real edge weights). A* is a taxi driver who also knows roughly which direction the museum is (a heuristic) and so explores fewer wrong turns. Same city, different definition of 'shortest'.

• Dijkstra with negative weights. Produces wrong results. Fix: BFS, or transform weights to be non-negative.
• A* with an inadmissible heuristic. Can return a non-shortest path. Fix: use a heuristic that never overestimates.
• Unweighted shortest path via Dijkstra. Overkill. Fix: BFS when all edges are equal.