Mysql을 이용해서 dijkstra's shortest pathway 구하는 방법입니다.
http://www.artfulsoftware.com/infotree/queries.php#766 사이트가면 자세히 보실 수 있습니다.
저는 주석을 달아보았습니다. 참고하세요~
The DDL:
DROP TABLE IF EXISTS dijnodes,dijpaths;
CREATE TABLE dijnodes ( //테이블을 두 개 만들어 줍니다.
nodeID int PRIMARY KEY AUTO_INCREMENT NOT NULL,
nodename varchar (50) 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
);
Here is a stored procedure to populate valid nodes and paths:
간단하게 설명하자면 call dijAddPath('a', 'b', 1) 이라고 명령을 하면
만약 a, b가 기존 node table에 존재한다면 cost를 지금 값으로 변경하고
만약 a, b가 기존 node table에 없다면 node로 추가하여라~ 이런 명령인 듯 싶네요.
또한 이 데이터는 dijpaths 테이블에도 포함됩니다.
DROP PROCEDURE IF EXISTS dijAddPath;
DELIMITER | // 구분자를 변경해줍니다.
CREATE PROCEDURE dijAddPath( // procedure 하나 생성해주네요.
pFromNodeName VARCHAR(20), pToNodeName VARCHAR(20), pCost INT
)
BEGIN // 시작해 볼까요~
DECLARE vFromNodeID, vToNodeID, vPathID INT; // procedure 변수를 받아옵니다.
SET vFromNodeID = ( SELECT NodeID FROM dijnodes WHERE NodeName = pFromNodeName );
IF vFromNodeID IS NULL THEN // 만약 입력받은 node가 존재하지 않으면?
BEGIN
INSERT INTO dijnodes (NodeName,Calculated) VALUES (pFromNodeName,0); // dijnodes 테이블에 값을 추가합니다.
SET vFromNodeID = LAST_INSERT_ID(); //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 ;
Use dijAddpath() to populate the tables:
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 |
+--------+------------+----------+------+
Now for the stored procedure, a 6-step:
1. null out path columns in the nodes table
2. find the nodeIDs referenced by input params
3. loop through all uncalculated one-step paths, calculating costs in each
4. if a node remains uncalculated, the graph is invalid, so quit
5. write the path sequence to a temporary table
6. query the temp table to show the result
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)
ALUES(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 |
+--------------+------------+------+