GQL API

Cheapest Paths

Overview

Cheapest paths between two nodes are those that minimize the sum of weights/costs of the traversed edges. Unlike shortest paths (which minimize the number of hops), cheapest paths use a weighted algorithm (Dijkstra's search) to find the path with the lowest cumulative cost. A cheapest path may therefore involve more edges than the shortest path.

When a cheapest path selector is used, the path mode defaults to TRAIL (no repeated edges).

Cheapest Path Selectors

Selector Description
ALL CHEAPEST Selects all cheapest paths from each partition.
ANY CHEAPEST Selects exactly one cheapest path from each partition.
CHEAPEST Equivalent to ANY CHEAPEST. Returns one cheapest path.
CHEAPEST k Selects up to k cheapest paths from each partition, proceeding to the next cheapest if a partition has fewer than k paths at the minimum cost.

The COST Clause

To calculate the path cost, you must include a COST clause inside the edge pattern. The COST clause specifies the per-edge weight expression. 

-- Syntax
-[ edge_variable [ label_expression ] COST value_expression ]->
Rules:
  • The COST clause cannot be combined with property specifications (curly braces {}) or inline WHERE clauses in the same edge pattern.
  • The value_expression can reference edge properties, use arithmetic operators (e.g. e.prop1 + e.prop2), or use constant values.
  • Negative edge costs are permitted.

Examples

1. Minimizing Mana Cost (CHEAPEST)

Find the cheapest path from "Albus" to "Luna" across 1 to 5 AlliedWith edges, minimizing the total mana_cost:

MATCH p = CHEAPEST (a:Wizard {name: "Albus"})-[e:AlliedWith COST e.mana_cost]->{1,5}(d:Wizard {name: "Luna"})
RETURN p

2. Combined Cost Formula (ALL CHEAPEST)

Find the path that minimizes the net cost of mana, subtracting the affinity boost (utility) of each channel: 

MATCH p = ALL CHEAPEST (a:Wizard {name: "Albus"})-[e:AlliedWith COST e.mana_cost - e.affinity_boost]->{1,5}(d:Wizard {name: "Luna"})
RETURN p

3. Constant Cost Degeneracy

Providing a constant cost of 1 per edge forces Dijkstra's algorithm to behave like standard BFS, finding the path with the fewest hops: 

MATCH p = CHEAPEST (a:Wizard {name: "Albus"})-[e:AlliedWith COST 1]->{1,5}(d:Wizard {name: "Luna"})
RETURN p