本文章是由機器翻譯。

測試回合

透過 SQL 以圖表為主的最短路徑分析

James McCaffrey

下載代碼示例

在本專欄中，我解釋如何實現基於圖的最短-­路徑分析在那裡你有圖形資料存儲在 SQL 資料庫中，並且想要使用本機 T-SQL 語言處理的情況下。傳統的最短路徑方法假定在電腦記憶體中的資料結構中存儲的圖形表示形式。但大的圖表，如那些代表社交網路，往往不適合到記憶體中，所以儲存和處理它們使用 SQL 是一種選擇。瞭解我的最佳方法是看中的示例圖圖 1，並在中運行的螢幕擷取畫面演示的 圖 2。

圖 1 演示圖的最短路徑分析

圖 2 最短路徑分析與 T-SQL

在關係圖中所示圖 1 是人工小，有八個節點 （有時稱為頂點） 與 Id 111 888 通過。你可以想像節點表示的人或電腦。方向箭頭 （通常稱為邊緣） 節點之間的關係。你可以想像兩個節點之間的箭頭表示電子郵件往來。在此示例中的圖形邊緣了權重由 1.0 或 2.0 的值表示。邊緣權重可以有不同的含義，具體取決於您的特定問題方案。例如，重量可以表示某種程度的親和社會或消息被發送時的一個指標。

"最短路徑"一詞可以有不同的含義。假設你興趣 222 使用者和使用者 444 之間的最短路徑。這可能意味著躍去從 222 444，這將是 4 (222 至 333 到 444 777 666) 最小的數。或者，最短路徑可能意味著 222 和 444，之間的權重的總和最小是 5.0 （1.0 + 1.0 + 1.0 + 2.0）。

在左視窗中圖 2，你可以看到我正在與 SQL 伺服器管理 Studio 中稱為 dbShortPathDemo 的資料庫。右上方視窗中自己的 T-SQL 腳本命名為 ShortestPath.sql，定義並填充演示資料庫中的關係圖所對應的資訊與圖 1，並定義一個名為 usp_ShortestPath 的存儲的過程的代碼。只被調用已存儲的過程來分析使用者 222 和 444 使用者之間的最短路徑。在右下角視窗中您可以看到結果。最短路徑是鑒於由字串"444 ； 777 ； 666 ； 333 ； 222"。以重量計的最短路徑是 5.0 （顯示沒有小數點）。圖像的右下角部分演示一個名為 tblAlgorithmData，這是實施的最短路徑代碼的關鍵表的最終狀態。

在下面的章節中，我將指導您通過生成的截圖中的 T-SQL 代碼圖 2 所以，你應該能夠適應代碼以滿足您自己的問題的方案。我假設你主要 （意味著您最常使用 C# 或一些其他程式的程式設計語言） 非 SQL 開發人員，但有一些基本的 SQL 知識。我目前在這篇文章 ； 解釋所有 T-SQL 代碼 代碼也是可用在 archive.msdn.microsoft.com/mag201212TestRun。

設置演示資料庫

若要創建演示資料庫啟動 SQL 伺服器管理工作室，並連接到我的伺服器機器。我使用 SQL Server 2008，但這裡，介紹用稍作修改，代碼應與大多數較早和所有較新版本的 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

在這裡我所有的預設參數值用於創建資料庫的語句。 將在許多方案中使用現有的資料庫與真實的資料，但我建議嘗試的小 demo 資料庫。 我寧願在最大程度上，使用小寫的 T-SQL 代碼，可能會冒犯 SQL 純粹主義者。 我用滑鼠來選擇這些九行代碼，然後按 F5 鍵以執行它們。 驗證演示資料庫的創建之後, 保存為 ShortestPath.sql 腳本。

接下來，創建一個表內演示資料庫來保存資料，用於定義要進行分析的關係圖：

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

我用滑鼠來突出顯示的代碼只是這些七行 （因此，我不會重新執行以前的行），按 f5 來創建表。 對節點 Id 使用 Bigint 類型。 您可能會遇到其他常見節點 ID 類型包括 int 一個相對簡單的雇員 ID 和 xxx-xx-xxxx 格式中的社會安全號碼為 Varchar(11)。 我對於使用類型實際列 edgeWeight。 T-SQL 類型實際是只是一個方便別名為 float(24)，這是類似于 C# 類型雙。 在許多情況下您可能沒有顯式邊緣重量之間的節點，和 edgeWeight 列，則可以省略。

下一步，我填充表 tblGraph 的輸入、 突出顯示和執行這些 15 行代碼：

    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，您將看到每個插入語句對應圖中箭頭之一。

下一步，我在 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 的表不是最短路徑分析，所必需的但它是有用的如果您想要執行錯誤檢查對啟動節點和結束節點的最短路徑的預存程序的輸入的參數。 通過對節點列適用主要關鍵條款，我在該列上隱式創建聚集的索引。 聯盟的 SQL 語句，用兩個或更多的選擇不同語句，是一種簡便方法從表中獲取一個唯一值的清單。

該演算法資料表格

理解和修改的最短路徑的存儲的過程，在這篇文章中提出的關鍵理解名為 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

表將有一行 （最多） 為每個唯一的節點，在圖中，因此，對於本文中的示例，表將有八行 （最多）。 節點是一個唯一的識別碼，因為我可能已定義它作為主鍵列。 Dist 列是從起始節點到了節點的節點的當前距離。 此 dist 值改變存儲的過程執行，但該存儲的過程完成時保存最後的距離。 如果你看看圖 2，你可以看到該存儲的過程完成時，節點 444，結束節點中，dist 值是 5.0 單位。

人口研究列所包含的前任與節點的最短路徑的節點從參數開始到結束節點的節點。 例如，在圖 2，結束節點是 444。 其前身是 777。 777 的前身是 666。 666 的前身是 333。 333 的前身是 222，啟動節點。 這些人口研究值放在一起給從結束節點啟動節點的最短路徑：444 到 777 到 222 333 666。 請注意我使用的演算法使只是一個最短路徑，即使在有兩個或更多具有相同的最短路徑的總距離 ； 的情況 在此示例中，路徑 444 到 777 到 222 555 666 也有 5.0 單位的總距離。

InQueue 列所包含位的值 （功能上類似于 C# 類型的布林值），該值指示是否應作為一部分的最短路徑的相關的節點進行重新檢查。 把另一種方式，如果 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 演算法是電腦科學中的最著名的演算法之一，您可以找到許多痛苦地詳細的解釋在互聯網上，但很少的完整實現，使用 SQL。 雖然很短，DSP 愛國者­定位中是非常棘手的和得以充分瞭解它的唯一途徑是通過幾個實例使用紙和筆的跟蹤。 演算法的實質是，在一個給定的節點 u，就會從起始節點到 u 知道當前最短的距離。 然後你發現所有鄰居的 u。 對於每個鄰居節點，v，你到 v 從啟動節點知道當前的距離。 您可以查找距離從 u 到 v。 如果從開始到 u 之間的距離，加上從 u 到 v 的距離比從開始到 v 的當前距離更短，你知道你已經找到一個較短的路徑，從開始的第五。 InQueue 變數可以防止重新訪問節點，一旦知道重新訪問該節點不會尋找較短的路徑演算法。

存儲的過程

我作為一個 T-SQL 預存程序實現的最短路徑。 存儲的程序定義開始：

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

我從系統預存程序 （"sp"），擴展存儲的過程 ("xp") 和 CLR 預存程序 （"csp"） 預置存儲的過程 usp_ShortestPath 名稱與"usp"（使用者定義的預存程序） 將其區分開來。 輸入的參數參數 @startNode 和 @endNode。 存儲的過程有兩個結果輸出參數、 @path 和 @totDist。 @Path 任意設置鍵入 Varchar (5000) — — 您可能需要增加 5000 最大值取決於您正在使用的節點 ID 和您期望的路徑的最大的類型。

下一步，初始化表 tblAlgorithmData 啟動節點的資訊：

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

Truncate 語句會擦除 tblAlgorithmData 從 usp_ShortestPath 中調用任何以前的內容。 記得 tblAlgorithmData 的列的節點、 dist、 人口研究和 inQueue。 從起始節點到本身的距離為 0.0，前身為啟動節點設置為-1 以指示未定義的和 inQueue 位設置為 1，以指示 true。

此代碼假定該 tblAlgorithmData 已經永久表的當前資料庫中創建。 在某些情況下您可能沒有創建表 ； 所需的安全許可權 在這些情況下，您可以要求相應的資料庫管理員這樣做，您或您可以創建在預存程序內的 tblAgorithmData 作為 temp 表或表變數。

此代碼還假定的 @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 中） 的距離。 @ 做的變數是虛擬迴圈控制變數。 可能要等最大反覆運算次數、 最大躍點計數或最大總路徑距離迴圈中放其他顯式停止條件。

主要加工迴圈內的第一步是要查找的值的 @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 的最大值 其他中斷條件只需檢查是否達到結束節點。 方式演算法搜索使用廣度優先的辦法，如果被命中的結束節點，該圖的最短路徑已找到。

接下來，該存儲的過程會檢查每個鄰居的當前節點 @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 語句的條件是不存在的語句，這可以解釋為，"如果鄰居節點 ID （價值 toNode） 已不在 tblAlgorithmData (作為節點）。"條件在哪裡為 true，insert 語句初始化與鄰居的節點，dist 值為無窮大 （2147483647.0），作為 tblAlgorithmData 的每個鄰居節點的前置未定義 （如-1），並為 true (1) 作為 inQueue。 在集上的資料，進行操作的 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 向鄰居都存儲在 toNode tblGraph，這連結到 tblAlgorithmData 的節點中。 還記得那個 @d 持有從起始節點到當前節點 @u 的距離。 EdgeWeight 列中的值將舉行從 @u 到鄰居的距離。 這些兩個距離的總和是從啟動節點的鄰居，縣的列中存儲的當前距離可能新短路徑 如果已找到新更短的距離，用這新的更短的距離 dist 列進行更新和鄰居節點的前身記錄為 @u，當前節點。 在您在其中定義最短路徑指的起始節點和結束節點之間的躍點數最少的情況下，您將取代 dist = @d + 與 dist tblGraph.edgeWeight = @d + 1。

此時的主要加工迴圈已退出和退出的原因可以進行檢查：

    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，結束節點已發現 ； 結束節點的 ID 不是 @u，如果找到結束節點之前將退出迴圈。 在這種情況下將設置到 '不可以到達' 的路徑字串，並指派任意-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 我節點類型可能的最大值 9223372036854775807，其中有 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 預存程序方法。

Dr. James McCaffrey 為伏資訊科學 Inc.，他在管理工作在微軟雷德蒙德，華盛頓州，校園的軟體工程師的技術培訓工作。他曾經參與過多項 Microsoft 產品的研發，包括 Internet Explorer 和 MSN Search。麥卡弗裡是作者的".NET 測試自動化食譜"（Apress，2006年）。他可以在達成 jammc@microsoft.com。

由於以下的技術專家對本文的審閱：沙恩 · 威廉斯