如何在T-SQL中实现Dijkstra算法查询仓库货位最短路径？

我有一张存储仓库n个货位及地图坐标的表，需要完成三个需求：

• 计算任意两点间的距离
• 在T-SQL中实现Dijkstra算法找到货位间的最短路径
• 将最短路径插入新临时表

之前尝试过pivot、cross apply、cross join等方法，都没得到预期结果，还经常报错。

样本数据 #

期望输出 #

（距离为占位符，非实际值，BinPath也可拆分为From和To列）

尝试过的无效代码 #

SELECT
    D1.[BinCoord],
    D1.[BinNum]
FROM
    ##Djik3 D1
    CROSS JOIN ##Djik3 D2
WHERE
    D1.BinCoord = D2.BinCoord
    AND
    D1.BinNum = D2.BinNum

我猜测可能需要循环或结合动态SQL的pivot实现，但目前没有清晰思路。

第一步：拆分坐标并计算任意两点间距离 #

首先需要把BinCoord中的X、Y坐标拆分出来，再用欧几里得距离公式计算两点间距离：

-- 创建临时表存储拆分后的坐标
DROP TABLE IF EXISTS #BinCoordinates;
CREATE TABLE #BinCoordinates (
    BinNumb VARCHAR(10),
    X INT,
    Y INT
);

-- 拆分坐标（适配(X,Y)格式）
INSERT INTO #BinCoordinates (BinNumb, X, Y)
SELECT
    BinNumb,
    CAST(SUBSTRING(BinCoord, 2, CHARINDEX(',', BinCoord) - 2) AS INT) AS X,
    CAST(SUBSTRING(BinCoord, CHARINDEX(',', BinCoord) + 1, LEN(BinCoord) - CHARINDEX(',', BinCoord) - 1) AS INT) AS Y
FROM ##Djik3;

-- 计算所有非重复两点间的距离
DROP TABLE IF EXISTS #BinDistances;
CREATE TABLE #BinDistances (
    FromBin VARCHAR(10),
    ToBin VARCHAR(10),
    Distance FLOAT
);

INSERT INTO #BinDistances (FromBin, ToBin, Distance)
SELECT
    bc1.BinNumb AS FromBin,
    bc2.BinNumb AS ToBin,
    SQRT(POWER(bc2.X - bc1.X, 2) + POWER(bc2.Y - bc1.Y, 2)) AS Distance
FROM #BinCoordinates bc1
CROSS JOIN #BinCoordinates bc2
WHERE bc1.BinNumb <> bc2.BinNumb; -- 排除自身到自身的无效路径

第二步：T-SQL实现Dijkstra算法 #

以下是遍历所有货位作为起点，计算到其他所有货位最短路径的实现：

-- 创建存储最终最短路径的临时表
DROP TABLE IF EXISTS #ShortestPaths;
CREATE TABLE #ShortestPaths (
    StartBin VARCHAR(10),
    EndBin VARCHAR(10),
    TotalDistance FLOAT,
    Path VARCHAR(MAX)
);

-- 遍历每个货位作为起点
DECLARE @StartBin VARCHAR(10);
DECLARE bin_cursor CURSOR FOR
SELECT BinNumb FROM #BinCoordinates;

OPEN bin_cursor;
FETCH NEXT FROM bin_cursor INTO @StartBin;

WHILE @@FETCH_STATUS = 0
BEGIN
    -- Dijkstra算法核心临时表
    DROP TABLE IF EXISTS #DijkstraTemp;
    CREATE TABLE #DijkstraTemp (
        BinNumb VARCHAR(10),
        TotalDistance FLOAT,
        Path VARCHAR(MAX),
        Visited BIT DEFAULT 0
    );

    -- 初始化起点数据
    INSERT INTO #DijkstraTemp (BinNumb, TotalDistance, Path)
    VALUES (@StartBin, 0, @StartBin);

    -- 初始化其他节点（用极大值标记初始不可达）
    INSERT INTO #DijkstraTemp (BinNumb, TotalDistance, Path)
    SELECT
        BinNumb,
        CAST(999999 AS FLOAT),
        ''
    FROM #BinCoordinates
    WHERE BinNumb <> @StartBin;

    DECLARE @CurrentBin VARCHAR(10);
    DECLARE @CurrentDistance FLOAT;
    DECLARE @CurrentPath VARCHAR(MAX);

    -- 循环处理所有未访问节点
    WHILE EXISTS (SELECT 1 FROM #DijkstraTemp WHERE Visited = 0)
    BEGIN
        -- 选取未访问节点中距离最小的节点
        SELECT TOP 1
            @CurrentBin = BinNumb,
            @CurrentDistance = TotalDistance,
            @CurrentPath = Path
        FROM #DijkstraTemp
        WHERE Visited = 0
        ORDER BY TotalDistance ASC;

        -- 标记当前节点为已访问
        UPDATE #DijkstraTemp SET Visited = 1 WHERE BinNumb = @CurrentBin;

        -- 更新相邻节点的最短距离和路径
        UPDATE dt
        SET
            TotalDistance = @CurrentDistance + bd.Distance,
            Path = @CurrentPath + '-' + dt.BinNumb
        FROM #DijkstraTemp dt
        JOIN #BinDistances bd ON bd.FromBin = @CurrentBin AND bd.ToBin = dt.BinNumb
        WHERE dt.Visited = 0 AND (@CurrentDistance + bd.Distance) < dt.TotalDistance;
    END

    -- 将当前起点的所有有效路径插入最终表
    INSERT INTO #ShortestPaths (StartBin, EndBin, TotalDistance, Path)
    SELECT
        @StartBin,
        BinNumb,
        TotalDistance,
        Path
    FROM #DijkstraTemp
    WHERE BinNumb <> @StartBin;

    FETCH NEXT FROM bin_cursor INTO @StartBin;
END

CLOSE bin_cursor;
DEALLOCATE bin_cursor;

第三步：输出适配期望格式 #

如果需要和期望输出格式一致，执行以下查询：

-- 合并路径格式
SELECT
    ROUND(TotalDistance, 2) AS Distance,
    Path AS BinPath
FROM #ShortestPaths;

-- 拆分From/To列的格式
SELECT
    StartBin AS FromBin,
    EndBin AS ToBin,
    ROUND(TotalDistance, 2) AS Distance,
    Path AS BinPath
FROM #ShortestPaths;

内容的提问来源于stack exchange，提问作者ayecob