AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Datenbanken MySQL: Dijkstra's "kürzester Pfad"

MySQL: Dijkstra's "kürzester Pfad"

Ein Thema von omata · begonnen am 2. Mai 2011 · letzter Beitrag vom 7. Mai 2011
Antwort Antwort
Seite 1 von 2  1 2   
omata

Registriert seit: 26. Aug 2004
Ort: Nebel auf Amrum
3.154 Beiträge
 
Delphi 7 Enterprise
 
#1

MySQL: Dijkstra's "kürzester Pfad"

  Alt 2. Mai 2011, 01:03
Datenbank: MySQL • Version: 5 • Zugriff über: egal
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 '02000SET 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');
  Mit Zitat antworten Zitat
Benutzerbild von Memnarch
Memnarch

Registriert seit: 24. Sep 2010
736 Beiträge
 
#2

AW: MySQL: Dijkstra's "kürzester Pfad"

  Alt 2. Mai 2011, 09:46
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
  Mit Zitat antworten Zitat
Benutzerbild von patti
patti

Registriert seit: 20. Okt 2004
Ort: Mittelfranken
665 Beiträge
 
Turbo Delphi für Win32
 
#3

AW: MySQL: Dijkstra's "kürzester Pfad"

  Alt 2. Mai 2011, 12:55
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
Patrick Kreutzer
[Informatik-Student im 4. Semester]
http://www.patti-k.de/
  Mit Zitat antworten Zitat
Benutzerbild von Memnarch
Memnarch

Registriert seit: 24. Sep 2010
736 Beiträge
 
#4

AW: MySQL: Dijkstra's "kürzester Pfad"

  Alt 2. Mai 2011, 13:01
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

Geändert von Memnarch ( 2. Mai 2011 um 13:05 Uhr)
  Mit Zitat antworten Zitat
omata

Registriert seit: 26. Aug 2004
Ort: Nebel auf Amrum
3.154 Beiträge
 
Delphi 7 Enterprise
 
#5

AW: MySQL: Dijkstra's "kürzester Pfad"

  Alt 2. Mai 2011, 13:10
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.
  Mit Zitat antworten Zitat
Benutzerbild von patti
patti

Registriert seit: 20. Okt 2004
Ort: Mittelfranken
665 Beiträge
 
Turbo Delphi für Win32
 
#6

AW: MySQL: Dijkstra's "kürzester Pfad"

  Alt 2. Mai 2011, 13:13
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
Patrick Kreutzer
[Informatik-Student im 4. Semester]
http://www.patti-k.de/
  Mit Zitat antworten Zitat
FredlFesl

Registriert seit: 19. Apr 2011
293 Beiträge
 
Delphi 2009 Enterprise
 
#7

AW: MySQL: Dijkstra's "kürzester Pfad"

  Alt 6. Mai 2011, 07:43
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.
Das Bild hängt schief.
  Mit Zitat antworten Zitat
Benutzerbild von Memnarch
Memnarch

Registriert seit: 24. Sep 2010
736 Beiträge
 
#8

AW: MySQL: Dijkstra's "kürzester Pfad"

  Alt 6. Mai 2011, 09:57
@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
  Mit Zitat antworten Zitat
Benutzerbild von s.h.a.r.k
s.h.a.r.k

Registriert seit: 26. Mai 2004
3.159 Beiträge
 
#9

AW: MySQL: Dijkstra's "kürzester Pfad"

  Alt 6. Mai 2011, 10:00
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.
»Remember, the future maintainer is the person you should be writing code for, not the compiler.« (Nick Hodges)
  Mit Zitat antworten Zitat
Benutzerbild von rollstuhlfahrer
rollstuhlfahrer

Registriert seit: 1. Aug 2007
Ort: Ludwigshafen am Rhein
1.529 Beiträge
 
Delphi 7 Professional
 
#10

AW: MySQL: Dijkstra's "kürzester Pfad"

  Alt 6. Mai 2011, 10:21
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
Bernhard
Iliacos intra muros peccatur et extra!
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 19:01 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf