Path Finding

algo.dijkstra

Property Value

Procedure

algo.dijkstra

Category

Path Finding

Complexity

CPU

Min Args

4

Max Args

5

Syntax

CALL algo.dijkstra(startNode, endNode, relTypes, weightProperty [, direction])
YIELD path, weight

Parameters

Parameter Type Required Default Description

startNode

Vertex

Yes

—

Source vertex

endNode

Vertex

Yes

—

Destination vertex

relTypes

String

Yes

—

Comma-separated relationship types; pass '' for all types

weightProperty

String

Yes

—

Edge property name to use as weight

direction

String

No

"BOTH"

Traversal direction: "IN", "OUT", or "BOTH"

Yield Fields

Field Type Description

path

List<RID>

Ordered list of vertex identities on the shortest path

weight

Double

Total path weight

Description

Finds the single shortest weighted path between two vertices using Dijkstra’s algorithm. Internally delegates to the A* implementation with no heuristic. An edge without weightProperty (or whose value is not a number) weighs 1, and an edge whose weight is negative, NaN or infinite is not walked: use algo.bellmanford for negative weights.

Use Cases

  • Route planning in transportation networks

  • Cost-optimal navigation in weighted graphs

  • Network latency analysis

Example

MATCH (src:City {name:'Rome'}), (dst:City {name:'Berlin'})
CALL algo.dijkstra(src, dst, 'ROAD', 'distance', 'OUT')
YIELD path, weight
RETURN path, weight

References

See also: reference/graph-algorithms/sql-path-functions.adoc#algo-dijkstra-sql for the SQL function variant, and astar() / dijkstra() for the SQL function equivalents.

algo.cch.shortestPath

Property Value

Procedure

algo.cch.shortestPath

Category

Path Finding

Complexity

CPU

Min Args

4

Max Args

5

Syntax

CALL algo.cch.shortestPath(startNode, endNode, relTypes, weightProperty [, direction])
YIELD path, weight

Parameters

Parameter Type Required Default Description

startNode

Vertex

Yes

-

Source vertex

endNode

Vertex

Yes

-

Destination vertex

relTypes

String or List

Yes

-

Relationship type(s): a name, a comma-separated list or a list; null for every type

weightProperty

String

Yes

-

Edge property name to use as weight

direction

String

No

"BOTH"

Traversal direction: "IN", "OUT", or "BOTH"

Yield Fields

Field Type Description

path

Map

The path: nodes, relationships (the cheapest usable edge between each pair of consecutive nodes) and length

weight

Double

Total path weight

Description

Finds the shortest weighted path between two vertices. When a Graph Analytical View keeps a Customizable Contraction Hierarchy for the same weight property and relationship types, the path is answered by the hierarchy in a time that depends on the depth of the hierarchy rather than on how far apart the two vertices are: on road-like graphs it is one to two orders of magnitude faster than Dijkstra, and the gap grows with the length of the route.

When no hierarchy can answer - none is defined, it is still being prepared after a change, the graph was found unsuitable for it, or the calling transaction holds uncommitted changes the view cannot see - the procedure answers with a bidirectional Dijkstra, on the view’s columns when a view materializes the weight and on the records otherwise. The answer is always exact and always reflects the calling transaction’s own changes; only the speed varies.

The weight of an edge is the numeric value of weightProperty; an edge without one weighs 1, and an edge whose value is negative, NaN or infinite is not walked. Among parallel edges only the cheapest counts. Every weighted path finder (algo.dijkstra, algo.astar, algo.dijkstra.singleSource, algo.kShortestPaths, algo.steinerTree and the dijkstra(), astar(), duanSSSP() and cchShortestPath() SQL functions) reads the weight by this same rule, so they answer the same path.

Use Cases

  • Route planning on road, logistics and utility networks with many point-to-point queries

  • Navigation where weights change often (traffic, closures) but the network itself rarely does

Example

CREATE GRAPH ANALYTICAL VIEW roads EDGE TYPES (ROAD) UPDATE MODE SYNCHRONOUS CCH (distance)
MATCH (src:City {name:'Rome'}), (dst:City {name:'Berlin'})
CALL algo.cch.shortestPath(src, dst, 'ROAD', 'distance', 'OUT')
YIELD path, weight
RETURN path, weight

References

  • Dibbelt, Strasser, Wagner: Customizable Contraction Hierarchies, ACM Journal of Experimental Algorithmics 21 (2016)

See also: cchShortestPath() for the SQL function, and how-to/data-modeling/graph-olap.adoc#gav-cch for defining and monitoring the hierarchy.

algo.astar

Property Value

Procedure

algo.astar

Category

Path Finding

Complexity

CPU

Min Args

4

Max Args

6

Syntax

CALL algo.astar(startNode, endNode, relTypes, weightProperty [, latProperty, lonProperty])
YIELD path, weight

Parameters

Parameter Type Required Default Description

startNode

Vertex

Yes

—

Source vertex

endNode

Vertex

Yes

—

Destination vertex

relTypes

String

Yes

—

Comma-separated relationship types; pass '' for all types

weightProperty

String

Yes

—

Edge property name to use as weight

latProperty

String

No

—

Vertex property name for latitude (enables geographic heuristic)

lonProperty

String

No

—

Vertex property name for longitude (enables geographic heuristic)

Yield Fields

Field Type Description

path

List<RID>

Ordered list of vertex identities on the shortest path

weight

Double

Total path weight

Description

Finds the shortest weighted path using the A* algorithm. When latProperty and lonProperty are provided, a geographic (Euclidean) heuristic accelerates the search. Without the geographic properties it behaves identically to Dijkstra. Edges are followed in both directions, like algo.dijkstra’s default. The returned `path includes the relationships between the vertices. An edge without weightProperty (or whose value is not a number) weighs 1, and an edge whose weight is negative, NaN or infinite is not walked: use algo.bellmanford for negative weights.

Use Cases

  • Geospatial route optimization

  • Game AI pathfinding with spatial heuristics

  • Weighted graph shortest paths with domain-specific heuristics

Example

MATCH (src:City {name:'Milan'}), (dst:City {name:'Paris'})
CALL algo.astar(src, dst, 'ROAD', 'km', 'lat', 'lon')
YIELD path, weight
RETURN path, weight

References

algo.bellmanford

Property Value

Procedure

algo.bellmanford

Category

Path Finding

Complexity

CPU

Min Args

4

Max Args

4

Syntax

CALL algo.bellmanford(startNode, endNode, relTypes, weightProperty)
YIELD path, weight, negativeCycle

Parameters

Parameter Type Required Default Description

startNode

Vertex

Yes

—

Source vertex

endNode

Vertex

Yes

—

Destination vertex

relTypes

String

Yes

—

Comma-separated relationship types; pass '' for all types

weightProperty

String

Yes

—

Edge property name to use as weight (may be negative)

Yield Fields

Field Type Description

path

List<RID>

Ordered list of vertex identities on the shortest path

weight

Double

Total path weight

negativeCycle

Boolean

true if a negative-weight cycle is reachable from startNode

Description

Finds the shortest weighted path between two vertices using the Bellman-Ford algorithm. Unlike Dijkstra, it correctly handles graphs with negative edge weights. It runs V−1 relaxation iterations followed by one extra iteration to detect negative-weight cycles. If a negative cycle is detected, negativeCycle is set to true and the path result is unreliable.

Use Cases

  • Financial transaction networks with negative-cost edges

  • Currency arbitrage detection (negative cycle = profit cycle)

  • Graphs where edge weights can be negative

Example

MATCH (a:Account {id:1}), (b:Account {id:5})
CALL algo.bellmanford(a, b, 'TRANSFER', 'cost')
YIELD path, weight, negativeCycle
RETURN path, weight, negativeCycle

References

See also: reference/graph-algorithms/sql-path-functions.adoc#algo-bellman-ford-sql for the SQL function variant.

algo.allsimplepaths

Property Value

Procedure

algo.allsimplepaths

Category

Path Finding

Complexity

CPU

Min Args

4

Max Args

4

Syntax

CALL algo.allsimplepaths(startNode, endNode, relTypes, maxDepth)
YIELD path

Parameters

Parameter Type Required Default Description

startNode

Vertex

Yes

—

Source vertex

endNode

Vertex

Yes

—

Destination vertex

relTypes

String

Yes

—

Comma-separated relationship types; pass '' for all types

maxDepth

Integer

Yes

—

Maximum path length in hops (minimum 1)

Yield Fields

Field Type Description

path

List<RID>

Ordered list of vertex identities for one simple path

Description

Enumerates all simple (loop-free) paths between two vertices up to a maximum depth, using DFS with backtracking. Edges are traversed in both directions. Each result row contains one complete path. Use maxDepth to prevent combinatorial explosion in dense graphs.

Use Cases

  • Finding all routes between two nodes in a network

  • Dependency analysis between components

  • Attack path enumeration in security graphs

Example

MATCH (s:Service {name:'AuthService'}), (t:Service {name:'Database'})
CALL algo.allsimplepaths(s, t, 'CALLS', 4)
YIELD path
RETURN path

References

algo.kShortestPaths

Property Value

Procedure

algo.kShortestPaths

Category

Path Finding

Complexity

CPU+RAM

Min Args

3

Max Args

5

Syntax

CALL algo.kShortestPaths(startNode, endNode, k [, relTypes, weightProperty])
YIELD path, weight, rank

Parameters

Parameter Type Required Default Description

startNode

Vertex

Yes

—

Source vertex

endNode

Vertex

Yes

—

Destination vertex

k

Integer

Yes

—

Number of shortest paths to find

relTypes

String

No

all types

Comma-separated relationship types

weightProperty

String

No

uniform weight

Edge property name for weights

Yield Fields

Field Type Description

path

List<RID>

Ordered list of vertex identities

weight

Double

Total path weight

rank

Integer

1-based rank (1 = shortest)

Description

Finds the k shortest loopless paths between two vertices using Yen’s algorithm. Internally uses Dijkstra on a V×V weight matrix, progressively building candidate paths by spur-node deviation from previous shortest paths. Memory usage scales as O(V²) for the weight matrix. An edge without weightProperty weighs 1, and an edge whose weight is negative, NaN or infinite is not walked.

Use Cases

  • Resilience planning: top-k alternative routes in case of failures

  • Network redundancy analysis

  • Multi-criteria path exploration

Example

MATCH (s:Router {id:'R1'}), (t:Router {id:'R10'})
CALL algo.kShortestPaths(s, t, 3, 'LINK', 'latency')
YIELD path, weight, rank
RETURN rank, path, weight ORDER BY rank ASC

References

algo.apsp

Property Value

Procedure

algo.apsp

Category

Path Finding

Complexity

CPU+RAM

Min Args

0

Max Args

2

Syntax

CALL algo.apsp([weightProperty, relTypes])
YIELD source, target, distance

Parameters

Parameter Type Required Default Description

weightProperty

String

No

uniform weight

Edge property name for weights

relTypes

String

No

all types

Comma-separated relationship types

Yield Fields

Field Type Description

source

RID

Source vertex identity

target

RID

Target vertex identity

distance

Double

Shortest distance between source and target

Description

Computes shortest distances between all reachable pairs of distinct vertices using the Floyd-Warshall algorithm. Time complexity is O(V³); memory usage is O(V²). Only reachable pairs (finite distance, source ≠ target) are returned. Suitable for small to medium graphs.

Use Cases

  • Graph diameter and radius computation

  • Network reachability analysis

  • Pre-computing all pairwise distances for downstream analytics

Example

CALL algo.apsp('weight', 'ROAD')
YIELD source, target, distance
RETURN source, target, distance ORDER BY distance DESC LIMIT 10

References

algo.bfs

Property Value

Procedure

algo.bfs

Category

Path Finding

Complexity

CPU

Min Args

1

Max Args

4

Syntax

CALL algo.bfs(startNode [, relTypes, direction, maxDepth])
YIELD node, depth

Parameters

Parameter Type Required Default Description

startNode

Vertex

Yes

—

Source vertex from which the traversal starts

relTypes

String

No

all types

Comma-separated relationship types to follow

direction

String

No

"BOTH"

Traversal direction: "IN", "OUT", or "BOTH"

maxDepth

Integer

No

unbounded

Maximum BFS depth (hop count) from the start node

Yield Fields

Field Type Description

node

RID

Vertex identity (the start node is not included)

depth

Integer

BFS depth from the start node

Description

Performs a Breadth-First Search traversal from a given start node, visiting all reachable vertices in non-decreasing distance order. Each reachable vertex (excluding the start node itself) is yielded together with its BFS depth. An optional maxDepth bound limits the traversal radius.

Use Cases

  • Shortest hop-count paths from a source

  • Neighbourhood exploration at a given radius

  • Level-order processing of tree or DAG structures

Example

MATCH (start:Person {name:'Alice'})
CALL algo.bfs(start, 'KNOWS', 'BOTH', 3)
YIELD node, depth
RETURN node.name, depth ORDER BY depth

References

algo.dfs

Property Value

Procedure

algo.dfs

Category

Path Finding

Complexity

CPU

Min Args

1

Max Args

4

Syntax

CALL algo.dfs(startNode [, relTypes, direction, maxDepth])
YIELD node, depth

Parameters

Parameter Type Required Default Description

startNode

Vertex

Yes

—

Source vertex from which the traversal starts

relTypes

String

No

all types

Comma-separated relationship types to follow

direction

String

No

"BOTH"

Traversal direction: "IN", "OUT", or "BOTH"

maxDepth

Integer

No

unbounded

Maximum DFS depth from the start node

Yield Fields

Field Type Description

node

RID

Vertex identity (the start node is not included)

depth

Integer

DFS discovery depth from the start node

Description

Performs an iterative (non-recursive) Depth-First Search from a given start node using an explicit stack, avoiding Java stack-overflow on large graphs. Vertices are yielded in DFS discovery order together with their depth. An optional maxDepth bound limits the traversal.

Use Cases

  • Reachability analysis

  • Dependency resolution and cycle detection

  • Tree/DAG structure enumeration

Example

MATCH (start:Module {name:'core'})
CALL algo.dfs(start, 'DEPENDS_ON', 'OUT')
YIELD node, depth
RETURN node.name, depth

References

algo.dijkstra.singleSource

Property Value

Procedure

algo.dijkstra.singleSource

Category

Path Finding

Complexity

CPU

Min Args

3

Max Args

4

Syntax

CALL algo.dijkstra.singleSource(startNode, relTypes, weightProperty [, direction])
YIELD node, cost

Parameters

Parameter Type Required Default Description

startNode

Vertex

Yes

—

Source vertex

relTypes

String

Yes

—

Comma-separated relationship types; pass '' for all types

weightProperty

String

Yes

—

Edge property name to use as weight (must be numeric, non-negative)

direction

String

No

"OUT"

Traversal direction: "IN", "OUT", or "BOTH"

Yield Fields

Field Type Description

node

RID

Reachable vertex identity (the start node is not included)

cost

Double

Minimum total weight from the start node to this vertex

Description

Computes the Single-Source Shortest Path (SSSP) from a given start node to every reachable vertex using Dijkstra’s algorithm with a binary min-heap. This procedure extends algo.dijkstra to return results for all reachable targets at once instead of just a single source-target pair. An edge without weightProperty (or whose value is not a number) weighs 1; an edge whose weight is negative, NaN or infinite is not walked.

Use Cases

  • Distance maps from a hub in transportation networks

  • Risk propagation from an origin node

  • Identifying the closest facility to every location in a network

Example

MATCH (hub:City {name:'London'})
CALL algo.dijkstra.singleSource(hub, 'ROAD', 'distance', 'OUT')
YIELD node, cost
RETURN node.name, cost ORDER BY cost LIMIT 10

References

See also: algo.dijkstra for the single source-target variant.

algo.longestPath

Property Value

Procedure

algo.longestPath

Category

Path Finding

Complexity

CPU

Min Args

0

Max Args

2

Syntax

CALL algo.longestPath([relTypes, weightProperty])
YIELD node, distance, source

Parameters

Parameter Type Required Default Description

relTypes

String

No

all types

Comma-separated relationship types to follow

weightProperty

String

No

1.0 per hop

Edge property name to use as weight

Yield Fields

Field Type Description

node

RID

Vertex identity

distance

Double

Maximum distance from the furthest source reaching this vertex

source

RID

The source vertex that achieves the maximum distance

Description

Finds the longest path in a Directed Acyclic Graph (DAG) using dynamic programming on topological order (Kahn’s algorithm). If the graph contains a cycle the procedure detects it and returns an empty result set. When no weightProperty is provided, each hop has weight 1.0 (i.e., the result is the maximum hop count).

Use Cases

  • Critical path analysis in project scheduling (CPM)

  • Longest dependency chain in build systems

  • Pipeline bottleneck identification

Example

CALL algo.longestPath('DEPENDS_ON')
YIELD node, distance, source
RETURN node.name AS task, distance, source.name AS criticalSource
ORDER BY distance DESC LIMIT 5

References

See also: reference/graph-algorithms/structural-analysis.adoc#algo-topological-sort for topological ordering.

algo.msa

Property Value

Procedure

algo.msa

Category

Path Finding

Complexity

CPU

Min Args

1

Max Args

3

Syntax

CALL algo.msa(rootNode [, relTypes, weightProperty]) YIELD source, target, weight, totalWeight

Parameters

Name Type Default Description

rootNode

Vertex

—

Root vertex for the arborescence

relTypes

String

all types

Comma-separated edge type names to traverse

weightProperty

String

null

Edge property for weights; null = all weights 1.0

Yield Fields

Field Type Description

source

Vertex

Source vertex of this MSA edge

target

Vertex

Destination vertex of this MSA edge

weight

Float

Weight of this edge

totalWeight

Float

Total weight of the arborescence (same on every row)

Description

Computes the Minimum Spanning Arborescence (directed MST) rooted at a specified vertex using the Chu-Liu/Edmonds algorithm. Unlike the undirected algo.mst, the arborescence is a directed spanning tree where every non-root vertex has exactly one incoming edge and all vertices are reachable from the root along directed paths.

Returns n − 1 rows (one per arborescence edge). Returns an empty result if no spanning arborescence exists (the directed graph is not strongly connected from the root).

Use Cases

  • Optimising directed distribution networks (water, power, logistics)

  • Dependency resolution with minimum total cost

  • Directed network backbone extraction

Example

MATCH (r:City {name:'Rome'})
CALL algo.msa(r, 'ROAD', 'distance')
YIELD source, target, weight, totalWeight
RETURN source.name, target.name, weight ORDER BY weight

References

algo.steinerTree

Property Value

Procedure

algo.steinerTree

Category

Path Finding

Complexity

CPU+RAM

Min Args

1

Max Args

3

Syntax

CALL algo.steinerTree(terminalNodes [, relTypes, weightProperty]) YIELD source, target, weight, totalWeight

Parameters

Name Type Default Description

terminalNodes

List<Vertex>

—

List of terminal (required) vertices to connect

relTypes

String

all types

Comma-separated edge type names to traverse (undirected)

weightProperty

String

null

Edge property for weights; null = all weights 1.0

Yield Fields

Field Type Description

source

Vertex

Source vertex of this Steiner-tree edge

target

Vertex

Destination vertex of this Steiner-tree edge

weight

Float

Weight of this edge

totalWeight

Float

Total Steiner-tree weight (same on every row)

Description

Finds an approximate minimum-weight connected subgraph that spans all terminal vertices, using the Kou-Markowsky-Berman 2-approximation algorithm (approximation ratio 2(1 − 1/|T|) where |T| is the number of terminals):

  1. Run Dijkstra from each terminal to find shortest paths to all other terminals.

  2. Build a complete graph on terminals with shortest-path distances.

  3. Find the MST of this terminal graph (Kruskal’s).

  4. Expand each MST edge back to its actual shortest path in the original graph.

  5. Prune non-terminal leaves iteratively.

Edges are traversed undirected. Returns an empty result if terminals are unreachable from each other. An edge without weightProperty weighs 1, an edge whose weight is negative, NaN or infinite is not walked, and among parallel edges the cheapest one is the one reported.

Use Cases

  • Designing minimum-cost subnetworks connecting mandatory waypoints

  • Content distribution network planning

  • Pipeline / cable routing connecting required endpoints

Example

MATCH (a:City {name:'Rome'}), (b:City {name:'Milan'}), (c:City {name:'Naples'})
CALL algo.steinerTree([a, b, c], 'ROAD', 'distance')
YIELD source, target, weight, totalWeight
RETURN source.name, target.name, weight

References