SQL Server 實現最短路徑搜尋：雙向 BFS + 遞迴 CTE 構建路徑

問題定義

表 RelationGraph(ID, Node, RelatedNode) 存儲節點連接關係。給定起點 p、終點 j，尋找經過節點最少的路徑。

演算法：雙向 BFS（雙源擴展）

以起點與終點同時向外分層擴展，直到兩側邊界相交（切點），保證找到最短路徑，搜尋空間指數級縮減。

建表與測試資料

CREATE TABLE RelationGraph(
    ID INT IDENTITY,
    Node NVARCHAR(50),
    RelatedNode NVARCHAR(20),
    CONSTRAINT PK_RelationGraph PRIMARY KEY(ID)
);
CREATE NONCLUSTERED INDEX IX_Node ON RelationGraph(Node) INCLUDE(RelatedNode);
CREATE NONCLUSTERED INDEX IX_RelatedNode ON RelationGraph(RelatedNode) INCLUDE(Node);

INSERT INTO RelationGraph(Node, RelatedNode) 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');

預存程序實作

CREATE PROC up_GetPath
    @Node NVARCHAR(50),
    @RelatedNode NVARCHAR(50)
AS
SET NOCOUNT ON;

DECLARE 
    @level SMALLINT = 1,
    @MaxLevel SMALLINT = 100,
    @Node_Flag BIT = 1,
    @RelatedNode_Flag BIT = 1;

-- 直接相連或同節點
IF EXISTS(SELECT 1 FROM RelationGraph 
    WHERE (Node=@Node AND RelatedNode=@RelatedNode) 
       OR (Node=@RelatedNode AND RelatedNode=@Node))
   OR @Node = @RelatedNode
BEGIN
    SELECT CONVERT(NVARCHAR(2000), @Node + ' --> ' + @RelatedNode) AS Path, 0 AS Steps;
    RETURN;
END

-- 暫存表：雙向擴展軌跡
IF OBJECT_ID('tempdb..#1') IS NOT NULL DROP TABLE #1;
IF OBJECT_ID('tempdb..#2') IS NOT NULL DROP TABLE #2;
CREATE TABLE #1(Node NVARCHAR(50), RelatedNode NVARCHAR(50), Level SMALLINT);
CREATE TABLE #2(Node NVARCHAR(50), RelatedNode NVARCHAR(50), Level SMALLINT);

-- 第 1 層：正向 + 反向
INSERT INTO #1 SELECT Node, RelatedNode, @level FROM RelationGraph WHERE Node = @Node
UNION SELECT RelatedNode, Node, @level FROM RelationGraph WHERE RelatedNode = @Node;
SET @Node_Flag = SIGN(@@ROWCOUNT);

INSERT INTO #2 SELECT Node, RelatedNode, @level FROM RelationGraph WHERE Node = @RelatedNode
UNION SELECT RelatedNode, Node, @level FROM RelationGraph WHERE RelatedNode = @RelatedNode;
SET @RelatedNode_Flag = SIGN(@@ROWCOUNT);

IF NOT EXISTS(SELECT 1 FROM #1) OR NOT EXISTS(SELECT 1 FROM #2) GOTO While_Out;

-- 迴圈擴展直到相交或達上限
WHILE NOT EXISTS(SELECT 1 FROM #1 a INNER JOIN #2 b ON b.RelatedNode = a.RelatedNode)
      AND (@Node_Flag | @RelatedNode_Flag) > 0
      AND @level < @MaxLevel
BEGIN
    IF @Node_Flag > 0
    BEGIN
        INSERT INTO #1
        SELECT a.Node, a.RelatedNode, @level+1
        FROM RelationGraph a
        WHERE EXISTS(SELECT 1 FROM #1 WHERE RelatedNode = a.Node AND Level = @level)
          AND NOT EXISTS(SELECT 1 FROM #1 WHERE Node = a.Node)
        UNION
        SELECT a.RelatedNode, a.Node, @level+1
        FROM RelationGraph a
        WHERE EXISTS(SELECT 1 FROM #1 WHERE RelatedNode = a.RelatedNode AND Level = @level)
          AND NOT EXISTS(SELECT 1 FROM #1 WHERE Node = a.RelatedNode);
        SET @Node_Flag = SIGN(@@ROWCOUNT);
    END

    IF @RelatedNode_Flag > 0
    BEGIN
        INSERT INTO #2
        SELECT a.Node, a.RelatedNode, @level+1
        FROM RelationGraph a
        WHERE EXISTS(SELECT 1 FROM #2 WHERE RelatedNode = a.Node AND Level = @level)
          AND NOT EXISTS(SELECT 1 FROM #2 WHERE Node = a.Node)
        UNION
        SELECT a.RelatedNode, a.Node, @level+1
        FROM RelationGraph a
        WHERE EXISTS(SELECT 1 FROM #2 WHERE RelatedNode = a.RelatedNode AND Level = @level)
          AND NOT EXISTS(SELECT 1 FROM #2 WHERE Node = a.RelatedNode);
        SET @RelatedNode_Flag = SIGN(@@ROWCOUNT);
    END

    SET @level += 1;
END

While_Out:

-- 遞迴 CTE 回溯構建路徑
IF OBJECT_ID('tempdb..#Path1') IS NOT NULL DROP TABLE #Path1;
IF OBJECT_ID('tempdb..#Path2') IS NOT NULL DROP TABLE #Path2;

;WITH cte1 AS (
    SELECT a.Node, a.RelatedNode, a.Level,
           CONVERT(NVARCHAR(2000), a.Node + ' -> ' + a.RelatedNode) AS PathStr,
           1 AS PathLevel
    FROM #1 a WHERE EXISTS(SELECT 1 FROM #2 WHERE RelatedNode = a.RelatedNode)
    UNION ALL
    SELECT b.Node, a.RelatedNode, b.Level,
           CONVERT(NVARCHAR(2000), b.Node + ' -> ' + a.PathStr),
           a.PathLevel + 1
    FROM cte1 a INNER JOIN #1 b ON b.RelatedNode = a.Node AND b.Level = a.Level - 1
)
SELECT * INTO #Path1 FROM cte1;

;WITH cte2 AS (
    SELECT a.Node, a.RelatedNode, a.Level,
           CONVERT(NVARCHAR(2000), a.Node) AS PathStr,
           1 AS PathLevel
    FROM #2 a WHERE EXISTS(SELECT 1 FROM #1 WHERE RelatedNode = a.RelatedNode)
    UNION ALL
    SELECT b.Node, a.RelatedNode, b.Level,
           CONVERT(NVARCHAR(2000), a.PathStr + ' -> ' + b.Node),
           a.PathLevel + 1
    FROM cte2 a INNER JOIN #2 b ON b.RelatedNode = a.Node AND b.Level = a.Level - 1
)
SELECT * INTO #Path2 FROM cte2;

;WITH cte_res AS (
    SELECT a.PathStr + ' -> ' + b.PathStr AS FullPath,
           a.PathLevel + b.PathLevel - 1 AS Steps,
           RANK() OVER(ORDER BY a.PathLevel + b.PathLevel) AS rn
    FROM #Path1 a INNER JOIN #Path2 b ON b.RelatedNode = a.RelatedNode AND b.Level = 1
    WHERE a.Level = 1
)
SELECT DISTINCT FullPath, Steps FROM cte_res WHERE rn = 1;
GO

執行與結果

EXEC up_GetPath @Node = 'p', @RelatedNode = 'j';

擴展應用

• 大眾運輸轉乘最少站點
• 社交網路六度人脈鏈
• 知識圖譜實體關聯路徑

效能提示

• 索引覆蓋 (Node, RelatedNode) 與 (RelatedNode, Node) 關鍵
• @MaxLevel 防止異常資料導致無限循環
• 大圖建議改用圖資料庫（Neo4j）或 SQL Graph (SQL 2017+)