递归查询以获取PostgreSQL中的路径

Question

我需要在pSQL中编写一个递归函数以获取以下查询：

• 我有一张名为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);
```

- Stephi

Answer 1

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

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
;

- Stephi

Answer 2

我理解你的问题是一个图遍历问题。根据你的问题描述，边是有向的（意味着你可以从from_city_name到达to_city_name，但反过来不行）。

这里提供一种使用递归CTE的方法。思路是从给定的城市开始，然后沿着所有可能的路径前进，同时在数组中跟踪整个旅行路径。递归停止的条件是检测到一个圆圈，或者到达目标城市。然后，外部查询会过滤成功的路径（可能没有、一个或多个）。

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 Fiddle上的演示:

from_city_name | to_city_name | km_distance_num | path :---------------------- | :--------------------- | --------------: | :------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 圣让皮德德波特 | 圣地亚哥德孔波斯特拉 | 775.3 | 圣让皮德德波特 > 龙塞瓦莱斯 > 祖比里 > 帕姆普洛纳/伊鲁尼亚 > 普恩特拉雷纳/加雷斯 > 埃斯特拉/利扎拉 > 托雷斯德尔里奥 > 洛格罗尼奥 > 纳杰拉 > 圣多明戈德拉卡尔萨达 > 贝洛拉多 > 阿赫斯 > 布尔戈斯 > 翁塔纳斯 > 博阿迪利亚德尔卡米诺 > 卡里翁德洛斯孔德斯 > 圣殿骑士的特拉德留斯 > 埃尔布尔戈拉内罗 > 莱昂 > 圣马丁德尔卡米诺 > 阿斯托加 > 丰塞巴东 > 庞费拉达 > 比利亚弗兰卡德尔比尔佐 > 奥塞布雷罗 > 特里亚卡斯特拉 > 萨里亚 > 波托马林 > 帕拉斯德雷伊 > 阿尔苏瓦 > 佩德罗佐 > 圣地亚哥德孔波斯特拉

- GMB

---

你好！我运行了代码，但在pgadmin 4中出现了以下错误：ERROR: recursive query "cte" column 3 has type numeric(5,2) in non-recursive term but type numeric overall LINE 18: km_distance_num, ^ HINT: Cast the output of the non-recursive term to the correct type. SQL state: 42804 Character: 715 - Stephi

@Stephi：你需要进行一些额外的转换...我建议使用numeric而不是numeric(n, m)，就像在我的db fiddle中展示的那样。注意：作为问题的提出者，你可以自由选择接受任何你喜欢的答案（包括你自己的）- 但是让我指出，你的查询基本上就是我的查询，只是有一些小的改动（而且你删除了防止循环的代码，这不一定是一个好主意）。我认为你应该接受我的答案！ - GMB

好的！谢谢！ - Stephi