使用递归 postgreSql 查找最短和最长路径

Question

我不熟悉 PostgreSQL 和递归查询，遇到以下问题：我有以下表格

节点（id，颜色）
边(n1,n2)

我必须编写一个带有递归语句的查询，returns 每对节点之间的最短和最长路径。输出应如下所示：(id1,id2, shortpath,longpath)

Answer 1

SQL 可能不是执行此操作的最佳工具，但您可以使用递归 CTE 来完成。

例如：

with recursive
p as (
  select n1, n2 as n, '/' || n1 || '/' as path, 1 as cost from edge where n1 = 'A'
 union all
  select p.n1, e.n2, p.path || e.n2 || '/', cost + 1
  from p
  join edge e on e.n1 = p.n
  where p.path not like '/' || e.n1 || '/'
    and p.n <> 'E'
)
select 'A' as source, 'E' as target, 
  (select min(cost) from p where n = 'E'),
  (select max(cost) from p where n = 'E');

结果：

source  target  min  max 
------- ------- ---- --- 
A       E       2    4

请参阅 DB Fiddle 中的运行示例。

使用递归 postgreSql 查找最短和最长路径

Find shortest and longest path with recursive postgreSql

sql

postgresql

recursive-query