在SQL Server中实现最短路径搜索的解决方法-木庄网络博客

本文整理自网络，侵删。

开始

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

在表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数据的脚本：

代码如下:

use TestDB

if object_id('RelactionGraph') Is not null drop table RelactionGraph

create table RelactionGraph(ID int identity,Item nvarchar(50),RelactionItem nvarchar(20),constraint PK_RelactionGraph primary key(ID))

create nonclustered index IX_RelactionGraph_Item on RelactionGraph(Item) include(RelactionItem)

create nonclustered index IX_RelactionGraph_RelactionItem on RelactionGraph(RelactionItem) include(Item)

insert into RelactionGraph (Item, RelactionItem ) values

('a','b'),('a','c'),('a','d'),('a','e'),

('b','f'),('b','g'),('b','h'),

('c','i'),('c','j'),

('f','k'),('f','l'),

('k','o'),('k','p'),

('o','i'),('o','l')

数据库系统概念第6版

￥41.1元 机械工业出版社

本书主要讲述了数据模型、基于对象的数据库和XML、数据存储和查询、事务管理、体系结构等方面的内容。