测试运行

项目
07/10/2015

使用 SQL 基于图形的最短路径分析

David McCaffrey 在本专栏中，我将说明在具有在 SQL 数据库中存储的图形数据并且想要使用本机 T-SQL 语言处理的情况下，如何实现基于图形的最短路径分析。传统的最短路径方法假定图形表示形式存储于计算机内存的数据结构中。但大型图形（例如表示社交网络的那些图形）常常不适合放置于内存中，因此，使用 SQL 存储和处理它们就是一个选项。理解我将要介绍的内容的最佳方式就是看一下图 1 中的示例图形，以及图 2 中运行演示的屏幕快照。

Demo Graph for Shortest-Path Analysis
图 1 用于最短路径分析的演示图形

Shortest-Path Analysis with T-SQL
图 2 使用 T-SQL 进行最短路径分析

图 1 中所示的图形是有意缩小的，该图形具有八个节点（有时候称作顶点）并且具有 111 到 888 的 ID。您可以设想节点表示人员或计算机。节点之间的方向箭头（通常称作边缘）是关系。您可以设想两个节点之间的箭头表示电子邮件的交换。在这个示例中，图形边缘具有由值 1.0 或 2.0 指示的权重。根据您的特定问题情况，边缘权重可以具有不同的意义。例如，这些权重可以表示社交关系的某种度量，或者作为发送消息的时间的指示符。

“最短路径”一词可以具有不同的含义。假定您对用户 222 和用户 444 之间的最短路径感兴趣。这可能意味着要获取从 222 到 444 的最小跃点数目，该数目可以是 4（222 到 333 到 666 到 777 到 444）。或者，最短路径可以意味着 222 和 444 之间权重的最小总和，这将会是 5.0（1.0 + 1.0 + 1.0 + 2.0）。

在图 2 中的左窗口中，您可以看到我在 SQL Server Management Studio 中正在使用一个数据库，该数据库名为 dbShortPathDemo。在右上窗口中，我具有一个名为 ShortestPath.sql 的 T-SQL 脚本，该脚本定义演示数据库并用与图 1 中的图形相对应的信息填充演示数据库，而且右上窗口中还有定义名为 usp_ShortestPath 的存储过程的代码。调用该存储过程只是为了分析用户 222 和用户 444 之间的最短路径。在右下窗口中，您可以看到结果。最短路径由字符串“444;777;666;333;222”提供。就权重而言，最短路径是 5.0（显示时不是小数）。该图像的右下部分显示名为 tblAlgorithmData 的表的最后状态，这是实现最短路径代码的关键。

在随后的部分中，我将逐步为您介绍生成了图 2 中的屏幕快照的 T-SQL 代码，这样，您将能够对该代码进行改编来处理您自己的问题情形。我假定您主要是非 SQL 开发人员（这意味着您最常使用 C# 或其他一些过程编程语言），但具有一些基本的 SQL 知识。我展示了在本文中说明的所有 T-SQL 代码；这些代码也在 archive.msdn.microsoft.com/mag201212TestRun 中提供。

设置演示数据库

为了创建演示数据库，我启动了 SQL Server Management Studio 并且连接到了我的服务器计算机。我使用了 SQL Server 2008，但通过一些小修改，在此处展示的代码应该可用于大多数更早的 SQL Server 版本以及所有更新的 SQL Server 版本。在连接后，我单击了“文件”|“新建查询”以便显示编辑窗口，然后键入了 T-SQL 代码以便创建我的虚拟数据库：

use master
go
if exists(select * from sys.sysdatabases 
  where name='dbShortPathDemo')
drop database dbShortPathDemo
go
create database dbShortPathDemo
go
use dbShortPathDemo
go

在这里，我使用了 create database 语句的所有默认参数值。在许多情况下，您将使用具有真实数据的现有数据库，但我建议使用较小的演示数据库。我喜欢将小写的 T-SQL 代码用于大多数部分，这可能会冒犯 SQL 纯粹主义者。我使用了鼠标来选择这 9 行代码，然后点击 F5 键以便执行这些代码。在确认演示数据库已创建后，我将该脚本另存为 ShortestPath.sql。

接下来，我在该演示数据库内创建了一个表，以便承载定义要分析的图形的数据：

create table tblGraph
(
fromNode bigint not null,
toNode bigint not null,
edgeWeight real not null
)
go

我使用了鼠标以便只突出显示这七行代码（这样，我将不会重新执行以前的行），然后点击 F5 以便创建该表。我将类型 bigint 用于节点 ID。您可能会遇到的其他常见节点 ID 类型包括用于相对简单的员工 ID 的 int 以及采用 xxx-xx-xxxx 格式的用于社会安全号码的 varchar(11)。我使用 real 类型用于列 edgeWeight。 T-SQL 类型 real 只是用于 float(24) 的方便的别名，这类似于 C# 类型 double。在许多情况下，在节点之间您可能没有显式的边缘权重，因此您可以省略 edgeWeight 列。

接下来，我通过输入、突出显示和执行以下 15 行代码，填充了表 tblGraph：

insert into tblGraph values(111,222,1.0)
insert into tblGraph values(111,555,1.0)
insert into tblGraph values(222,111,2.0)
insert into tblGraph values(222,333,1.0)
insert into tblGraph values(222,555,1.0)
insert into tblGraph values(333,666,1.0)
insert into tblGraph values(333,888,1.0)
insert into tblGraph values(444,888,1.0)
insert into tblGraph values(555,111,2.0)
insert into tblGraph values(555,666,1.0)
insert into tblGraph values(666,333,2.0)
insert into tblGraph values(666,777,1.0)
insert into tblGraph values(777,444,2.0)
insert into tblGraph values(777,888,1.0)
go

如果您参考图 1，将会看到每个 insert 语句都对应于该图形中的箭头之一。

接下来，我在 tblGraph 中的 fromNode 和 toNode 列上创建了索引，以便在最短路径存储过程访问图形数据时改进性能：

create nonclustered index idxTblGraphFromNode on tblGraph(fromNode)
go
create nonclustered index idxTblGraphToNode on tblGraph(toNode)
go
I then created and populated a table to hold a list of unique node IDs:
create table tblNodes
(
nodeID bigint primary key
)
go
insert into tblNodes
select distinct fromNode from tblGraph
union
select distinct toNode from tblGraph
go

对于最短路径分析不要求仅含节点 ID 的表，但是，如果您想要对最短路径存储过程的起始节点和结束节点输入参数执行错误检查，则这样做将很有用。通过将主键子句应用于 nodeID 列，我在该列上隐式创建一个聚集索引。将 SQL union 子句与两个或更多的 select-distinct 语句一起使用是从表中获取唯一值的列表的便捷方法。

算法数据表

理解和修改在本文中提供的最短路径存储过程的关键是理解名为 tblAlgorithmData 的信息表。您可以通过执行以下 T-SQL 语句来创建该表：

create table tblAlgorithmData
(
nodeID bigint not null,
dist real not null,
pred bigint not null,
inQueue bit not null
)
go
create index idxTblAlgorithmDataNodeID on tblAlgorithmData(nodeID)
create index idxTblAlgorithmDataDist on tblAlgorithmData(dist)
create index idxTblAlgorithmDataPred on tblAlgorithmData(pred)
create index idxTblAlgorithmDataInQueue on tblAlgorithmData(inQueue)
go

对于图形中的每个唯一节点，该表将具有（至多）一行，因此，对于本文中的示例，该表将具有（至多）八行。因为 nodeID 是唯一标识符，所以，我可以将其定义为主键列。 dist 列是从起始节点到具有 nodeID 的节点的当前距离。该 dist 值随着存储过程的执行而更改，但在存储过程结束时持有最终距离。如果您查看图 2，则可以在存储过程结束时看到节点 444（即结束节点）的 dist 值为 5.0 个单位。

pred 列承载节点的紧挨着的祖先节点以及从参数起始节点到结束节点的最短路径的 nodeID。例如，在图 2 中，结束节点为 444。其祖先节点为 777。 777 的祖先节点是 666。 666 的祖先节点是 333。 333 的祖先节点是 222，即起始节点。通过将这些 pred 值放置在一起将会提供从结束节点到起始节点的最短路径： 444 到 777 到 666 到 333 到 222。请注意，我使用的算法只给出了一个最短路径，甚至是在两个或更多路径具有相同最短总距离的情况下；在这个示例中，路径 444 到 777 到 666 到 555 到 222 也具有 5.0 个单位的总距离。

inQueue 列持有一个位值（在功能上类似于 C# 类型 Boolean），该值指示是否应作为最短路径的一部分重新检查关联节点。换句话说，如果 inQueue 的值为 1，则算法需要将关联节点作为该算法中当前节点的邻居节点进行检查。如果 inQueue 的值为 0，则不需要将关联节点作为邻居节点进行检查。列名 inQueue 会带来某种程度上的误导，因为该算法并没有真正地使用显式队列，因此，您可能要考虑使用 isActive 之类的名称。我使用 inQueue 这个名称的原因在于，在最短路径算法的过程编程语言实现中，常常使用显式队列，因此这个名称有一些传统。

算法

我在本文中展示的算法是 Dijkstra 的最短路径 (DSP) 算法的一种变化形式。在非 SQL 伪代码中，我使用的 DSP 算法的变化形式在图 3 中展示。

图 3 最短路径算法

set dist of startNode to 0.0
set pred of startNode to undefined
set inQueue of startNode to true
while there are any nodes with inQueue = true
  set u = node with smallest dist and inQueue = true
  if dist of u is infinity break
  if u = endNode break
  fetch all neighbors of u
  foreach neighbor v that has inQueue = true
    if v has not been seen before then
      set dist of v to infinity
      set pred of v to undefined
      set inQueue of v to true
    end if
  end foreach
  set inQueue of u = false
  foreach neighbor v of u
    if ((dist from startNode to u) + (dist from u to v) <
      curr dist to v) then
        set dist of v to (dist from startNode to u) + (dist from u to v)
        set pred of v to u
    end if
  end foreach
end while
if (u != endNode) then
  path from startNode to endNode is unreachable
else
  retrieve path using pred values
  shortest path distance = dist of endNode
end if

该 DSP 算法是计算机科学中最著名的算法之一，并且您可以在 Internet 上找到许多不厌其烦的详细说明，但使用 SQL 的完整实现非常少。尽管比较短，但 DSP 算法非常复杂，并且我能够完全理解它的唯一方式是使用纸和笔把几个示例从头到尾搞清楚。该算法是实质是在某个给定节点 u，您将知道从起始节点到 u 的当前最短距离。然后，您找到 u 的所有邻居节点。对于每个邻居节点 v，您知道从起始节点到 v 的当前距离。您可以查找从 u 到 v 的距离。如果从起始节点到 u 的距离加上从 u 到 v 的距离比从起始节点到 v 的当前距离短，您就知道找到了从起始节点到 v 的更短路径。 inQueue 变量可防止在该算法已知重新访问某一节点将找不到更短路径后重新访问该节点。

存储过程

我将该最短路径作为 T-SQL 存储过程实现。该存储过程定义以下面的代码作为开头：

    create procedure usp_ShortestPath
      @startNode bigint,
      @endNode bigint,
      @path varchar(5000) output,
      @totDist real output
    as
    begin
      ...

我在存储过程 usp_ShortestPath 名称之前加上了“usp”（用户定义的存储过程），以便将其与系统存储过程（“sp”）、扩展存储过程（“xp”）和 CLR 存储过程（“csp”）有所区别。参数 @startNode 和 @endNode 是输入参数。该存储过程具有两个结果输出参数 @path 和 @totDist。 @path 任意设置为 varchar(5000) 类型 — 根据您正在使用的节点 ID 的类型以及期望的最长路径，您可能需要增加该 5000 最大大小。

接下来，我使用起始节点的信息初始化表 tblAlgorithmData：

    truncate table tblAlgorithmData
    insert into tblAlgorithmData
    values (@startNode, 0.0, -1, 1)
    ...

truncate 语句从以前对 usp_ShortestPath 的任何调用中清除 tblAlgorithmData 的内容。回想一下，tblAlgorithmData 的列是 nodeID、dist、pred 和 inQueue。从起始节点到自身的距离是 0.0，该起始节点的祖先节点设置为 -1 以便指示未定义，并且 inQueue 位设置为 1 以便指示 true。

此节点假定 tblAlgorithmData 已在当前数据库中作为永久表创建。在某些情况下，您可能没有创建该表所需的安全权限；在这些情况下，您或者可以要求相应的数据库管理员为您创建表，或者可以在存储过程内将 tblAgorithmData 作为临时表或表变量创建。

此代码还假定 @startNode 和 @endNode 的值都是有效的。如果您具有含所有节点 ID 的一个表，则可以使用下面的行对此进行检查：

    if not exists(select nodeID from tblNodes where @startNode = nodeID)
      // Error out in some way //

接下来，我准备主要处理循环：

    declare @u bigint
    declare @d real = 0.0
    declare @done bit = 0
    while @done = 0
    begin
    ...

这里，@u 是算法中当前节点的节点 ID。变量 @d 十分方便并且持有从 @startNode 到节点 @u 的距离（存储于 tblAlgorithmData 中）。 @done 变量是虚拟循环控制变量。您可能想要在循环中放置其他显式停止条件，例如最大迭代数目、最大跃点计数或最长总路径距离。

在主处理循环中，第一步是找到 @u 的值 — 即当前节点的节点 ID。这是在 tblAlgorithmData 中具有最小 dist 列值并且还具有 inQueue = 1 的节点：

    select top 1 @u = nodeID, @d = dist from tblAlgorithmData
    where inQueue = 1
    order by dist asc
    ...

此时，该存储过程将检查两个循环退出条件：

    if @d = 2147483647.0 break
    if @u = @endNode break
    ...

如果从起始节点到 @u 的距离（存储于 @d 中）等于某个看起来有些神秘的值 2147483647.0，则意味着无法从起始节点到达结束节点。值 2147483647.0 表示无穷大。您可以使用不能实际作为距离出现的任意大值。我选择了 2147483647.0，因为 2147483647（显示时不是小数）是针对 SQL 类型 int 的最大值。其他中断条件只是查看是否已到达结束节点。由于该算法使用 breadth-first（宽度优先）方法搜索图形的方式，因此，如果到达结束节点，就找到了最短路径。

接下来，该存储过程将检查当前节点 @u 的每个邻居节点，并且如果某个邻居节点在以前尚未看到，则将该邻居节点初始化为 tblAlgorithmData：

    insert into tblAlgorithmData
    select toNode, 2147483647.0, -1, 1 from tblGraph where fromNode = @u
    and not exists (select * from tblAlgorithmData where nodeID = toNode)
    ...

如果您是很少使用 SQL 的编码员，则该 SQL 代码稍有点复杂。 insert 语句对于 not exists 语句而言是条件语句，该语句可被解释为：“如果邻居节点 ID（值 toNode）尚未处于 tblAlgorithmData（作为 nodeID）中”。对于该条件成立的每个邻居节点，insert 语句都将使用该邻居节点的 nodeID、无穷大的 dist 值（作为 2147483647.0）、未定义的祖先节点（作为 -1）以及值为 true 的 inQueue（作为 1）初始化 tblAlgorithmData。使用对数据组进行操作的 SQL 语句（而不是像对过程编程语言一样使用循环对集合进行迭代）可能难于掌握。

在这个算法中，在节点首次作为邻居节点出现时被初始化。另一个重要的方法是在该算法的一开始就初始化所有图形节点。该方法的问题是，对于大型图形，用可能数百万的节点填充 tblAlgorithmData 可能需要稍有些长的时间。

此时，该存储过程将当前节点标记为已处理：

    update tblAlgorithmData set inQueue = 0
    where nodeID = @u
    ...

接下来，该存储过程将检查当前节点的每个邻居节点，以便查看是否找到了新的、更短的到该邻居节点的路径；如果找到，则更新 tblAlgorithmData 中针对该邻居节点的条目：

    update tblAlgorithmData
      set dist = @d + tblGraph.edgeWeight, pred = @u
      from tblAlgorithmData inner join tblGraph on 
        tblAlgorithmData.
    nodeID = tblGraph.toNode
      where tblGraph.fromNode = @u and tblAlgorithmData.inQueue = 1
        and (@d + tblGraph.edgeWeight) < tblAlgorithmData.dist
    end -- loop
    ...

这是到目前为止最短路径实现中最棘手的部分。表 tblGraph 联接到 tblAlgorithmData，以便所有数据都可以在 update 语句中使用。当前节点的 ID 存储于 @u 中，并且该值与 tblGraph 中的 fromNode 匹配。 @u 的邻居节点存储于 tblGraph 的 toNode 中，它链接到 tblAlgorithmData 的 nodeID。回想一下，@d 持有从起始节点到当前节点 @u 的距离。 edgeWeight 列中的值将持有从 @u 到邻居节点的距离。这两个距离之和是从起始节点到邻居节点的当前距离的可能的更短新路径，并且存储于 dist 列中。如果找到了某个新的更短距离，则 dist 列将用这个新的更短距离进行更新，并且邻居节点的祖先节点记录为 @u，即当前节点。如果您将最短路径定义为起始节点和结束节点之间跃点的最小数目，则在此类情况下，应该使用 dist = @d + 1 替换 dist = @d + tblGraph.edgeWeight。

此时，主要处理循环已退出并且可以检查退出原因：

    if (@u != @endNode)
      begin
        set @path = 'NOT REACHABLE'
        set @totDist = -1.0
      end
      else
      begin
        set @path = ''
        declare @currNode bigint
        set @currNode = @endNode
      ...

如果 @u 中的值是结束节点的 ID，则已找到该结束节点；如果 @u 是结束节点 ID 以外的其他值，则循环在找到结束节点前已退出。在这个示例中，我将路径字符串设置为“NOT REACHABLE”，并且分配任意最短路径总距离 -1.0 以便指示无法到达。如果实际上找到了结束节点，则我将该最短路径字符串初始化为空字符串，并且设置本地变量 @currNode 以便迭代 tblAlgorithmData 来构建最短路径字符串。

最后，下面的存储过程定义代码构建最短路径字符串并分配最短路径总距离：

    ...
    while @currNode != @startNode
        begin
          set @path = @path + cast(@currNode as varchar(19)) + ';'
          set @currNode = (select pred from tblAlgorithmData 
            where nodeID = @currNode)
        end
        set @path = @path + cast(@startNode as varchar(19))
        select @totDist = dist from tblAlgorithmData 
          where nodeID = @endNode
      end -- else
    end -- usp_ShortestPath definition
    go

在上面的代码中，我使用了 T-SQL 字符串连接“+”运算符。我使用 varchar(19)，因为我的 bigint 的 nodeID 类型的可能最大值为 9,223,372,036,854,775,807，它具有 19 位。

创建了该存储过程后，我可以找到任何两个节点之间的最短路径；例如：

    declare @startNode bigint
    declare @endNode bigint
    declare @path varchar(5000)
    declare @totDist real
    set @startNode = 222
    set @endNode = 444
    exec usp_ShortestPath @startNode, @endNode, 
      @path output, @totDist output
    select @path
    select @totDist

总结

随着企业收集更多的数据，并将数据存储在云环境中，最短路径分析的重要性可能因此提升。本文中提供的代码和说明应该可以帮助您打下坚实的基础，以便开始对您的数据执行最短路径分析。针对本文中所介绍的本机 T-SQL 语言方法的一个重要替代方法是使用 CLR 存储过程。基于我的经验，使用 CLR 存储过程执行最短路径分析可帮助您提高性能，但代价是会增加复杂性。在将来的文章中，我将介绍如何使用 CLR 存储过程方法来执行基于图形的最短路径分析。

James McCaffrey博士供职于 Volt Information Sciences, Inc.，在该公司他负责管理对华盛顿州雷蒙德市沃什湾 Microsoft 总部园区的软件工程师进行的技术培训。他参与过多项 Microsoft 产品的研发工作，其中包括 Internet Explorer 和 MSN Search。 McCaffrey 是《.NET 软件测试自动化之道》（Apress，2006）的作者。可通过 jammc@microsoft.com 与他联系。

衷心感谢以下技术专家对本文的审阅： Shane Williams

测试运行

使用 SQL 基于图形的最短路径分析

设置演示数据库

算法数据表

算法

存储过程

总结

其他资源