位置: 编程技术 - 正文

在SQL Server中实现最短路径搜索的解决方法(在sql server数据库中)

编辑:rootadmin

开始这是去年的问题了,今天在整理邮件的时候才发现这个问题,感觉顶有意思的,特记录下来。

在表RelationGraph中,有三个字段(ID,Node,RelatedNode),其中Node和RelatedNode两个字段描述两个节点的连接关系;现在要求,找出从节点"p"至节点"j",最短路径(即经过的节点最少)。

图1.解析:了能够更好的描述表RelationGraph中字段Node和 RelatedNode的关系,我在这里特意使用一个图形来描述,如图2.

图2.

在图2,可清晰的看出各个节点直接如何相连,也可以清楚的看出节点"p"至节点"j"的的几种可能路径。

从上面可以看出第2种可能路径,经过的节点最少。

为了解决开始的问题,我参考了两种方法,

第1方法是,

参考单源最短路径算法:Dijkstra(迪杰斯特拉)算法,主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

图3.

第2方法是,

针对第1种方法的改进,就是采用多源点方法,这里就是以节点"p"和节点"j"为中心向外层扩展,直到两圆外切点,如图4. :

图4.实现:在接下来,我就描述在SQL Server中,如何实现。当然我这里采用的前面说的第2种方法,以"P"和"J"为始点像中心外层层扩展。

这里提供有表RelactionGraph的create& Insert数据的脚本:编写一个存储过程up_GetPath上面的存储过程,主要分为两大部分,第1部分是实现如何搜索,第2部分实现如何构造返回结果。其中第1部分的代码根据前面的方法2,通过@Node 和 @RelatedNode 两个节点向外层搜索,每次搜索返回的节点都保存至临时表#1和#2,再判断临时表#1和#2有没有出现切点,如果出现就说明已找到最短的路径(经过多节点数最少),否则就继续循环搜索,直到循环至最大的搜索深度(@MaxLevel smallint=)或找到切点。要是到层都没搜索到切点,将放弃搜索。这里使用最大可搜索深度@MaxLevel,目的是控制由于数据量大可能会导致性能差,因为在这里数据量与搜索性能成反比。代码中还说到一个正向和反向搜索,主要是相对Node 和 RelatedNode来说,它们两者互为参照对象,进行向外搜索使用。

下面是存储过程的执行:

你可以根据需要来,赋予@Node 和 @RelatedNode不同的值。拓展:前面的例子,可扩展至城市的公交路线,提供两个站点,搜索经过这两个站点最少站点公交路线;可以扩展至社区的人际关系的搜索,如一个人与另一个人想认识,那么他们直接要经过多少个人才可以。除了人与人直接有直接的朋友、亲戚关联,还可以通过人与物有关联找到人与人关联,如几个作家通过出版一个本,那么就说明这几个人可以通过某一本书的作者列表中找到他们存在共同出版书籍的关联,这为搜索两个人认识路径提供参考。这问题可能会非常大复杂,但可以这样的扩展。小结:这里只是找两个节点的所有路径中,节点数最少的路径,在实际的应用中,可能会碰到比这里更复杂的情况。在其他的环境或场景可能会带有长度,时间,多节点,多作用域等一些信息。无论如何,一般都要参考一些原理,算法来实现。

推荐整理分享在SQL Server中实现最短路径搜索的解决方法(在sql server数据库中),希望有所帮助,仅作参考,欢迎阅读内容。

在SQL Server中实现最短路径搜索的解决方法(在sql server数据库中)

文章相关热门搜索词:sqlserver有实例吗,sqlserver有实例吗,sqlserver有实例吗,sql server的实例是什么,在sql server中实现数据完整性,在sql server数据库中,在sql server中实现数据完整性,在sql server数据库中,内容如对您有帮助,希望把文章链接给更多的朋友!

基于SQL Server OS的任务调度机制详解 简介SQLServerOS是在Windows之上,用于服务SQLServer的一个用户级别的操作系统层次。它将操作系统部分的功能从整个SQLServer引擎中抽象出来,单独形成一层

SQLite数据库管理相关命令的使用介绍 1.创建数据库启动命令行,通过输入如下命令打开Shell模式的CLP:sqlite3test.db虽然我们提供了数据库名称,但如果该数据库不存在,SQLite实际上就未创建该

sql存储过程的使用和介绍 sqlserver存储过程语法定义总是很抽象。存储过程其实就是能完成一定操作的一组SQL语句,只不过这组语句是放在数据库中的(这里我们只谈SQLServer)。如

标签: 在sql server数据库中

本文链接地址:https://www.jiuchutong.com/biancheng/347522.html 转载请保留说明!

上一篇:SqlServer获取存储过程返回值的实例(sqlserver 获取字符位置)

下一篇:基于SQL Server OS的任务调度机制详解(基于sql server的大数据审计分析应用)

  • 小规模纳税人收入是含税还是不含税
  • 增值税加计扣除是什么意思啊
  • 应交印花税会计分录
  • 小规模印花税计税金额是什么
  • 财产转让应纳税额如果是负数怎么办
  • 非财政补助支出
  • 冲销管理费用如何计算
  • 国外客户给你寄来礼物怎么感谢
  • 非居民企业所得税
  • 包装物一次摊销的会计分录
  • 劳务分包服务费率
  • 劳务报酬算公积金基数吗
  • 银行手续费要纳进去吗
  • 供电局开具增值发票
  • 营改增金融商品范围
  • 学校发票抬头类型填企业还是非企业
  • 差额纳税的会计处理
  • 房产税入哪个科目
  • 运输费发票备注栏填不下
  • 生活服务的发票可以报销吗
  • 公司为员工负担个税怎么做账
  • 退回押金如果要退回吗
  • 两年利润都为负数,如何计算完成率
  • 残保金次年申报
  • 跨期费用会计处理
  • 购置土地税款怎么入账?
  • macbook自动弹出页面
  • 收到银行承兑汇票后,如何取钱
  • 固定资产改扩建过程中,发生的人工费用
  • 增值税当月申报次月缴纳吗
  • mac如何修改照片的尺寸大小
  • 使用权资产
  • 应收账款转让的风险
  • Win10 Build 19044.1320 (21H2)更新补丁KB5006738预览版发布(附更新修复内容汇总)
  • php字符串定义
  • 收到某公司的钱的会计分录
  • 冲回上年多提的费用会计分录
  • musirc4.71.exe - musirc4是什么进程文件 有什么作用
  • 泰姬陵 (© Michele Falzone/plainpicture)
  • 计提工会经费会计账务处理
  • 自产商品公司自用算增值税吗
  • php操作mysql数据库
  • 计算机视角技术
  • 最新windows11安装要求
  • 微信随机红包表情包怎么弄
  • PHP+JQuery+Ajax实现分页方法详解
  • 固定资产清理应交增值税怎么算
  • 采购和销售都做的叫什么
  • 印花税是不是每个月都要交
  • 采购货未到收到发票
  • 结转财务费用时怎么做账
  • 新公司建账初始数据
  • 捐赠支出怎么抵税
  • 广告公司的广告制作费计入什么科目
  • 学历教育服务增值税
  • 税务滞纳金计入什么会计科目
  • 产权交易所交易流程
  • 接受捐赠后怎么发表感言
  • 研发费用加计扣除的条件
  • 购进中央空调可以抵税吗
  • 收到投资厂房有折旧的记账凭证怎么处理
  • 简单介绍清明上河图
  • mysqlvarchar汉字
  • 主板如何清除cmos
  • win7如何开启VT
  • win7系统的启动项在哪里
  • win7搜索无法使用
  • ubuntu和windows文件互传
  • ext.grid.editorgridpanel
  • 编程语言javascript
  • js确认框s弹出框确定和取消
  • shell脚本编程实例
  • jquery中的事件
  • node.js gui
  • javascriptcsdn
  • jquery.load()方法,刷新网页
  • multiset volatile
  • 单位轿车出售怎么处理
  • 五证合一后工商变更完还要税务变更吗
  • 电力营销岗
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设