位置: 编程技术 - 正文

在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的大数据审计分析应用)

  • 企业收到购买标书的增值税专用发票可以抵扣吗?
  • 企业存款利息收入缴纳企业所得税吗
  • 企业所得税优惠政策最新2023小微企业
  • 个人所得税征收范围及税率
  • 汽车销售和租赁哪个大
  • 项目差旅费能计入项目费用吗
  • 增值税抵扣凭证装订要求
  • 商业发票和形式发票英文
  • 期末小规模纳税人差额纳税的会计处理分析
  • 有外经证的计税收入怎么算?
  • 收到补助款的会计分录
  • 减半征收企业所得税税率
  • 原材料入库单运费要怎么计入?
  • 劳务发票普票怎么开
  • 小规模纳税人印花税怎样计算
  • 营改增开始试点到普及的行业
  • 融资租赁购入固定资产开票吗
  • 开票人为什么不能改
  • 折扣销售怎么确认
  • thinkpad预装的office怎么激活
  • 分级核算下的建议有哪些
  • 应交增值税视频讲解
  • php数组实现原理
  • 附有退回条件的销售商
  • 营改增后固定资产报废处置收入计税
  • 冲减管理费用是什么意思
  • wordpress建网站详细教程
  • php字符串包含某个字符串
  • 微信小程序分包加载
  • 蓝湖怎么用的
  • 实现产供销一体化
  • 项目差旅费能计入项目费用吗
  • 汽车客运补充车道标志
  • 如何快速使用验证码
  • 什么是Unicode
  • gmt微调
  • 【历史上的今天】3 月 29 日:“机器人三定律”问世;电脑动画首次获得奥斯卡;Caldera Linux 沉浮史
  • 国内php大牛
  • python描述器有什么用
  • 母子公司转让不动产 契税
  • 帝国cms如何搭建的
  • 股权激励和期权激励
  • 专项附加可以叠加吗
  • case语句怎么执行
  • 专票抵扣税款的会计分录
  • 全额计提坏账准备有什么作用
  • 生活垃圾处理费合法吗
  • 股东分红申报个税怎么填
  • 长期闲置机器设备评估方法
  • 应交税费科目怎么调整
  • 银行开户的费用计入什么科目
  • 对公转账个人垫付怎么写
  • 小规模纳税人购车是怎么抵税的
  • 充值优惠怎么写
  • 收到赞助费如何开发票
  • 税控盘减免税款会计分录一般纳税人
  • 企业管理费的计算基础
  • 实物投资的会计科目
  • 税收分类编码填错有影响吗
  • 分公司从业人数填越少越好吗
  • 小规模纳税人买车可以抵扣哪些税
  • 无形资产管理的特点
  • mysql批量修改字段值
  • MySQL(win7x64 5.7.16版本)下载、安装、配置与使用的详细图文教程
  • ubuntu 操作系统
  • mac os怎么删除用户
  • bios启动项正确设置
  • userint32.exe - userint32是什么进程
  • centos安装教程详解
  • win7系统怎么设置微信多开
  • js原生实现ajax
  • js数据的基本类型有哪些
  • linux命令行命令
  • 批处理实例
  • putty自动退出
  • android的数据储存方式
  • javascript零基础入门书籍
  • delphi7教程
  • 销售车位需要交房产税吗
  • 苏州封闭式高中
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设