一个求最短总路径的问题

newkid

既然是经典问题，就应该有前人研究出来的算法，比如：
https://blog.forec.cn/2015/09/23/Graph-Algorithms4/

如果用SQL那只能暴力求出所有路径的组合然后去重复并计算总成本。

newkid

用SQL暴力算了一小时：

create table p2 as
with d as (
select 1 id,1 d from dual union all
select 2,23 from dual union all
select 3,34 from dual union all
select 4,125 from dual union all
select 5,145 from dual )
,p as (
select cast(sys_connect_by_path(from_id||':'||to_id||':'||len,',') as varchar2(1000)) as path,to_id
  from trip
where to_id in (select d from d)
start with from_id=12345
connect by from_id=prior to_id
)
,p2 (path,to_id,cnt) as (
select cast(path as varchar2(2000)),to_id,d.id from p,d where p.to_id=d.d and d.id=1
union all
select cast(p2.path||p.path as varchar2(2000)),p.to_id,p2.cnt+1
from p2,p,d
where p2.cnt+1=d.id and p.to_id=d.d
)
select * from p2 where cnt=5;


select * from (
select *
from p2
     ,lateral(
       select sum(distance) as distance
         from ( select distinct from_id,to_id,distance
                  from (select regexp_substr(node,'[^:]+',1,1) from_id,regexp_substr(node,'[^:]+',1,2) to_id,regexp_substr(node,'[^:]+',1,3) distance
                          from ( select regexp_substr(p2.path,'[^,]+',1,level) as node
                                  from dual
                                  connect by level<=regexp_count(p2.path,',')
                               )
                       )
              )
      )
order by distance
)
where rownum=1;

PATH
-----------------------------------------------------------------------------------------------------------------------------
     TO_ID        CNT   DISTANCE
---------- ---------- ----------
,12345:125:30,125:1:0,12345:1234:49,1234:234:0,234:23:1,12345:1234:49,1234:134:0,134:34:0,12345:125:30,12345:145:50
       145          5        130


Elapsed: 00:00:54.68

〇〇

谢谢帮助

〇〇

distinct很巧妙，但是笛卡尔积，有没有办法中间剪枝

〇〇

另外，看时间是54秒，怎么是1小时？
我的p2改用cte很快
create table p2 as
with d as (
select 1 id,1 d union all
select 2,23 union all
select 3,34 union all
select 4,125 union all
select 5,145 ),
p(path,to_id) as
(select from_id||':'||to_id||':'||len ,to_id from trip where from_id=12345
union all
select p.path||','||trip.from_id||':'||trip.to_id||':'||trip.len,trip.to_id from trip,p
where trip.from_id=p.to_id)
select * from p where to_id in (select d from d);

newkid

我看错了，应该是一分钟。我弄完了就没管它，一小时后才想起去看结果。最初写法是一整个SQL，但是12c会崩溃，所以先建了临时表。我的算法是事后求组合，所以是没法剪枝的。在生成路径的过程中可以剪枝但用SQL没法做。先用Dijkstra 算法求出每个点到每个目的地的代价，在路径分叉处穷尽所有人分组的组合取最小。分叉后的成本计算用递归函数。

〇〇

从123456开始的6级数据

〇〇

把newkid的改写成postgres
create table p as
with RECURSIVE d as (
select 1 id,1 d union all
select 2,23 union all
select 3,34 union all
select 4,125 union all
select 5,145 ),
p(path,to_id) as
(select from_id||':'||to_id||':'||len ,to_id from trip where from_id=12345
union all
select p.path||','||trip.from_id||':'||trip.to_id||':'||trip.len,trip.to_id from trip,p
where trip.from_id=p.to_id)
select * from p where to_id in (select d from d);

SELECT 107
时间：23.861 ms

create table p2 as
with RECURSIVE d as (
select 1 id,1 d union all
select 2,23 union all
select 3,34 union all
select 4,125 union all
select 5,145 ),
p2 (path,to_id,cnt) as (
select cast(path as varchar(2000)),to_id,d.id from p,d where p.to_id=d.d and d.id=1
union all
select cast(p2.path||','||p.path as varchar(2000)),p.to_id,p2.cnt+1
from p2,p,d
where p2.cnt+1=d.id and p.to_id=d.d
)
select * from p2 where cnt=5;

SELECT 114075
Time: 2359.945 ms (00:02.360)

with d as
(select p2.*,regexp_split_to_table(path,',') node from p2)
,d2 as
(select d.*,regexp_split_to_array(node,':') arr from d)
select * from
(
select path,sum(dis) distance
from(select distinct path, arr[1] from_id,arr[2] to_id,arr[3]::int dis from d2)y
group by path)x
order by distance
limit 1;
                                                              path                                                              | distance
--------------------------------------------------------------------------------------------------------------------------------+----------
12345:1234:49,1234:123:0,123:1:0,12345:1234:49,1234:234:0,234:23:1,12345:1234:49,1234:134:0,134:34:0,12345:125:30,12345:145:50 |   130
(1 行记录)


Time: 73903.664 ms (01:13.904)

〇〇

把distinct操作提前到node,快了很多
with d as
(select p2.*,unnest(array(select distinct unnest(regexp_split_to_array(path,',')))) node from p2)
,d2 as
(select d.*,regexp_split_to_array(node,':') arr from d)
select * from
(
select path,sum(dis) distance
from(select path, arr[1] from_id,arr[2] to_id,arr[3]::int dis from d2)y
group by path)x
order by distance
limit 1;
Time: 15025.549 ms (00:15.026)

〇〇

6级，p2创建失败
create table p as
with RECURSIVE d as (
select 1 id,1 d union all
select 2,23 union all
select 3,34 union all
select 4,125 union all
select 5,145 ),
p(path,to_id) as
(select from_id||':'||to_id||':'||len ,to_id from trip where from_id=123456
union all
select p.path||','||trip.from_id||':'||trip.to_id||':'||trip.len,trip.to_id from trip,p
where trip.from_id=p.to_id)
select * from p where to_id in (select d from d);

SELECT 717
时间：34.603 ms

create table p2 as
with RECURSIVE d as (
select 1 id,1 d union all
select 2,23 union all
select 3,34 union all
select 4,125 union all
select 5,145 ),
p2 (path,to_id,cnt) as (
select cast(path as varchar(2000)),to_id,d.id from p,d where p.to_id=d.d and d.id=1
union all
select cast(p2.path||','||p.path as varchar(2000)),p.to_id,p2.cnt+1
from p2,p,d
where p2.cnt+1=d.id and p.to_id=d.d
)
select * from p2 where cnt=5;
ERROR:  could not write to file "base/pgsql_tmp/pgsql_tmp8000.55": No space left on device
Time: 36069.743 ms (00:36.070)