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

# A* Shortest Path

## Algorithm introduction

A* shortest path uses a best-first strategy with a heuristic score to find an efficient route from source to target.

Compute an A* shortest path in a directed weighted graph whose node primary key is id and edge weight property is weight. This demo version embeds the heuristic table for target_id = 24; other target values fall back to zero heuristic and therefore degrade toward Dijkstra.

For more information, see [A* Shortest Path](https://en.wikipedia.org/wiki/A*_search_algorithm).

## Data model

To implement the A* 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/astar_shortest_path/#1_prepare_graph_data).

## Procedure implementation[]()

To compute A* 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/astar_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 to start the search from.
- `target_id`: `INT64`. ID of the target node to find the path to.

Additionally, the following variables are defined within the procedure:

 | Variable name | Variable type | Description
 | `search_done` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Flag indicating the A* search has terminated.
 | `has_path` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Whether a valid path from source to target was found.
 | `inf` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Infinity sentinel for uninitialized scores.
 | `current_id` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | ID of the node being expanded in the current step.
 | `current_g` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | g-score (cost from source) of the currently expanded node.
 | `final_cost` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Total cost of the found shortest path.
 | `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 traversal.
 | `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 number of steps in the found path.
 | `best_open` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Min-heap entry selecting the next node to expand (lowest f-score).
 | `pick_state` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | State snapshot of the node currently being settled.
 | `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 reverse path reconstruction.
 | `heur` | 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 A* heuristic (h-score) estimate to the target.
 | `gscore` | 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 cost from source (g-score).
 | `fscore` | 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 f-score (g + h), used for open-set ordering.
 | `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 node ID on the best path found so far.
 | `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 edge weight from parent to this node on the best path.
 | `opened` | 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 flag: node is currently in the open set.
 | `closed` | 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 flag: node has been settled and removed from open set.
 | `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 candidate relaxation found in the current expansion.
 | `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 for reconstruction.

The following steps outline the logic of the procedure:

1. Initialize all nodes' `gscore` to infinity; set the source node's `gscore` to 0 and `fscore` to its heuristic `heur`; add it to the open set.
2. Repeatedly extract the open-set node with the lowest `fscore` (`best_open`); if it is the target, record `final_cost` and stop.
3. For each neighbor, compute a tentative g-score; if it improves the neighbor's `gscore`, update `gscore`, `fscore`, `parent`, and add to the open set.
4. Reconstruct the path from target to source via `parent` links; return the ordered path steps.

## 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 astar_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/astar_shortest_path/` under your deployment directory:

  - [astar_shortest_path_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/astar_shortest_path/astar_shortest_path_node.csv): Node data.
  - [astar_shortest_path_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/astar_shortest_path/astar_shortest_path_edge.csv): Edge data.

Preview the CSV files

astar_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

````

astar_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

````

3. 

Create a temporary graph based on the graph type and load the data files into the temporary graph.

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #astar_shortest_path_graph TYPED astar_shortest_path_graph_type

````

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

````

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

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

````

The expected `node_count` is `24`. If it differs, [check the files and import results](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting) before continuing.

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

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

````
'''
CREATE OR REPLACE PROCEDURE astar_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 an A* shortest path in a directed weighted graph whose vertex primary key is id and edge weight property is weight. This demo version embeds the heuristic table for target_id = 24; other target values fall back to zero heuristic and therefore degrade toward Dijkstra."
AS {
  VALUE search_done BOOLEAN = false
  VALUE has_path BOOLEAN = false
  VALUE inf DOUBLE = 1000000000000000000.0
  VALUE current_id INT64 = 0
  VALUE current_g DOUBLE = 0.0
  VALUE final_cost DOUBLE = 0.0
  VALUE walk_id INT64 = 0
  VALUE reverse_step INT64 = 0
  VALUE path_len INT64 = 0

  VALUE best_open TopKAgg<1, f DOUBLE ASC, node_id INT64 ASC>
  VALUE pick_state TopKAgg<1, g DOUBLE ASC, f DOUBLE ASC, node_id INT64 ASC>
  VALUE back_state TopKAgg<1, g DOUBLE ASC, parent_id INT64 ASC, edge_weight DOUBLE ASC>

  NODE VALUE heur SumAgg<DOUBLE> = 0.0
  NODE VALUE gscore MinAgg<DOUBLE> = 1000000000000000000.0
  NODE VALUE fscore MinAgg<DOUBLE> = 1000000000000000000.0
  NODE VALUE parent MinAgg<INT64> = 0
  NODE VALUE edge_w MinAgg<DOUBLE> = 0.0
  NODE VALUE opened OrAgg = false
  NODE VALUE closed OrAgg = false
  NODE VALUE cand TopKAgg<1, f DOUBLE ASC, g 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 n.@heur = 0.0
    SET n.@gscore = inf
    SET n.@fscore = inf
    SET n.@parent = 0
    SET n.@edge_w = 0.0
    SET n.@opened = false
    SET n.@closed = false
    SET n.@cand.clear()
  }

  IF target_id = 24 THEN {
    MATCH (n)
    PER NODE (n) {
      IF n.id = 1 THEN {
        SET n.@heur = 23.0
      }
      ELSEIF n.id = 2 THEN {
        SET n.@heur = 19.0
      }
      ELSEIF n.id = 3 THEN {
        SET n.@heur = 22.0
      }
      ELSEIF n.id = 4 THEN {
        SET n.@heur = 19.0
      }
      ELSEIF n.id = 5 THEN {
        SET n.@heur = 19.0
      }
      ELSEIF n.id = 6 THEN {
        SET n.@heur = 17.0
      }
      ELSEIF n.id = 7 THEN {
        SET n.@heur = 15.0
      }
      ELSEIF n.id = 8 THEN {
        SET n.@heur = 16.0
      }
      ELSEIF n.id = 9 THEN {
        SET n.@heur = 13.0
      }
      ELSEIF n.id = 10 THEN {
        SET n.@heur = 16.0
      }
      ELSEIF n.id = 11 THEN {
        SET n.@heur = 16.0
      }
      ELSEIF n.id = 12 THEN {
        SET n.@heur = 15.0
      }
      ELSEIF n.id = 13 THEN {
        SET n.@heur = 11.0
      }
      ELSEIF n.id = 14 THEN {
        SET n.@heur = 12.0
      }
      ELSEIF n.id = 15 THEN {
        SET n.@heur = 9.0
      }
      ELSEIF n.id = 16 THEN {
        SET n.@heur = 12.0
      }
      ELSEIF n.id = 17 THEN {
        SET n.@heur = 10.0
      }
      ELSEIF n.id = 18 THEN {
        SET n.@heur = 10.0
      }
      ELSEIF n.id = 19 THEN {
        SET n.@heur = 6.0
      }
      ELSEIF n.id = 20 THEN {
        SET n.@heur = 7.0
      }
      ELSEIF n.id = 21 THEN {
        SET n.@heur = 5.0
      }
      ELSEIF n.id = 22 THEN {
        SET n.@heur = 4.0
      }
      ELSEIF n.id = 23 THEN {
        SET n.@heur = 1.0
      }
      ELSEIF n.id = 24 THEN {
        SET n.@heur = 0.0
      }
    }
  }

  MATCH (s)
  WHERE s.id = source_id
  PER NODE (s) {
    SET s.@gscore = 0.0
    SET s.@fscore = s.@heur
    SET s.@parent = source_id
    SET s.@edge_w = 0.0
    SET s.@opened = true
    SET s.@closed = false
  }

  WHILE search_done = false THEN {
    SET @best_open.clear()

    MATCH (n)
    WHERE n.@opened = true AND n.@closed = false
    PER NODE (n) {
      SET @best_open += RECORD{f: n.@fscore, node_id: n.id}
    }

    IF @best_open.size() = 0 THEN {
      SET search_done = true
    }
    ELSE {
      SET current_id = @best_open.min().node_id
      SET @pick_state.clear()

      MATCH (u)
      WHERE u.id = current_id
      PER NODE (u) {
        SET @pick_state += RECORD{g: u.@gscore, f: u.@fscore, node_id: u.id}
        SET u.@opened = false
        SET u.@closed = true
      }

      SET current_g = @pick_state.min().g

      IF current_id = target_id THEN {
        SET final_cost = current_g
        SET has_path = true
        SET search_done = true
      }
      ELSE {
        MATCH (v)
        PER NODE (v) {
          SET v.@cand.clear()
        }

        MATCH (u)-[e]->(v)
        WHERE u.id = current_id
        PER PATH {
          VALUE tentative DOUBLE = 0.0
          VALUE edge_cost DOUBLE = 0.0

          SET edge_cost = CAST(e.weight AS DOUBLE)
          SET tentative = current_g + edge_cost

          IF tentative < v.@gscore THEN {
            SET v.@cand += RECORD{
              f: tentative + v.@heur,
              g: tentative,
              parent_id: current_id,
              edge_weight: edge_cost
            }
          }
        }

        MATCH (v)
        WHERE v.@cand.size() > 0
        PER NODE (v) {
          SET v.@gscore = v.@cand.min().g
          SET v.@fscore = v.@cand.min().f
          SET v.@parent = v.@cand.min().parent_id
          SET v.@edge_w = v.@cand.min().edge_weight
          SET v.@opened = true
          SET v.@closed = false
        }
      }
    }
  }

  IF has_path = true THEN {
    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{
          g: n.@gscore,
          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().g
      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{
        g: n.@gscore,
        parent_id: n.@parent,
        edge_weight: n.@edge_w
      }
    }

    EXPORT reverse_step, source_id, @back_state.min().parent_id, 0.0, @back_state.min().g 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[]()

Find a path from node `1` to node `24`, returning its nodes, edge weights, and accumulated costs.

````
USE #astar_shortest_path_graph CALL astar_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       |
+---------+---------+-----------+-------------+-----------+------------+

````

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.