首页 / 算法 / SQL版本的Dijkstra最短路径算法

SQL版本的Dijkstra最短路径算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了SQL版本的Dijkstra最短路径算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1767字，纯文字阅读大概需要3分钟。

内容图文

受这篇文章《SQL,NoSQL以及数据库的实质》结尾处题目的启发，我尝试写了一个SQL版本的Dijkstra最短路径算法。算法描述如下：

前提假设:
     Hive支持Stored Procedure
     或者
     Mysql支持Insert into、insert overwrite、create table as select操作
 
数据结构:
Table meta_distances(
     src int,
     dst int,
     distance int
)
 
Table known_nodes(
     node int,
     distance int
)
Table unknown_nodes(
     node int,
     distance int
)
求节点1到其他所有节点的距离
 
初始，各表包含的数据:
meta_distances:
     各个节点之间的距离
known_nodes:
     (1,0)
unknown_nodes:
     (2, MaxInt)
     (3, MaxInt)
     (4, MaxInt)
     …...
     (n, MaxInt)
 
     pivot_node=1
            Create
            Procedure Dijkstra(IN pivot_node int)
     Begindeclare unknown_nodes_count intdefault1While unknown_nodes_count>0 do
               
               droptable tmp_distance_a
               //计算unknown_nodes中每一个node若经过pivot_node，与源点的距离
               createtable tmp_distance_a
               asselect
                    dst,
                    distance+(select distance from known_nodes where node=pivot_node)
               from
                    (selectdistinct
                         meta_distances.*from
                         meta_distances as f1,
                         unknown_nodes as f2
                    where
                         f1.dst=f2.node
                         and
                         src=pivot_node
                    )as tmp
                    
              //更新unknown_nodes的距离信息
               insert overwrite table unknown_nodes
               select
                    f2.node
                    IF(f1.node isnull,
                         f2.distance,
                         IF(f1.distance>f2.distance,
                              f2.distance,
                              f1.distance
                         )
                    )
               from
                    tmp_distance_a as f1
               rightouterjoin
                    unknown_nodes as f2
               on
                    f1.dst=f2.node

               //挑选出最小的node，放入known_nodes中
               insertintotable known_nodes
               select
                    node,
                    distance
               from
                    unknown_nodes
               where
                    distance=min(distance)
              
               //挑选出最小的node，最为下一个pivot_node
               select
                    node
                    into pivot_node
               from
                    unknown_nodes
               where
                    distance=min(distance)

               //从unknown_nodes中删除最小node
               deletefrom
                    unknown_nodes
               where
                    distance=min(distance)
               
               //计算unknown_nodes中剩余node的数量
               selectcount(*)
                    into unknown_nodes_count
               from
                    unknown_nodes

          EndWhileEnd

也许有人会问：用SQL实现这个算法的意义是什么？它与用常规语言写出来的程序相比，几乎没有任何优势。当数据规模控制在一定范围之内时，我承认是这样的。但是，设想如果我们面对的节点规模是几百万甚至几千万数量级，而我们的机器只有几个G内存时，如何处理？

答案是：Hive+SQL。

原文：http://www.cnblogs.com/linghuaichong/p/4367055.html

内容总结

以上是互联网集市为您收集整理的SQL版本的Dijkstra最短路径算法全部内容，希望文章能够帮你解决SQL版本的Dijkstra最短路径算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1173235.html

来源：【匿名】