graph-shortest-paths Operator (Preview)

Applies to: ✅ Microsoft FabricAzure Data ExplorerAzure MonitorMicrosoft Sentinel

The graph-shortest-paths operator finds the shortest paths between a set of source nodes and a set of target nodes in a graph and returns a table with the results.

Note

This operator is used in conjunction with the make-graph operator.

Syntax

G | graph-shortest-paths [output = OutputOption] Pattern where Predicate project [ColumnName =] Expression [, ...]

Parameters

Name Type Required Description
G string ✔️ The graph source, typically the output from a make-graph operation.
Pattern string ✔️ A path pattern that describes the path to find. Patterns must include at least one variable length edge and can't contain multiple sequences.
Predicate expression A boolean expression that consists of properties of named variables in the pattern and constants.
Expression expression ✔️ A scalar expression that defines the output row for each found path, using constants and references to properties of named variables in the pattern.
OutputOption string Specifies the search output as any (default) or all. Output is specified as any for a single shortest path per source/target pair and all for all shortest paths of equal minimum length.

Path pattern notation

The following table shows the supported path pattern notations.

Element Named variable Anonymous element
Node (n) ()
Directed edge from left to right -[e]-> -->
Directed edge from right to left <-[e]- <--
Any direction edge -[e]- --
Variable length edge -[e*3..5]- -[*3..5]-

Variable length edge

A variable length edge allows a specific pattern to repeat multiple times within defined limits. An asterisk (*) denotes this type of edge, followed by the minimum and maximum occurrence values in the format min..max. These values must be integer scalars. Any sequence of edges within this range can match the variable edge of the pattern, provided all the edges in the sequence meet the where clause constraints.

Returns

The graph-shortest-paths operator returns a tabular result, where each record corresponds to a path found in the graph. The returned columns are defined in the operator's project clause using properties of nodes and edges defined in the pattern. Properties and functions of properties of variable length edges, are returned as a dynamic array. Each value in the array corresponds to an occurrence of the variable length edge.

Examples

This section provides practical examples demonstrating how to use the graph-shortest-paths operator in different scenarios.

Find any shortest path between two train stations

The following example demonstrates how to use the graph-shortest-paths operator to find the shortest path between two stations in a transportation network. The query constructs a graph from the data in connections and finds the shortest path from the "South-West" to the "North" station, considering paths up to five connections long. Since the default output is any, it finds any shortest path.

let connections = datatable(from_station:string, to_station:string, line:string) 
[ 
  "Central", "North", "red",
  "North", "Central", "red", 
  "Central", "South",  "red", 
  "South", "Central",  "red", 
  "South", "South-West", "red", 
  "South-West", "South", "red", 
  "South-West", "West", "red", 
  "West", "South-West", "red", 
  "Central", "East", "blue", 
  "East", "Central", "blue", 
  "Central", "West", "blue",
  "West", "Central", "blue",
]; 
connections 
| make-graph from_station --> to_station with_node_id=station
| graph-shortest-paths (start)-[connections*1..5]->(destination)
  where start.station == "South-West" and destination.station == "North"
  project from = start.station, path = connections.to_station, line = connections.line, to = destination.station

Output

from path line to
South-West [
"South",
"Central",
"North"
]
[
"red",
"red",
"red"
]
North

Finding all shortest paths between two train stations

The following example, like the previous example, finds the shortest paths in a transportation network. However, it uses output=all, so returns all shortest paths.

let connections = datatable(from_station:string, to_station:string, line:string) 
[ 
  "Central", "North", "red",
  "North", "Central", "red", 
  "Central", "South",  "red", 
  "South", "Central",  "red", 
  "South", "South-West", "red", 
  "South-West", "South", "red", 
  "South-West", "West", "red", 
  "West", "South-West", "red", 
  "Central", "East", "blue", 
  "East", "Central", "blue", 
  "Central", "West", "blue",
  "West", "Central", "blue",
]; 
connections 
| make-graph from_station --> to_station with_node_id=station
| graph-shortest-paths output=all (start)-[connections*1..5]->(destination)
  where start.station == "South-West" and destination.station == "North"
  project from = start.station, path = connections.to_station, line = connections.line, to = destination.station

Output

from path line to
South-West [
"South",
"Central",
"North"
]
[
"red",
"red",
"red"
]
North
South-West [
"West",
"Central",
"North"
]
[
"red",
"blue",
"red"
]
North