递归查询以在postgreSQL中给出路由

Question

我必须在 pSQL 中执行递归函数才能获得以下查询：

我有一个名为 tb_route 的 table，from_city 和 to_city
我还有另一列显示不同城市之间的距离（以公里为单位）。

table 是递归构建的。我必须制作一个递归 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...

Table:

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);
```

Answer 1

我将您的问题理解为图形遍历问题。如您的问题所述，边是有向的（这意味着您可以从 from_city_name 到 to_city_name，但不能反过来）。

这是一种使用递归 CTE 的方法。这个想法是从一个给定的城市开始，然后沿着所有可能的路线走，同时随时跟踪整个旅行路径。当检测到圆圈或到达目标城市时，递归停止。然后，外部查询过滤成功的路径（可能有none，一个或几个）。

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

Demo on DB Fiddle:

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

Answer 2

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

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
;

递归查询以在postgreSQL中给出路由

Recursive query to give a route in postgreSQL

sql

postgresql

graph-theory

recursive-query

graph-algorithm