如何在BigQuery中基于两张表实现Dijkstra算法？

针对你的NODE和VERTEX表结构，我们可以利用BigQuery支持的递归CTE来实现Dijkstra算法，完美适配单向边的场景。以下是完整的实现方案：

前提说明 #

假设你的表结构如下：

• NODE：ID（节点唯一标识）、latitude（纬度）、longitude（经度）
• VERTEX：start_node_id（起始节点ID）、end_node_id（终止节点ID）、distance（边的权重/距离）

完整SQL实现 #

DECLARE start_node STRING; -- 若节点ID为数值类型，改为INT64
SET start_node = '你的起始节点ID'; -- 替换成实际起始节点ID

WITH RECURSIVE dijkstra AS (
  -- 初始阶段：初始化起始节点的距离为0，标记已访问
  SELECT
    start_node_id AS node_id,
    0 AS total_distance,
    ARRAY[start_node_id] AS path,
    TRUE AS visited
  FROM VERTEX
  WHERE start_node_id = start_node
  UNION ALL
  -- 递归阶段：迭代更新未访问节点的最短距离
  SELECT
    v.end_node_id AS node_id,
    d.total_distance + v.distance AS total_distance,
    ARRAY_CONCAT(d.path, [v.end_node_id]) AS path,
    TRUE AS visited
  FROM dijkstra d
  JOIN VERTEX v ON d.node_id = v.start_node_id
  -- 排除已访问节点，避免循环
  LEFT JOIN dijkstra d2 ON v.end_node_id = d2.node_id
  WHERE d2.node_id IS NULL
  -- 筛选同一节点的最短路径，避免重复计算
  QUALIFY ROW_NUMBER() OVER (PARTITION BY v.end_node_id ORDER BY total_distance) = 1
),
-- 汇总所有节点的最短路径，包含起始节点本身
all_nodes AS (
  SELECT node_id, total_distance, path
  FROM dijkstra
  UNION ALL
  SELECT start_node, 0, ARRAY[start_node]
  WHERE NOT EXISTS (SELECT 1 FROM dijkstra WHERE node_id = start_node)
)
-- 关联NODE表，获取节点经纬度信息
SELECT
  a.node_id,
  n.latitude,
  n.longitude,
  a.total_distance,
  a.path
FROM all_nodes a
LEFT JOIN NODE n ON a.node_id = n.ID
ORDER BY total_distance;

关键说明 #

1. 节点ID类型适配：如果你的NODE.ID是数值类型（如INT64），需修改DECLARE语句的类型，并调整SET语句的赋值内容。
2. 迭代次数调整：BigQuery递归CTE默认限制100次迭代，若你的图节点较多，可在WITH RECURSIVE后添加OPTIONS(max_recursion = 500)（数值按需调整）。
3. 单向边处理：代码直接复用VERTEX表的边方向，天然支持单向边场景，无需额外修改。
4. 路径记录：path字段用数组存储从起始节点到当前节点的完整路径，方便查看路径详情。

优化建议 #

• 若VERTEX表数据量较大，可给start_node_id添加分区或索引，提升递归查询效率。
• 若仅需特定目标节点的最短路径，可在最终查询中添加WHERE a.node_id = '目标节点ID'过滤结果。

内容的提问来源于stack exchange，提问作者Ignacio Telechea