Source: https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/single_pair_shortest_path/
Documentation version: v5.3.2

# Single Pair Shortest Path

## Algorithm introduction

Single-pair shortest path computes the minimum-cost route between one source node and one target node.

Compute the classic Bellman-Ford single-pair shortest path in a directed weighted graph whose node primary key is id and edge weight property is weight. Supports negative and non-negative edge weights, but requires that no negative-weight cycle is reachable from the source.

For more information, see [Single Pair Shortest Path](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm).

## Data model

To implement the Single Pair Shortest Path algorithm in GQL, the following data model is used to create a graph type:

- Entities are represented by nodes of type `Node`, with properties `id` and `rating`.
- Relationships are represented by edges of type `Link`, with property `weight`.

For the complete definition of the graph type, see [Prepare graph data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/single_pair_shortest_path/#1_prepare_graph_data).

## Procedure implementation[]()

To compute Single Pair Shortest Path results, a [procedure](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/procedures/create/) is created.

For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/single_pair_shortest_path/#procedure_implement). The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

- `source_id`: `INT64`. ID of the source node.
- `target_id`: `INT64`. ID of the target node.

Additionally, the following variables are defined within the procedure:

 | Variable name | Variable type | Description
 | `inf` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Infinity sentinel for uninitialized distances.
 | `round` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Current Bellman-Ford relaxation round.
 | `final_cost` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Shortest path cost from source to target.
 | `walk_id` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Node ID used during reverse path reconstruction.
 | `reverse_step` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Step counter during reverse path reconstruction.
 | `path_len` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Total path length.
 | `vertex_count` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Total number of nodes (used as Bellman-Ford iteration limit).
 | `updated` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Whether any edge was relaxed in the current round.
 | `target_state` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Best known state for the target node.
 | `back_state` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | State used during path reconstruction.
 | `dist` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node best known distance from source.
 | `parent` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node parent on the shortest path.
 | `edge_w` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node incoming edge weight on the shortest path.
 | `cand` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node best relaxation candidate in the current round.
 | `path_table` | [Table variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/table-variable/) | Intermediate table storing reversed path steps.

The following steps outline the logic of the procedure:

1. Initialize all nodes' `dist` to infinity; set the source node's `dist` to 0.
2. Run Bellman-Ford relaxation for up to `vertex_count` rounds: for each edge, relax the destination's `dist` if a shorter path is found via `cand`.
3. Stop early when `updated` is false (no relaxation occurred).
4. Reconstruct the path from target to source via `parent` links; return the ordered path steps with costs.

## Steps

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow [Prepare algorithm sample data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/) to check where to run commands and how the directory is mounted.

### 1. Prepare graph data[]()

1. 

Create a graph type that matches your data model.

````
'''
CREATE GRAPH TYPE IF NOT EXISTS single_pair_shortest_path_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

````

2. 

Download these CSV files and save them with their original names in `examples/algorithms/single_pair_shortest_path/` under your deployment directory:

  - [single_pair_shortest_path_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/single_pair_shortest_path/single_pair_shortest_path_node.csv): Node data.
  - [single_pair_shortest_path_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/single_pair_shortest_path/single_pair_shortest_path_edge.csv): Edge data.

Preview the CSV files

single_pair_shortest_path_node.csv

````
id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

````

single_pair_shortest_path_edge.csv

````
src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

````

Sample data with negative edge weights (optional)

Save these files in the same directory and use their names in the import statement below. If you already loaded the default data, [drop and recreate the temporary graph](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/#reload) first. After importing, use the [negative-weight example call](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/single_pair_shortest_path/#negative-weights).

  - [single_pair_shortest_path_negative_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/single_pair_shortest_path/single_pair_shortest_path_negative_node.csv): Node data.
  - [single_pair_shortest_path_negative_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/single_pair_shortest_path/single_pair_shortest_path_negative_edge.csv): Edge data.

single_pair_shortest_path_negative_node.csv

````
id,rating
1,0
2,0
3,0
4,0

````

single_pair_shortest_path_negative_edge.csv

````
src_id,dst_id,weight
1,2,4
1,3,5
2,3,-2
2,4,6
3,4,3

````

3. 

Create a temporary graph from the graph type, then import the CSV files.

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #single_pair_shortest_path_graph TYPED single_pair_shortest_path_graph_type

````

````
'''
USE #single_pair_shortest_path_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/single_pair_shortest_path/single_pair_shortest_path_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/single_pair_shortest_path/single_pair_shortest_path_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

````

After the import succeeds, run this query in the console to check the node count:

````
'''
USE #single_pair_shortest_path_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

The default CSV files should produce a `node_count` of `24`; the optional negative-weight dataset should produce `4`. If the count differs, check which files you used.

### 2. Create a procedure[]()

Create a procedure to implement the Single Pair Shortest Path algorithm. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/single_pair_shortest_path/#procedure_implement). 

````
'''
CREATE OR REPLACE PROCEDURE single_pair_shortest_path(
  source_id INT64,
  target_id INT64
)
RETURNS (step_no INT64, node_id INT64, parent_id INT64, edge_weight DOUBLE, path_cost DOUBLE, total_cost DOUBLE)
COMMENT "Compute the classic Bellman-Ford single-pair shortest path in a directed weighted graph whose vertex primary key is id and edge weight property is weight. Supports negative and non-negative edge weights, but requires that no negative-weight cycle is reachable from the source."
AS {
  VALUE inf DOUBLE = 1000000000000000000.0
  VALUE round INT64 = 0
  VALUE final_cost DOUBLE = 0.0
  VALUE walk_id INT64 = 0
  VALUE reverse_step INT64 = 0
  VALUE path_len INT64 = 0

  VALUE vertex_count SumAgg<INT64> = 0
  VALUE updated OrAgg = false
  VALUE target_state TopKAgg<1, dist DOUBLE ASC, parent_id INT64 ASC, edge_weight DOUBLE ASC>
  VALUE back_state TopKAgg<1, dist DOUBLE ASC, parent_id INT64 ASC, edge_weight DOUBLE ASC>

  NODE VALUE dist MinAgg<DOUBLE> = 1000000000000000000.0
  NODE VALUE parent MinAgg<INT64> = 0
  NODE VALUE edge_w MinAgg<DOUBLE> = 0.0
  NODE VALUE cand TopKAgg<1, dist DOUBLE ASC, parent_id INT64 ASC, edge_weight DOUBLE ASC>

  TABLE path_table TYPED TABLE {
    rev_step INT64,
    node_id INT64,
    parent_id INT64,
    edge_weight DOUBLE,
    path_cost DOUBLE
  }

  MATCH (n)
  PER NODE (n) {
    SET @vertex_count += 1
    SET n.@dist = inf
    SET n.@parent = 0
    SET n.@edge_w = 0.0
    SET n.@cand.clear()
  }

  MATCH (s)
  WHERE s.id = source_id
  PER NODE (s) {
    SET s.@dist = 0.0
    SET s.@parent = source_id
    SET s.@edge_w = 0.0
  }

  WHILE round < @vertex_count - 1 THEN {
    SET @updated = false

    MATCH (n)
    PER NODE (n) {
      SET n.@cand.clear()
    }

    MATCH (u)-[e]->(v)
    WHERE u.@dist < inf
    PER PATH {
      VALUE tentative DOUBLE = 0.0
      VALUE edge_cost DOUBLE = 0.0

      SET edge_cost = CAST(e.weight AS DOUBLE)
      SET tentative = u.@dist + edge_cost

      IF tentative < v.@dist THEN {
        SET v.@cand += RECORD{
          dist: tentative,
          parent_id: u.id,
          edge_weight: edge_cost
        }
        SET @updated += true
      }
    }

    MATCH (v)
    WHERE v.@cand.size() > 0
    PER NODE (v) {
      SET v.@dist = v.@cand.min().dist
      SET v.@parent = v.@cand.min().parent_id
      SET v.@edge_w = v.@cand.min().edge_weight
    }

    IF @updated = false THEN {
      SET round = @vertex_count
    }
    ELSE {
      SET round = round + 1
    }
  }

  SET @updated = false

  MATCH (u)-[e]->(v)
  WHERE u.@dist < inf
  PER PATH {
    VALUE tentative DOUBLE = 0.0

    SET tentative = u.@dist + CAST(e.weight AS DOUBLE)

    IF tentative < v.@dist THEN {
      SET @updated += true
    }
  }

  IF @updated = true THEN {
    LOG_ERROR("single_pair_shortest_path detected a negative-weight cycle reachable from the source")
  }
  ELSE {
    SET @target_state.clear()

    MATCH (t)
    WHERE t.id = target_id
    PER NODE (t) {
      SET @target_state += RECORD{
        dist: t.@dist,
        parent_id: t.@parent,
        edge_weight: t.@edge_w
      }
    }

    IF @target_state.size() > 0 AND @target_state.min().dist < inf THEN {
      SET final_cost = @target_state.min().dist
      SET walk_id = target_id
      SET reverse_step = 0

      WHILE walk_id <> source_id THEN {
        SET @back_state.clear()

        MATCH (n)
        WHERE n.id = walk_id
        PER NODE (n) {
          SET @back_state += RECORD{
            dist: n.@dist,
            parent_id: n.@parent,
            edge_weight: n.@edge_w
          }
        }

        EXPORT
          reverse_step,
          walk_id,
          @back_state.min().parent_id,
          @back_state.min().edge_weight,
          @back_state.min().dist
        INTO path_table

        SET walk_id = @back_state.min().parent_id
        SET reverse_step = reverse_step + 1
      }

      SET @back_state.clear()

      MATCH (n)
      WHERE n.id = source_id
      PER NODE (n) {
        SET @back_state += RECORD{
          dist: n.@dist,
          parent_id: n.@parent,
          edge_weight: n.@edge_w
        }
      }

      EXPORT reverse_step, source_id, @back_state.min().parent_id, 0.0, @back_state.min().dist INTO path_table
      SET path_len = reverse_step
    }
  }

  FOR r IN path_table
  RETURN
    path_len - r.rev_step AS step_no,
    r.node_id AS node_id,
    r.parent_id AS parent_id,
    r.edge_weight AS edge_weight,
    r.path_cost AS path_cost,
    final_cost AS total_cost
  ORDER BY step_no ASC
}
'''

````

### 3. Call your procedure[]()

The following call uses the default CSV data to find a path from node `1` to node `24`. For the optional negative-weight dataset, use the [negative-weight example call](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/single_pair_shortest_path/#negative-weights).

````
USE #single_pair_shortest_path_graph CALL single_pair_shortest_path(1, 24) RETURN step_no, node_id, parent_id, edge_weight, path_cost, total_cost

````

Returns:

Expand to view results

````
+---------+---------+-----------+-------------+-----------+------------+
| step_no | node_id | parent_id | edge_weight | path_cost | total_cost |
+---------+---------+-----------+-------------+-----------+------------+
| 0       | 1       | 1         | 0.0         | 0.0       | 23.0       |
| 1       | 2       | 1         | 4.0         | 4.0       | 23.0       |
| 2       | 6       | 2         | 2.0         | 6.0       | 23.0       |
| 3       | 8       | 6         | 1.0         | 7.0       | 23.0       |
| 4       | 9       | 8         | 3.0         | 10.0      | 23.0       |
| 5       | 13      | 9         | 2.0         | 12.0      | 23.0       |
| 6       | 15      | 13        | 2.0         | 14.0      | 23.0       |
| 7       | 19      | 15        | 3.0         | 17.0      | 23.0       |
| 8       | 21      | 19        | 1.0         | 18.0      | 23.0       |
| 9       | 23      | 21        | 4.0         | 22.0      | 23.0       |
| 10      | 24      | 23        | 1.0         | 23.0      | 23.0       |
+---------+---------+-----------+-------------+-----------+------------+

````

Call the negative-weight example

If you imported the optional negative-weight dataset, use node `1` as the source and node `4` as the target:

````
'''
USE #single_pair_shortest_path_graph
CALL single_pair_shortest_path(1, 4)
RETURN step_no, node_id, parent_id, edge_weight, path_cost, total_cost
'''

````

The expected `total_cost` is `5`.

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see [EXPORT](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/in-out/export/). Match the exported fields to the returned columns and target properties.