# Delta-stepping single source shortest path (SSSP) algorithm
The `.sssp.deltaStepping` algorithm computes the shortest path distances from a single source vertex to all other vertices in the graph using a [delta-stepping](https://en.wikipedia.org/wiki/Parallel_single-source_shortest_path_algorithm#Delta_stepping_algorithm) algorithm.
Neptune Analytics implements the algorithm such that:
+ Positive edge weights must be provided using the `edgeWeightProperty` field
+ Negative edge weights are not supported.
+ The traversal direction cannot be set to `both`.
## `.sssp.deltaStepping` syntax
```
CALL neptune.algo.sssp.deltaStepping(
[source-node list (required)],
{
edgeWeightProperty: edge weight predicate for traversal (required)
edgeWeightType: numeric type of the edge weight property (required)
delta: the stepping delta (optional)
edgeLabels: [list of edge labels for filtering (optional)],
vertexLabel: a node label for filtering (optional),
traversalDirection: traversal direction (optional),
concurrency: number of threads to use (optional)
}
)
YIELD the outputs to generate (source and/or node)
RETURN the outputs to return
```
## `.sssp.deltaStepping` inputs
+ **a source node list** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the starting location(s) for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source-node list is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source-node list for the algorithm.
+
**a configuration object that contains:**
+ **edgeWeightProperty** *(required)* – *type:* `string`; *default: none*.
The edge weight predicate for traversal.
+ **edgeWeightType** *(required)* – *type:* `string`; *valid values:* `"int"`, `"long"`, `"float"`, `"double"`.
The numeric data type of the values in the property specified by `edgeWeightProperty`.
+ **delta** *(optional)* – *type:* float; *example:* `3.0`; *default:* `2.0`.
The delta stepping value.
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **vertexLabel** *(optional)* – *type:* `string`; *example:* `"airport"`; *default:* no node filtering.
A node label for node filtering. If a node label is provided, vertices matching the label are the only vertices that are included, including vertices in the input list.
+ **traversalDirection** *(optional)* – *type:* `string`; *default:*` "outbound"`.
The direction of edge to follow. Must be one of: `"inbound"` or `"outbound"`.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## Outputs for the `sssp.deltaStepping` algorithm
For every node that can be reached from the specified source list, the algorithm returns:
+ **source** – The source node.
+ **node** – A node found traversing from the source.
+ **distance** – The distance between the source node and the found node.
## `.sssp.deltaStepping` query examples
This is a standalone query, where a source node (or nodes) is explicitly provided:
```
CALL neptune.algo.sssp.deltaStepping(
["101"],
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int"
}
)
```
This is a query integration example, where where `.sssp.deltaStepping` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node list:
```
MATCH (source:airport {code: 'ANC'})
CALL neptune.algo.sssp.deltaStepping(
source,
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int",
vertexLabel: "airport",
traversalDirection: "outbound",
concurrency: 1
}
)
YIELD node, parent, distance
RETURN source, node, parent, distance
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes is returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.sssp.deltaStepping` output
Here is an example of the output returned by .sssp.deltaStepping when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string "CALL neptune.algo.sssp.deltaStepping(['101'],
{edgeWeightProperty: 'dist', edgeWeightType: 'int'})
yield source, node, distance
return source, node, distance
limit 2" \
--language open_cypher \
/tmp/out.txt
cat /tmp/out.txt
{
"results": [
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "2709",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 65.4809036254883,
"elev": 49,
"longest": 8711,
"city": "Nadym",
"type": "airport",
"region": "RU-YAN",
"desc": "Nadym Airport",
"code": "NYM",
"prscore": 0.00016044313088059425,
"degree": 18,
"lon": 72.6988983154297,
"wccid": 2357352929951779,
"country": "RU",
"icao": "USMM",
"runways": 1
}
},
"distance": 3812
},
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "2667",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 56.8567008972168,
"elev": 2188,
"longest": 6562,
"city": "Ust-Kut",
"type": "airport",
"region": "RU-IRK",
"desc": "Ust-Kut Airport",
"code": "UKX",
"prscore": 0.000058275499999999997,
"degree": 4,
"lon": 105.730003356934,
"wccid": 2357352929951779,
"country": "RU",
"icao": "UITT",
"runways": 1
}
},
"distance": 2993
}
]
}
```