好吧，使用sql实现Dijkstra算法

2022-01-22 17:49:40

我本来不想做这么蛋疼的事情的，可是更蛋疼的是我看了王大神的博客然后中毒了！我发誓再！不！看！了！
不过问题本身还是有一点意思的，正好学过图论没有实现过dijkstra，刚好在慕课上又学了一点pl/sql。然后就这样一个题目做了一晚上然后还是不想睡觉，赶紧写点代码来压压惊。
好吧，使用sql实现Dijkstra算法

图片出自http://blog.jobbole.com/70639/ 《真正统治世界的十大算法》
顶点可以忽略，对于有权有向边，一般必须的属性：起点、终点、距离，最后表建出来就是这样
好吧，使用sql实现Dijkstra算法

create table EDGE

(

  SOURCE      VARCHAR2(10) not null,

  DESTINATION VARCHAR2(10) not null,

  DISTANCE    NUMBER(4)

)

对于dijkstra算法来说是计算结果是从源点到其他顶点的最短距离以及最短路径，这个好像没办法用变量保存
所以再建立一张全局临时表保存计算结果

create global temporary table DISTANCE

(

  DESTINATION VARCHAR2(10),--目的点

  DISTANCE    NUMBER(4),--最短路径

  PREVIOUS    VARCHAR2(10),--经过的上一个节点

  SOURCED     VARCHAR2(1)--是否当过源点

)

on commit delete rows;

-- Created on 2015/7/21 by cbwleft

declare

  -- Local variables here

  va_source edge.source%type:='s';

  va_distance Integer:=0;

begin

  -- Test statements here

  insert into distance(destination,distance,previous) values(va_source,0,va_source);--源点到自己的距离为0

  loop

    for edge in (select * from edge where source=va_source)--查询邻接边

    loop

      merge into distance t using dual on (t.destination  = edge.destination)

        when matched then update set distance = edge.distance+va_distance,previous=va_source where distance>edge.distance+va_distance--如果有更短路径则更新

        when not matched then insert  values (edge.destination,edge.distance+va_distance,va_source,'');--加入邻接点

    end loop;

    select max(destination),max(distance) into va_source,va_distance from

        (select * from distance t where sourced ='' order by distance) where rownum=1;--贪心

    exit when va_source is null;

    update distance set sourced='' where destination=va_source;

  end loop;

end;

最后在事务提交前执行查询，路径好像最后还得用递归统计一次。
好吧，使用sql实现Dijkstra算法

比如说查询x到源点的最短路径

SELECT wm_concat(destination) FROM distance START WITH destination = 'x' CONNECT BY destination = PRIOR previous

结果是x,t,y,s

码农公寓

相关文章