sql - SQL:找到最长的路径

我对图论完全不熟悉，很难理解这个问题。下面给出一个简单的表（单向），如何使用select语句从定义的起点和终点找到最长的路径？
似乎需要一些递归语句，但我很难理解它。如果有人能帮忙举个例子，那就太好了。
我在用Postgresql。

+ -------- + ------ + -------- +
| fromnode | tonode | distance |
+ -------- + ------ + -------- +
| 1        | 2      | 1306     |
| 1        | 6      | 2661     |
| 2        | 3      | 919      |
| 2        | 4      | 629      |
| 3        | 4      | 435      |
| 3        | 5      | 1225     |
| 3        | 7      | 1983     |
| 5        | 6      | 1483     |
| 5        | 7      | 1258     |
+ -------- + ------ + -------- +

最佳答案

您可以对此递归CTE执行以下操作：

with recursive params as (
  select 1 fromnode,
         7 tonode
),
paths as (
    select ARRAY[fromnode] pathnodes,
           fromnode lastnode,
           0 sumdistance
    from   params
  union all
    select     pathnodes || e.tonode,
               e.tonode,
               sumdistance + e.distance
    from       paths
    join       edges e on e.fromnode = lastnode
    cross join params p
    where      e.fromnode <> p.tonode
    and        e.tonode <> all(pathnodes)
)
select   pathnodes, sumdistance
from     paths, params
where    lastnode = tonode
order by sumdistance desc
limit    1

（根据列的类型，这里和那里可能需要强制转换。）
http://rextester.com/VRFHK43986
但是，这将始终计算所有可能的路径（从params.fromnode开始；不带圆）&然后将选择其中最长的路径。
编辑：上面的解决方案假设图是有方向的。如果它是无向的，您可以修改它，以使用从tonode到fromnode的边：

with recursive params as (
  select 7 fromnode,
         1 tonode
),
paths as (
    select ARRAY[fromnode] pathnodes,
           fromnode lastnode,
           0 sumdistance
    from   params
  union all
    select     pathnodes || e.nodeb,
               e.nodeb,
               sumdistance + e.distance
    from       paths
    cross join lateral (select fromnode nodea,
                               tonode   nodeb,
                               distance
                        from   edges
                        where  fromnode = lastnode
                        union
                        select tonode   nodea,
                               fromnode nodeb,
                               distance
                        from   edges
                        where  tonode = lastnode) e
    cross join params p
    where      e.nodea <> p.tonode
    and        e.nodeb <> all(pathnodes)
)
select   pathnodes, sumdistance
from     paths, params
where    lastnode = tonode
order by sumdistance desc
limit    1;

但是，在(LEAST(fromnode, tonode), GREATEST(fromnode, tonode))上可能需要一个唯一的索引以避免重复，其中row1.fromnode = row2.tonode and row1.tonode = row2.fromnode。（查询不处理这种类型的复制，在这种情况下将使用两个单独的路径进行计算）。
http://rextester.com/XEGAX60117