sql—在postgresql中提供路由的递归查询

bvjxkvbb 于 2021-07-29 发布在 Java

关注(0)|答案(2)|浏览(314)

我必须在psql中执行递归函数才能获得以下查询：
我有一张table叫 tb_route 与 from_city 以及 to_city 我还有一个专栏，写的是不同城市之间的距离，单位是公里。
表是递归构建的。我必须做一个递归cte来显示两个城市之间的路线（即从“santiago de compostela”到“saint jean pied de port”），显示路线的总公里数和经过的城市。
输出必须如下所示：

这就是我尝试过的：

WITH RECURSIVE cities AS (
      SELECT *
      FROM textil.tb_route
      WHERE to_city_name = 'Santigo de Compostela'
  UNION ALL
      SELECT e.from_city, e.to_city, e.route, e.km
      FROM textil.tb_route e
  INNER JOIN cities tb_route ON tb_route.from_city_name = e.from_city
)

SELECT *
FROM cities;

我犯了一个错误，比如：

ERROR:  column e.from_city does not exist
LINE 8: ...JOIN cities tb_route ON tb_route.from_city_name = e.from_cit...

表格：

CREATE TABLE textil.tb_route
(
    from_city_name            CHARACTER VARYING(120) NOT NULL ,
    to_city_name              CHARACTER VARYING(120) NOT NULL ,
    km_distance_num           NUMERIC(5,2) NOT NULL ,
    CONSTRAINT pk_route PRIMARY KEY (from_city_name, to_city_name)
);

数据：

INSERT INTO textil.tb_route VALUES
  ('Saint Jean Pied de Port','Roncesvalles',25.7),
  ('Somport','Jaca',30.5),
  ('Roncesvalles','Zubiri',21.5),
  ('Jaca','Arrés',25),
  ('Zubiri','Pamplona/Iruña',20.4),
  ('Arrés','Ruesta',28.7),
  ('Pamplona/Iruña','Puente la Reina/Gares',24),
  ('Ruesta','Sangüesa',21.8),
  ('Puente la Reina/Gares','Estella/Lizarra',22),
  ('Sangüesa','Monreal',27.25),
  ('Estella/Lizarra','Torres del Río',29),
  ('Monreal','Puente la Reina/Gares',31.1),
  ('Torres del Río','Logroño',20),
  ('Logroño','Nájera',29.6),
  ('Nájera','Santo Domingo de la Calzada',21),
  ('Santo Domingo de la Calzada','Belorado',22.7),
  ('Belorado','Agés',27.4),
  ('Agés','Burgos',23),
  ('Burgos','Hontanas',31.1),
  ('Hontanas','Boadilla del Camino',28.5),
  ('Boadilla del Camino','Carrión de los Condes',24.6),
  ('Carrión de los Condes','Terradillos de los Templarios',26.6),
  ('Terradillos de los Templarios','El Burgo Ranero',30.6),
  ('El Burgo Ranero','León',37.1),
  ('León','San Martín del Camino',25.9),
  ('San Martín del Camino','Astorga',24.2),
  ('Astorga','Foncebadón',25.9),
  ('Foncebadón','Ponferrada',27.3),
  ('Ponferrada','Villafranca del Bierzo',24.1),
  ('Villafranca del Bierzo','O Cebreiro',28.4),
  ('O Cebreiro','Triacastela',21.1),
  ('Triacastela','Sarria',18.3),
  ('Sarria','Portomarín',22.4),
  ('Portomarín','Palas de Rei',25),
  ('Palas de Rei','Arzúa',28.8),
  ('Arzúa','Pedrouzo',19.1),
  ('Pedrouzo','Santiago de Compostela',20),
  ('Bayona','Ustaritz',14.3),
  ('Ustaritz','Urdax',21.2),
  ('Urdax','Elizondo',18.8),
  ('Elizondo','Berroeta',9.7),
  ('Berroeta','Olagüe',20.4),
  ('Olagüe','Pamplona/Iruña',25),
  ('Irún','Hernani',26.6),
  ('Hernani','Tolosa',18.9),
  ('Tolosa','Zerain',33),
  ('Zerain','Salvatierra/Agurain',28),
  ('Salvatierra/Agurain','Vitoria/Gasteiz',27.4),
  ('Vitoria/Gasteiz','La Puebla de Arganzón',18.5),
  ('La Puebla de Arganzón','Haro',31),
  ('Haro','Santo Domingo de la Calzada',20),
  ('Bayona','Irún',33.8),
  ('Tolosa','Zegama',37.9),
  ('Zegama','Salvatierra/Agurain',20.1),
  ('La Puebla de Arganzón','Miranda del Ebro',22.3),
  ('Miranda del Ebro','Pancorbo',16.7),
  ('Pancorbo','Briviesca',23.4),
  ('Briviesca','Monasterio de Rodilla',19.8),
  ('Monasterio de Rodilla','Burgos',28.5);

sql postgresql recursive-query graph-algorithm graph-theory

来源：https://stackoverflow.com/questions/62313871/recursive-query-to-give-a-route-in-postgresql

2条答案

按热度按时间

bis0qfac1#

我把你的问题理解为一个走图问题。如您的问题中所述，边是定向的（意味着您可以从 from_city_name 至 to_city_name ，但不是相反）。
下面是一个使用递归cte的方法。这个想法是从一个给定的城市出发，然后沿着所有可能的路线走，同时在arry中跟踪整个旅行路径。当检测到圆或到达目标城市时，递归停止。然后，外部查询过滤成功路径（可能没有、一个或多个）。

with recursive cte as (
    select 
        from_city_name, 
        to_city_name, 
        km_distance_num, 
        array[from_city_name::text, to_city_name::text] path
    from tb_route
    where from_city_name = 'Saint Jean Pied de Port'
    union all
    select 
        r.from_city_name, 
        r.to_city_name, 
        c.km_distance_num + r.km_distance_num,
        c.path || r.to_city_name::text
    from tb_route r
    inner join cte c on c.to_city_name = r.from_city_name
    where 
        not r.to_city_name = any(c.path) 
        and c.from_city_name <> 'Santiago de Compostela'
)
select 
    path[1] from_city_name, 
    to_city_name, 
    km_distance_num, 
    array_to_string(path, ' > ') path
from cte
where to_city_name = 'Santiago de Compostela';

db小提琴演示：

from_city_name          | to_city_name           | km_distance_num | path                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 
:---------------------- | :--------------------- | --------------: | :------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Saint Jean Pied de Port | Santiago de Compostela |           775.3 | Saint Jean Pied de Port > Roncesvalles > Zubiri > Pamplona/Iruña > Puente la Reina/Gares > Estella/Lizarra > Torres del Río > Logroño > Nájera > Santo Domingo de la Calzada > Belorado > Agés > Burgos > Hontanas > Boadilla del Camino > Carrión de los Condes > Terradillos de los Templarios > El Burgo Ranero > León > San Martín del Camino > Astorga > Foncebadón > Ponferrada > Villafranca del Bierzo > O Cebreiro > Triacastela > Sarria > Portomarín > Palas de Rei > Arzúa > Pedrouzo > Santiago de Compostela

赞(0）回复(0）举报 2021-07-29

4xrmg8kj2#

这里我留下了我最终得到的解决方案：

with recursive caminos(from_city_name, to_city_name, path, total_distance, terminar, ultima_ciudad) as (
    -- Consulta base
    select  to_city_name
            ,'Saint Jean Pied de Port' -- Cambiar Destino 
            ,concat(to_city_name, concat(' -> ', from_city_name)) 
            ,cast(km_distance_num as numeric(8,2))
            ,0 --No terminar
            ,from_city_name
    from    textil.tb_route 
    where   to_city_name = 'Santiago de Compostela' -- Cambiar Origen 
    union all
    -- Consulta recursiva
    select  caminos.from_city_name
            ,caminos.to_city_name
            ,concat(caminos.path, concat( ' -> ', tr.from_city_name))
            ,cast(caminos.total_distance + tr.km_distance_num as numeric(8,2))
            ,case when tr.from_city_name = caminos.to_city_name then 1 else 0 end
            ,tr.from_city_name  
    from    caminos inner join textil.tb_route tr on tr.to_city_name = caminos.ultima_ciudad and caminos.terminar != 1  
)
select from_city_name, to_city_name, path, total_distance 
from caminos 
where 1 = 1
and from_city_name = 'Santiago de Compostela' --Cambiar Origen 
and ultima_ciudad = 'Saint Jean Pied de Port' -- Cambiar Destino
;

赞(0）回复(0）举报 2021-07-29

我来回答

sql—在postgresql中提供路由的递归查询

2条答案

相关问题

热门标签

最新问答