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

# 单点对最短路径

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

## 算法介绍

单点对最短路径用于计算指定源点与目标点之间的最小代价路径。

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

更多信息，请参见[单点对最短路径](https://zh.wikipedia.org/wiki/Bellman-Ford%E7%AE%97%E6%B3%95)。

## 数据模型

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

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

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

## 过程实现[]()

为了计算单点对最短路径结果，创建一个[过程](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/single_pair_shortest_path/#procedure_implement)。下文将介绍该过程的关键组成部分及其工作原理。

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

- `source_id`：`INT64`类型。 源点的 ID。
- `target_id`：`INT64`类型。 目标点的 ID。

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

 | 变量名 | 变量类型 | 描述
 | `inf` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 未初始化距离的无穷大哨兵值。
 | `round` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前 Bellman-Ford 松弛轮次。
 | `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/) | 路径总长度。
 | `vertex_count` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 点总数（用作 Bellman-Ford 迭代上限）。
 | `updated` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前轮是否有边被松弛。
 | `target_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/) | 路径重建中使用的状态。
 | `dist` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点从源出发的已知最短距离。
 | `parent` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点在最短路径上的父点。
 | `edge_w` | 点绑定 [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. 将所有点的`dist`初始化为无穷大；将源点的`dist`设为 0。
2. 执行最多`vertex_count`轮 Bellman-Ford 松弛：对每条边，若通过`cand`找到更短路径则松弛目标点的`dist`。
3. 当`updated`为 false（本轮无松弛）时提前停止。
4. 通过`parent`链从目标回溯到源点重建路径，返回带代价的有序路径步骤。

## 操作步骤

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

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

1. 

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

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

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

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

查看 CSV 内容

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

````

含负权边的示例数据（可选）

下载以下文件并保存到相同目录。将下方导入语句中的点、边文件名替换为这组文件；若已加载默认数据，先按[重新导入](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#reload)删除并重新创建临时图。导入后，使用[负权边示例的调用](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/single_pair_shortest_path/#negative-weights)。

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

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

````

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

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

````

使用默认 CSV 文件时，`node_count`应为`24`；可选负权边数据应为`4`。点数不符时，先核对所用的文件。

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

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

以下调用使用默认 CSV 数据，查找从点`1`到点`24`的路径。使用可选负权边数据时，按[负权边示例的调用](https://dev-docs.yueshu.com.cn/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

````

返回：

展开查看返回

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

````

负权边示例的调用

若导入了可选的负权边数据，使用点`1`作为起点、点`4`作为终点：

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

````

`total_cost`应为`5`。

保存结果到文件或图中

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