Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/astar_shortest_path/
Documentation version: v5.3.2

# A* 最短路径

本文介绍 A* 最短路径算法，并演示如何用 GQL 实现该算法。

## 算法介绍

A* 最短路径通过启发式评分进行最佳优先搜索，以更高效地找到源点到目标点的路径。

该过程将算法逻辑封装为可复用过程，可直接在图数据上执行并输出结果。

更多信息，请参见 [A* 最短路径](https://zh.wikipedia.org/wiki/A*%E6%90%9C%E5%AF%BB%E7%AE%97%E6%B3%95)。

## 数据模型

为了在 GQL 中实现 A* 最短路径算法，使用以下数据模型创建图类型：

- 实体由类型为`Node`的点表示，点属性包括`id`和`rating`。
- 实体间关系由类型为`Link`的边表示，边属性包括`weight`。

该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/astar_shortest_path/#1_prepare_graph_data)。

## 过程实现[]()

为了计算 A* 最短路径结果，创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)。

关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/astar_shortest_path/#procedure_implement)。下文将介绍该过程的关键组成部分及其工作原理。

该过程接受以下输入参数：

- `source_id`：`INT64`类型。 搜索起始点的 ID。
- `target_id`：`INT64`类型。 目标点的 ID。

此外，在过程内部定义了以下变量：

 | 变量名 | 变量类型 | 描述
 | `search_done` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 标志 A* 搜索已终止。
 | `has_path` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 是否找到从源到目标的有效路径。
 | `inf` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 未初始化分数的无穷大哨兵值。
 | `current_id` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前步骤中正在扩展的点 ID。
 | `current_g` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前扩展点的 g 分数（从源出发的代价）。
 | `final_cost` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 找到的最短路径的总代价。
 | `walk_id` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 逆向路径重建时使用的点 ID。
 | `reverse_step` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 逆向路径重建时的步骤计数。
 | `path_len` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 找到路径的总步数。
 | `best_open` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 选取下一个待扩展点的最小堆条目（最小 f 分数）。
 | `pick_state` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 当前正在确定的点的状态快照。
 | `back_state` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 逆向路径重建中使用的状态。
 | `heur` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点到目标的 A* 启发值（h 分数）。
 | `gscore` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点从源出发的已知最小代价（g 分数）。
 | `fscore` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点 f 分数（g + h），用于开放集排序。
 | `parent` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点在当前最优路径上的父点 ID。
 | `edge_w` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点在最优路径上从父点到该点的边权。
 | `opened` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点标志：该点当前在开放集中。
 | `closed` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点标志：该点已被确定并移出开放集。
 | `cand` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 当前扩展中为该点找到的最优松弛候选。
 | `path_table` | [表变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/table-variable/) | 存储逆序路径步骤以供重建的中间表。

以下步骤概述了该过程的逻辑：

1. 将所有点的`gscore`初始化为无穷大；将源点的`gscore`设为 0，`fscore`设为其启发值`heur`，并加入开放集。
2. 反复从开放集中取出`fscore`最小的点（`best_open`）；若该点是目标点，则记录`final_cost`并停止搜索。
3. 对每个邻居点，计算暂定 g 分数；若优于当前`gscore`，则更新`gscore`、`fscore`、`parent`并重新加入开放集。
4. 通过`parent`链从目标回溯到源点重建路径，返回有序路径步骤。

## 操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。

### 1. 准备图数据[]()

1. 

创建一个与数据模型匹配的图类型。

````
'''
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. 

下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/astar_shortest_path/`：

  - [astar_shortest_path_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/astar_shortest_path/astar_shortest_path_node.csv)：点数据。
  - [astar_shortest_path_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/astar_shortest_path/astar_shortest_path_edge.csv)：边数据。

查看 CSV 内容

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 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: ','
      }
  }
'''

````

导入成功后，在控制台执行以下查询核对点数：

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

````

`node_count`应为`24`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。

### 2. 创建过程[]()

创建实现 A* 最短路径算法的过程。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/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. 调用过程[]()

查找从点`1`到点`24`的路径，返回路径中的点、边权和累计代价。

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

````

返回：

展开查看返回

````
+---------+---------+-----------+-------------+-----------+------------+
| 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       |
+---------+---------+-----------+-------------+-----------+------------+

````

保存结果到文件或图中

如需将返回的结果保存为 CSV 文件或写入图，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)。导出字段应与返回列及目标属性对应。