迪杰斯特拉 Dijkstra 最短路径算法 mysql实现

mjc123456 的个人博客 / 1 / 0 / 创建于 3年前 / 更新于 3年前

Dijkstra 算法mysql实现

最开始我很没有头绪，当真正要实现这种对我而言比较难的需求的时候，我就头大了，需求是这样的，根据权值，计算最短路径，根据有关联的方向，找出x点到x点的最短路径组合，问题大概如下图

为什么是mysql

让我最没有头绪的就是这个数据该怎么存，搜了好多答案，基本都没涉及到存储的问题，讲真的，我除了mysql以外，对别的数据库不太熟悉，考虑到存储，拓展，查询的问题，还是mysql更符合我这个学历不高的人，于是就找mysql的解决方法，还真找到了。

解决问题

给定一个源到目标路径表，其中每个节点引用节点表中的一行，我们如何找到从一个节点到另一个节点的最短路径，这个算法纯代码实现的例子有很多，但涉及到存储的很少，我暂时只找到了mysql，相信大家有需要的也是业务需求，最主要的是存储，读取，查询，然后才是语言实现，下面只说代码，没测试过性能，大家可以参考。

DROP TABLE IF EXISTS dijnodes,dijpaths;
CREATE TABLE dijnodes (
  nodeID int PRIMARY KEY AUTO_INCREMENT NOT NULL,
  nodename varchar (20) NOT NULL,
  cost int NULL,
  pathID int NULL,
  calculated tinyint NOT NULL 
);

CREATE TABLE dijpaths (
  pathID int PRIMARY KEY AUTO_INCREMENT,
  fromNodeID int NOT NULL ,
  toNodeID int NOT NULL ,
  cost int NOT NULL
);

以下是用于填充有效节点和路径的存储过程：

DROP PROCEDURE IF EXISTS dijAddPath;
DELIMITER |
CREATE PROCEDURE dijAddPath( 
  pFromNodeName VARCHAR(20), pToNodeName VARCHAR(20), pCost INT 
)
BEGIN
  DECLARE vFromNodeID, vToNodeID, vPathID INT;
  SET vFromNodeID = ( SELECT NodeID FROM dijnodes WHERE NodeName = pFromNodeName );
  IF vFromNodeID IS NULL THEN
    BEGIN
      INSERT INTO dijnodes (NodeName,Calculated) VALUES (pFromNodeName,0);
      SET vFromNodeID = LAST_INSERT_ID();
    END;
  END IF;
  SET vToNodeID = ( SELECT NodeID FROM dijnodes WHERE NodeName = pToNodeName );
  IF vToNodeID IS NULL THEN
    BEGIN
      INSERT INTO dijnodes(NodeName, Calculated) 
      VALUES(pToNodeName,0);
      SET vToNodeID = LAST_INSERT_ID();
    END;
  END IF;
  SET vPathID = ( SELECT PathID FROM dijpaths 
                  WHERE FromNodeID = vFromNodeID AND ToNodeID = vToNodeID 
                );
  IF vPathID IS NULL THEN
    INSERT INTO dijpaths(FromNodeID,ToNodeID,Cost) 
    VALUES(vFromNodeID,vToNodeID,pCost);
  ELSE
    UPDATE dijpaths SET Cost = pCost  
    WHERE FromNodeID = vFromNodeID AND ToNodeID = vToNodeID;
  END IF;
END; 
|
DELIMITER ;

使用dijAddpath（）填充表：

call dijaddpath( 'a', 'b',  4 );
call dijaddpath( 'a', 'd',  1 );
call dijaddpath( 'b', 'a', 74 );
call dijaddpath( 'b', 'c',  2 );
call dijaddpath( 'b', 'e', 12 );
call dijaddpath( 'c', 'b', 12 );
call dijaddpath( 'c', 'f', 74 );
call dijaddpath( 'c', 'j', 12 );
call dijaddpath( 'd', 'e', 32 );
call dijaddpath( 'd', 'g', 22 );
call dijaddpath( 'e', 'd', 66 );
call dijaddpath( 'e', 'f', 76 );
call dijaddpath( 'e', 'h', 33 );
call dijaddpath( 'f', 'i', 11 );
call dijaddpath( 'f', 'j', 21 );
call dijaddpath( 'g', 'd', 12 );
call dijaddpath( 'g', 'h', 10 );
call dijaddpath( 'h', 'g',  2 );
call dijaddpath( 'h', 'i', 72 );
call dijaddpath( 'i', 'f', 31 );
call dijaddpath( 'i', 'j',  7 );
call dijaddpath( 'i', 'h', 18 );
call dijaddpath( 'j', 'f',  8 );

SELECT * FROM dijnodes;
+--------+----------+------+--------+------------+
| nodeID | nodename | cost | pathID | calculated |
+--------+----------+------+--------+------------+
|      1 | a        | NULL |   NULL |          0 |
|      2 | b        | NULL |   NULL |          0 |
|      3 | d        | NULL |   NULL |          0 |
|      4 | c        | NULL |   NULL |          0 |
|      5 | e        | NULL |   NULL |          0 |
|      6 | f        | NULL |   NULL |          0 |
|      7 | j        | NULL |   NULL |          0 |
|      8 | g        | NULL |   NULL |          0 |
|      9 | h        | NULL |   NULL |          0 |
|     10 | i        | NULL |   NULL |          0 |
+--------+----------+------+--------+------------+
SELECT * FROM dijpaths;
+--------+------------+----------+------+
| pathID | fromNodeID | toNodeID | cost |
+--------+------------+----------+------+
|      1 |          1 |        2 |    4 |
|      2 |          1 |        3 |    1 |
|      3 |          2 |        1 |   74 |
|      4 |          2 |        4 |    2 |
|      5 |          2 |        5 |   12 |
|      6 |          4 |        2 |   12 |
|      7 |          4 |        6 |   74 |
|      8 |          4 |        7 |   12 |
|      9 |          3 |        5 |   32 |
|     10 |          3 |        8 |   22 |
|     11 |          5 |        3 |   66 |
|     12 |          5 |        6 |   76 |
|     13 |          5 |        9 |   33 |
|     14 |          6 |       10 |   11 |
|     15 |          6 |        7 |   21 |
|     16 |          8 |        3 |   12 |
|     17 |          8 |        9 |   10 |
|     18 |          9 |        8 |    2 |
|     19 |          9 |       10 |   72 |
|     20 |         10 |        6 |   31 |
|     21 |         10 |        7 |    7 |
|     22 |         10 |        9 |   18 |
|     23 |          7 |        6 |    8 |
+--------+------------+----------+------+

存储过程包括6个步骤：

“节点”表中的路径列为空
查找输入参数引用的节点ID
循环所有未计算的单步路径，计算每个路径的成本
如果节点未计算，则图形无效，因此退出
将路径序列写入临时表
查询临时表以显示结果

DROP PROCEDURE IF EXISTS dijResolve;
DELIMITER |
CREATE PROCEDURE dijResolve( pFromNodeName VARCHAR(20), pToNodeName VARCHAR(20) )
BEGIN
  DECLARE vFromNodeID, vToNodeID, vNodeID, vCost, vPathID INT;
  DECLARE vFromNodeName, vToNodeName VARCHAR(20);
  -- null out path info in the nodes table
  UPDATE dijnodes SET PathID = NULL,Cost = NULL,Calculated = 0;
  -- find nodeIDs referenced by input params
  SET vFromNodeID = ( SELECT NodeID FROM dijnodes WHERE NodeName = pFromNodeName );
  IF vFromNodeID IS NULL THEN
    SELECT CONCAT('From node name ', pFromNodeName, ' not found.' ); 
  ELSE
    BEGIN
      -- start at src node
      SET vNodeID = vFromNodeID;
      SET vToNodeID = ( SELECT NodeID FROM dijnodes WHERE NodeName = pToNodeName );
      IF vToNodeID IS NULL THEN
        SELECT CONCAT('From node name ', pToNodeName, ' not found.' );
      ELSE
        BEGIN
          -- calculate path costs till all are done
          UPDATE dijnodes SET Cost=0 WHERE NodeID = vFromNodeID;
          WHILE vNodeID IS NOT NULL DO
            BEGIN
              UPDATE 
                dijnodes AS src
                JOIN dijpaths AS paths ON paths.FromNodeID = src.NodeID
                JOIN dijnodes AS dest ON dest.NodeID = paths.toNodeID
              SET dest.Cost = CASE
                                WHEN dest.Cost IS NULL THEN src.Cost + paths.cost
                                WHEN src.Cost + paths.cost < dest.Cost THEN src.Cost + paths.cost
                                ELSE dest.Cost
                              END,
                  dest.PathID = paths.pathID
              WHERE 
                src.NodeID = vNodeID
                AND (dest.Cost IS NULL OR src.Cost + paths.cost < dest.Cost)
                AND dest.Calculated = 0;

              UPDATE dijnodes SET Calculated = 1 WHERE NodeID = vNodeID;

              SET vNodeID = ( SELECT nodeID FROM dijnodes
                              WHERE Calculated = 0 AND Cost IS NOT NULL
                              ORDER BY Cost LIMIT 1
                            );
            END;
          END WHILE;
        END;
      END IF;
    END;
  END IF;
  IF EXISTS( SELECT 1 FROM dijnodes WHERE NodeID = vToNodeID AND Cost IS NULL ) THEN
    -- problem,  cannot proceed
    SELECT CONCAT( 'Node ',vNodeID, ' missed.' );
  ELSE
    BEGIN
      -- write itinerary to Map table
      DROP TEMPORARY TABLE IF EXISTS Map;
      CREATE TEMPORARY TABLE Map (
        RowID INT PRIMARY KEY AUTO_INCREMENT,
        FromNodeName VARCHAR(20),
        ToNodeName VARCHAR(20),
        Cost INT
      ) ENGINE=MEMORY;
      WHILE vFromNodeID <> vToNodeID DO
        BEGIN
          SELECT 
            src.NodeName,dest.NodeName,dest.Cost,dest.PathID
            INTO vFromNodeName, vToNodeName, vCost, vPathID
          FROM 
            dijnodes AS dest
            JOIN dijpaths AS Paths ON Paths.pathID = dest.PathID
            JOIN dijnodes AS src ON src.NodeID = Paths.FromNodeID
          WHERE dest.NodeID = vToNodeID;

          INSERT INTO Map(FromNodeName,ToNodeName,Cost) VALUES(vFromNodeName,vToNodeName,vCost);

          SET vToNodeID = (SELECT FromNodeID FROM dijpaths WHERE pathID = vPathID);
        END;
      END WHILE;
      SELECT FromNodeName,ToNodeName,Cost FROM Map ORDER BY RowID DESC;
      DROP TEMPORARY TABLE Map;
    END;
  END IF;
END;
|
DELIMITER ;

然后执行查询

CALL dijResolve( 'a','i');
+--------------+------------+------+
| FromNodeName | ToNodeName | Cost |
+--------------+------------+------+
| a            | b          |    4 |
| b            | c          |    6 |
| c            | j          |   18 |
| j            | f          |   26 |
| f            | i          |   37 |
+--------------+------------+------+

本作品采用《CC 协议》，转载必须注明作者和本文链接

马江川@13753441707

mjc123456

59 声望

一个der货

1 人点赞

以构建论坛项目 LaraBBS 为线索，展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。

从零开始带你一步步开发一个 Go 博客项目，让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。

讨论数量: 0

(=￣ω￣=)··· 暂无内容！

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

迪杰斯特拉 Dijkstra 最短路径算法 mysql实现

Dijkstra 算法mysql实现

为什么是mysql

解决问题

以下是用于填充有效节点和路径的存储过程：

使用dijAddpath（）填充表：

然后执行查询

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

迪杰斯特拉 Dijkstra 最短路径算法 mysql实现

Dijkstra 算法mysql实现

为什么是mysql

解决问题

以下是用于填充有效节点和路径的存储过程：

使用dijAddpath（）填充表：

然后执行查询

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录