如何用 SQL 实现 Dijkstra 的最短路径算法

发布网友发布时间：2022-04-22 16:44

共2个回答

懂视网时间：2022-04-30 09:14

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

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

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 where distance>edge.distance+va_distance--更新距离 when not matched then insert values (edge.destination,edge.distance+va_distance,va_source,‘0‘);--加入邻接点 end loop; select max(destination),max(distance) into va_source,va_distance from (select * from distance t where sourced =‘0‘ order by distance) where rownum=1;--贪心 exit when va_source is null; update distance set sourced=‘1‘ where destination=va_source; end loop; end;

最后在事务提交前执行查询，路径好像最后还得用递归统计一次。
技术分享

好吧脑壳晕了，明天再检查正确性。

好吧，使用sql实现Dijkstra算法

标签：

热心网友时间：2022-04-30 06:22

您好.

开个表当dijkstra里面那个【我从哪里来】数组，剩下的用T-SQL都一样，分支循环样样能写

我不知道为什么用关系数据库的sql来搞图模型的算法～先考虑数据怎么存吧。

如果用图数据库neo4j的类sql的cypher，分分钟搞定啊

如果还有问题，可以继续追问，感谢。