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');

[Memnarch]

Mh, Kurze unwissende Frage meinerseits: Warum sollte ich einen Dijkstra über MySQL laufen lassen. Das wird mir nicht ganz schlüssig. Nicht dass ich deine Arbeit in Frage stellen möchte.

Vielleicht hab ich auch das anwendungsgebiet nicht ganz verstanden. Ich nutze Dijkstra/AStar für Pathfinding in Räumlichen gebieten für meine Spielfiguren(z.b für mein TowerDefense). Gibts da noch was anderes? Den in meinem Kopf wäre Dijkstra über MySQL server anfragen doch erheblich langsamer als native oder nicht?


MFG
Memnarch

[patti]

Ich könnte mir das z.B. in "sozialen Netzwerken" vorstellen: Es gibt User und zwischen diesen Usern gibt es "Freundschaften". Nun kann man mittels Dijkstra z.B. den kürzesten "Freundschafts-Weg" zwischen zwei unbefreundeten Usern herausfinden. Gut, dafür bräuchte man jetzt nicht unbedingt gewichtete Kanten, aber eine Möglichkeit wärs

[Memnarch]

Gut okay, wenn auch etwas abstract^^.

EDIT: gut okay, wens natürlich NodeBasierend ist(jeder freund ne Node), dan hat man ja nen Graphen, da klappts wunderbar.

MFG
Memnarch

[omata]

Die Idee war eigentlich eine andere...

Wenn ich ein sehr großes Netz in einer Datenbank gespeichert habe und dann eine Berechnung auf den Daten ausführen möchte, dann müsste ich erst alle Daten in eine eigene Datenstruktur aus der DB laden, oder ich mache während der Algoirithmus läuft viele einzelene SQL-Abfragen. Das heißt, der Datenverkehr zwischen Client-Anwendung und Datenbank ist sehr hoch. Deshalb diese Idee, dort bleiben die Daten in der DB und es findet auch kein großer Datenverkehr statt.

Vielleicht ist mein Aufruf-Beispiel auch unverständlich:
-> Ist das Netz erstellt, ist nur die Resolve-Zeile nötig.

Naja, vielleicht ist das auch alles bödsinn.
Vergesst einfach diesen Beitrag, sorry fürs posten und Speicher verbrauchen.

[patti]

Zitat von omata:

Naja, vielleicht ist das auch alles bödsinn.
Vergesst einfach diesen Beitrag, sorry fürs posten und Speicher verbrauchen.

Ganz im Gegenteil! Ich finde die Umsetzung sehr interessant und wer weiß - vielleicht kann man sowas ja mal brauchen

[FredlFesl]

Das ist der 'Single-Pair-Shortest-Path' Algorithmus, richtig?
Lustig wäre auch der 'All-Pair-Shortest-Path' Algorithmus, der nur unwesentlich komplexer ist, wenn ich mich recht erinnere...

Ist trotzdem schon lustic, was man mit SQL (=Mengenlehre) so alles anstellen kann.

[Memnarch]

@Omata: Ich wollte deine Arbeit in keinster Weise schmälern. Brauchte nur nen Denkanstoss

@FredlFesel: Was ist all-pair-shortest-path? Die beiden begriffe single und all pair waren mir noch nicht begegnet o.O


MFG
Memnarch

[s.h.a.r.k]

Zitat von patti:

Zitat von omata:

Naja, vielleicht ist das auch alles bödsinn.
Vergesst einfach diesen Beitrag, sorry fürs posten und Speicher verbrauchen.

Ganz im Gegenteil! Ich finde die Umsetzung sehr interessant und wer weiß - vielleicht kann man sowas ja mal brauchen

Also mir ist in dem Zusammenhang gleich das Thema Mobile Devices eingefallen. Selbst in SmartPhones stecken keine Hochleistungsrechner und von dem her finde ich den Ansatz echt klasse, da so halt der Server rechnen muss und nicht der Client. Kommt natürlich immer auf das Einsatzgebiet an, aber sowas kann sich durchaus lohnen.

[rollstuhlfahrer]

Wenn ich im PhpMyAdmin das ausführe (SQL Block 1, SQL Block 2 und dann SQL Block 3 hintereinander), dann bekomme ich im letzten Block einen Fehler:

Zitat von MySQL Fehler:

#2014 - Commands out of sync; you can't run this command now
CALL procResolve('a', 'i')

Wenn ich dann die letzte Anweisung (bei der er meckert) nochmal ausführe, dann klappts. Liegt das jetzt an mir oder am Server?

Bernhard