SQL 最短路径

Question

我有一个 table，它有一堆边，由 CREATE TABLE example ([FromId] INT, [ToId] INT); 制作（我必须使用这样的格式）。我试图找到给定“FromId”到“ToId”之间的最短路径（即我们试图从一个节点到另一个节点）。

我知道有一条最短路径，但我不确定如何在我的案例中使用它，因为我没有声明我的 table 一个 SQL 图。

抱歉，如果这是一个愚蠢的问题，我是 Whosebug 和 SQL 的新手。我正在使用 SQLite.

Answer 1

这是一个递归 CTE。这是一种方法：

with recursive cte as (
      select f, t, 1 as lev, (f || '->' || t) as path
      from edges
      where f = 1
      union all
      select e.f, e.t, lev + 1 , (cte.path || '->' || e.t) as path
      from cte join
           edges e
           on e.f = cte.t
      where lev < 100 or e.t = 4
     )
select cte.*
from cte
where cte.t = 4
order by lev
limit 1;

这将路径长度限制为 100（在大多数情况下是合理的最大值）以处理图表中的潜在循环。

Here 是一个 db<>fiddle.

SQL 最短路径

SQL Shortest Path

sql

sqlite

shortest-path