位置: 编程技术 - 正文

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

  • 工程会计税率
  • 房地产企业什么时候开具正式发票
  • 股票交易印花税降低
  • 法人工资怎么发最划算
  • 所得税费用影响净利润吗
  • 个人销售货物缴增值税吗
  • 增值税专票税种
  • 给职工发奖金有什么规定吗
  • 留存收益转增资本有什么好处
  • 建筑企业城建税及教育附加税率
  • 抵税更正申报需要多久
  • 取得进项票当月未认证
  • 电子普通发票入账规则
  • 工会发放员工福利的通知
  • 专家评审费个人所得税计算公式
  • 填报退税
  • 客户忠诚度的表现行为有哪些
  • 低价购买债权后可否向债务人全额主张债务
  • 季度不含税收入30万以内免增值税
  • 生产性企业购买粽子可以开专票吗
  • 非货币性资产交换的会计处理
  • 净利润与未分配利润的勾稽关系
  • mac os x v10.10
  • 预提费用的对应科目
  • 网速第一的国家
  • nullable object must have a value
  • 完美替身好看吗
  • pace框架
  • 以公允价值计量的金融资产不计提损失准备
  • 融资租赁利息资本化条件
  • Python计算机视觉———照相机标定
  • ls -lh命令
  • 神经网络浅讲
  • php获取文件信息
  • 个税系统怎么查询已申报个人明细
  • 工程完工收到工程发票
  • 织梦专题页模板
  • 拓展费怎么做账
  • 购销合同印花税税率
  • 所得税汇算清缴退税会计分录怎么做
  • 公司捐赠给个人公司要交税吗
  • sqlserver FOR XML PATH 语句的应用
  • 扫码开票软件
  • 物流公司过户给我需要做什么
  • 营改增会计分录怎么做
  • 小规模购置金税盘抵税如何申报
  • 房地产结转收入的条件
  • MS-SQL Server 2005 其中三个版本的比较
  • MySQL数据迁移到oracle
  • win8安装虚拟机的步骤
  • xp磁盘管理打不开
  • 苹果mac升级系统
  • win7怎样关闭u盘保护功能
  • linux防火墙设置firewalld
  • centos6.5安装步骤
  • alp是什么文件
  • 电脑avg是什么软件
  • 禁用windows installer没有用
  • linux常用命令修改
  • 怎么修改Windows账户密码
  • xp系统怎么卸载驱动程序
  • Linux内核级别的资源隔离机制是
  • win7无法识别usb设备怎么办 五大方法来解决
  • Aero glass for Win8.1黑屏/不兼容弹窗的解决方法介绍
  • android如何导入文件
  • 安卓手机微信取消窗口化
  • 用bat脚本快速编程
  • unity shader lod
  • node.js 教程
  • linux网络编程有什么用
  • 一个页面
  • node.js mac
  • js怎么设置图片大小
  • eclipse自动生成
  • 百旺税控密码忘记了怎么找回
  • 增值税的进项税额转出是什么意思
  • 税务网络安全制度
  • 关注龙江医保
  • 江西国家税务局电子税务局
  • 代理记账公司有什么风险吗?
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设