大查询Dijkstra

Question

我试图使用两个表在bigquery上运行Dijkstra算法。第一个表具有节点信息(ID、纬度、经度)，第二个表具有顶点信息(Start_node_ID、End_node_ID、节点之间的距离)。我不知道如何开始这个项目，我对bigquery没有太多的经验，我见过一些人在SQL上做了类似的事情，所以我知道这是可能的，但是我很难在BigQuery上复制它。

所有的帮助都是欢迎的，谢谢你的时间。

在这里，它的数据看起来是谁，一些顶点只朝一个方向走。

NODE

 1. |ID|LAT|LONG|
 2. |1 |1.2| 1.3|
 3. |2 |1.2| 1.4|
 4. |3 |3.4|-2.5|

VERTEX

 1. |STR|END|DST|
 2. | 1 | 2 | 3 |
 3. | 2 | 1 | 3 |
 4. | 1 | 3 | 4 |

我尝试了以下代码，但不确定如何将其转换为bigquery

https://kainwen.com/2019/10/31/dijkstra-via-sql-a-glance-at-recursive-cte/

Answer 1

递归CTE在BigQuery中是支持的，但是有一些限制可能是您的用例的关键。

让我们以这里解释的最后SQL代码为例：https://kainwen.com/2019/10/31/dijkstra-via-sql-a-glance-at-recursive-cte/

并将其翻译为BigQuery：

create OR REPLACE table `qwiklabs-gcp-01-6fe73054adde.data.roadmap`(a int, b int, d int);
insert into `qwiklabs-gcp-01-6fe73054adde.data.roadmap` values
(1, 2, 7),
(1, 3, 9),
(1, 6, 14),
(2, 3, 10),
(2, 4, 15),
(3, 4, 11),
(3, 6, 2),
(4, 5, 6),
(5, 6, 9);

create OR REPLACE table `qwiklabs-gcp-01-6fe73054adde.data.roadmap_sym`
AS SELECT * FROM `qwiklabs-gcp-01-6fe73054adde.data.roadmap`;

insert into `qwiklabs-gcp-01-6fe73054adde.data.roadmap_sym` select b,a,d from `qwiklabs-gcp-01-6fe73054adde.data.roadmap`;
insert into `qwiklabs-gcp-01-6fe73054adde.data.roadmap_sym` values (null, null, null);
 
create OR REPLACE table `qwiklabs-gcp-01-6fe73054adde.data.known`
AS SELECT * FROM `qwiklabs-gcp-01-6fe73054adde.data.roadmap`
WHERE 1<>1;


insert into `qwiklabs-gcp-01-6fe73054adde.data.known` values (6, 3, 2);
 
with recursive sp as
(
select * from `qwiklabs-gcp-01-6fe73054adde.data.known`
union all
select a, b, d
from
(
  select
    a, b, d, s, rank() over (order by (d+s)) as rk
  from
  (
    select a, b, d, s
    from
    (
      select
      a, b, min(d) as d, sum(t) as s
      from
      (
        select
          sp.a as a,
          case
        when rm.a is null then sp.b
        else rm.b
      end as b,
          case
        when rm.a is null then sp.d
            when sp.a = rm.a then rm.d
            else sp.d + rm.d
          end as d,
      case
        when rm.a is null then 1000
        else 0
      end as t
        from
          sp, `qwiklabs-gcp-01-6fe73054adde.data.roadmap_sym` as rm
        where
      rm.a is null
      or
      (
            (sp.a = rm.a or
             sp.b = rm.a) and
            sp.a <> rm.b
      )
      ) x
      group by a, b
    )y
  )z
)q where rk = 1 or s = 1000
)
select * from sp where b = 4 limit 1;

由于以下错误，BigQuery在执行CTE时将失败：

A subquery containing a recursive reference may not use DISTINCT, GROUP BY, or any aggregate function

考虑到这一点，您可以利用递归的CTE，但是对于某些查询，现有的限制可能是一个阻止器问题。

请看一下这里记录的所有规格和限制：https://cloud.google.com/bigquery/docs/reference/standard-sql/query-syntax#recursive_keyword

Answer 2

在SQL中这样的函数是相当棘手的。编写JavaScript UDF通常是有意义的。

Carto编写了这样的路由算法代码，您可能会看到是否可以将其修改为您的数据：https://carto.com/blog/how-to-do-route-optimization-at-scale-with-carto-bigquery/