位置: 编程技术 - 正文
在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数据库中)，希望有所帮助，仅作参考，欢迎阅读内容。
文章相关热门搜索词: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 转载请保留说明！
