MySQL: Dijkstra's "kürzester Pfad"

[omata]

Vielleicht benötigt ja mal einer diesen Algorithmus innerhalb einer Datenbank.

Hier ist die Variante für MSSQL zufinden.

Tabellen:

SQL-Code:

CREATE TABLE Nodes (
  NodeID INT AUTO_INCREMENT NOT NULL,
  NodeName VARCHAR(20) NOT NULL,
  Cost INT NULL,
  PathID INT NULL,
  Calculated INT NOT NULL,
  CONSTRAINT PK_Nodes
    PRIMARY KEY (NodeID)
);

/*---------------------------------------------------------------*/

CREATE TABLE Paths (
  PathID INT AUTO_INCREMENT NOT NULL,
  FromNodeID INT NOT NULL,
  ToNodeID INT NOT NULL,
  Cost INT NOT NULL,
  CONSTRAINT PK_Paths
    PRIMARY KEY (PathID),
  CONSTRAINT FK_Paths_FromNodes
    FOREIGN KEY (FromNodeID) REFERENCES Nodes (NodeID),
  CONSTRAINT FK_Paths_ToNodes
    FOREIGN KEY (ToNodeID) REFERENCES Nodes (NodeID)
);

Prozeduren:

SQL-Code:

DELIMITER $$

DROP PROCEDURE IF EXISTS `dijkstra`.`procInitializeMap` $$
CREATE PROCEDURE `dijkstra`.`procInitializeMap` ()
BEGIN
  DELETE FROM Paths;
  ALTER TABLE Paths AUTO_INCREMENT = 1;

  DELETE FROM Nodes;
  ALTER TABLE Nodes AUTO_INCREMENT = 1;
END $$

DELIMITER ;

/*---------------------------------------------------------------*/

DELIMITER $$

DROP PROCEDURE IF EXISTS `procClearMap` $$
CREATE PROCEDURE `procClearMap`()
BEGIN
  UPDATE Nodes
  SET PathID = NULL,
      Cost = NULL,
      Calculated = 0;
END $$

DELIMITER ;

/*---------------------------------------------------------------*/

DELIMITER $$

DROP PROCEDURE IF EXISTS `procAddPath` $$
CREATE PROCEDURE `procAddPath`(
  pFromNodeName VARCHAR(20), pToNodeName VARCHAR(20), pCost INT
)
BEGIN
  DECLARE pFromNodeID INT;
  DECLARE pToNodeID INT;
  DECLARE pPathID INT;

  SELECT NodeID
  INTO pFromNodeID
  FROM Nodes
  WHERE NodeName = pFromNodeName;

  IF pFromNodeID IS NULL THEN
    INSERT Nodes (NodeName, Calculated)
      VALUES (pFromNodeName, 0);
    SET pFromNodeID = LAST_INSERT_ID();
  END IF;

  SELECT NodeID
  INTO pToNodeID
  FROM Nodes
  WHERE NodeName = pToNodeName;

  IF pToNodeID IS NULL THEN
    INSERT Nodes (NodeName, Calculated)
      VALUES (pToNodeName, 0);
    SET pToNodeID = LAST_INSERT_ID();
  END IF;

  SELECT PathID
  INTO pPathID
  FROM Paths
  WHERE FromNodeID = pFromNodeID
    AND ToNodeID = pToNodeID;

  IF pPathID IS NULL THEN
    INSERT Paths (FromNodeID, ToNodeID, Cost)
      VALUES (pFromNodeID, pToNodeID, pCost);
  ELSE
    UPDATE Paths
    SET Cost = pCost
    WHERE FromNodeID = pFromNodeID
      AND ToNodeID = pToNodeID;
  END IF;
END $$

DELIMITER ;

/*---------------------------------------------------------------*/

DELIMITER $$

DROP PROCEDURE IF EXISTS `procResolve` $$
CREATE PROCEDURE `procResolve`(
  pFromNodeName VARCHAR(20), pToNodeName VARCHAR(20)
)
MAIN_BLOCK: BEGIN
  DECLARE pFromNodeID INT;
  DECLARE pToNodeID INT;
  DECLARE pNodeID INT;
  DECLARE pCost INT;
  DECLARE pPathID INT;
  DECLARE pNodeID2 INT;
  DECLARE pCost2 INT;
  DECLARE pPathID2 INT;
  DECLARE done INT;
  DECLARE pRowID INT;

  DECLARE cur1 CURSOR FOR
    SELECT ToNodes.NodeID,
           CASE
             WHEN ToNodes.Cost IS NULL
               THEN FromNodes.Cost + Paths.Cost
             WHEN FromNodes.Cost + Paths.Cost < ToNodes.Cost
               THEN FromNodes.Cost + Paths.Cost
             ELSE ToNodes.Cost
           END Cost, Paths.PathID
    FROM Nodes AS FromNodes
    INNER JOIN Paths
      ON Paths.FromNodeID = FromNodes.NodeID
    INNER JOIN Nodes AS ToNodes
      ON ToNodes.NodeID = Paths.ToNodeID
    WHERE FromNodes.NodeID = pNodeID
      AND (   ToNodes.Cost IS NULL
           OR FromNodes.Cost + Paths.Cost < ToNodes.Cost)
      AND ToNodes.Calculated = 0;
  DECLARE CONTINUE HANDLER FOR SQLSTATE '02000' SET done = 1;

  CALL procClearMap;

  SELECT NodeID, NodeID
  INTO pFromNodeID, pNodeID
  FROM Nodes
  WHERE NodeName = pFromNodeName;

  IF pFromNodeID IS NULL THEN
    SELECT CONCAT('From node name "',
                  COALESCE(pFromNodeName, '?'),
                  '" can not be found.') AS info;
    LEAVE MAIN_BLOCK;
  END IF;

  SELECT NodeID
  INTO pToNodeID
  FROM Nodes
  WHERE NodeName = pToNodeName;

  IF pToNodeID IS NULL THEN
    SELECT CONCAT('To node name "',
                  COALESCE(pToNodeName, '?'),
                  '" can not be found.') AS info;
    LEAVE MAIN_BLOCK;
  END IF;

  UPDATE Nodes
  SET Cost = 0
  WHERE NodeID = pFromNodeID;

  WHILE pNodeID IS NOT NULL DO
    SET done = 0;
    OPEN cur1;
    REPEAT
      FETCH cur1 INTO pNodeID2, pCost2, pPathID2;
      UPDATE Nodes
      SET Cost = pCost2,
          PathID = pPathID2
      WHERE NodeID = pNodeID2;
    UNTIL done END REPEAT;
    CLOSE cur1;

    UPDATE Nodes
    SET Calculated = 1
    WHERE NodeID = pNodeID;

    SET pNodeID = NULL;

    SELECT NodeID
    INTO pNodeID
    FROM Nodes
    WHERE Calculated = 0
      AND Cost IS NOT NULL
    ORDER BY Cost LIMIT 1;
  END WHILE;

  CREATE TEMPORARY TABLE Map (
    RowID INT,
    FromNodeName VARCHAR(20),
    ToNodeName VARCHAR(20),
    Cost INT
  );

  IF EXISTS (SELECT *
             FROM Nodes
             WHERE NodeID = pToNodeID
               AND Cost IS NULL)
  THEN
    SELECT FromNodeName, ToNodeName, Cost
    FROM Map;
    DROP TEMPORARY TABLE Map;
    LEAVE MAIN_BLOCK;
  END IF;

  WHILE pFromNodeID <> pToNodeID DO
    SELECT FromNodes.NodeName,
           ToNodes.NodeName,
           ToNodes.Cost,
           ToNodes.PathID
    INTO pFromNodeName, pToNodeName, pCost, pPathID
    FROM Nodes AS ToNodes
    INNER JOIN Paths
      ON Paths.PathID = ToNodes.PathID
    INNER JOIN Nodes AS FromNodes
      ON FromNodes.NodeID = Paths.FromNodeID
    WHERE ToNodes.NodeID = pToNodeID;

    SET pRowID = COALESCE((SELECT MIN(RowID)-1 FROM Map), -1);
    INSERT Map (RowID, FromNodeName, ToNodeName, Cost)
      VALUES (pRowID, pFromNodeName, pToNodeName, pCost);

    SELECT FromNodeID
    INTO pToNodeID
    FROM Paths
    WHERE PathID = pPathID;
  END WHILE;

  SELECT FromNodeName, ToNodeName, Cost
  FROM Map
  ORDER BY RowID;

  DROP TEMPORARY TABLE Map;
END MAIN_BLOCK $$

DELIMITER ;

Aufruf:

SQL-Code:

CALL procInitializeMap;

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

CALL procResolve('a', 'i');