psGsSsip

1-- Runs Dijkstras algorithm from the specified node.
2-- StartNode: Id of node to start from.
3-- EndNode: Stop the search when the shortest path to this node is found.
4-- Specify NULL find shortest path to all nodes.
5DELIMITER $$
6
7DROP PROCEDURE IF EXISTS evemap.RouteIt $$
8CREATE PROCEDURE RouteIt (StartNode INT, EndNode INT)
9BEGIN
10
11-- Create a temporary table for storing the estimates as the algorithm runs
12	CREATE TEMPORARY TABLE Nodes
13	(
14	Id int NOT NULL AUTO_INCREMENT, -- The Node Id
15	Estimate decimal(10,3) NOT NULL, -- What is the distance to this node, so far?
16	Predecessor int NULL, -- The node we came from to get to this node with this distance.
17	Done bit NOT NULL, -- Are we done with this node yet (is the estimate the final distance)?
18	PRIMARY KEY (Id)
19	);
20
21	-- Fill the temporary table with initial data
22	INSERT INTO Nodes (Id, Estimate, Predecessor, Done)
23	SELECT solarSystemID, 9999999.999, NULL, 0 FROM mapSolarSystems;
24
25	-- Set the estimate for the node we start in to be 0.
26	UPDATE Nodes SET Estimate = 0 WHERE Id = StartNode;
27
28	DECLARE FromNode INT;
29	DECLARE CurrentEstimate INT;
30
31	-- Run the algorithm until we decide that we are finished
32	While_Loop: WHILE 1=1 DO
33		-- Reset the variable, so we can detect getting no records in the next step.
34		SET FromNode = NULL;
35
36		-- Select the Id and current estimate for a node not done, with the lowest estimate.
37		SELECT Id,Estimate INTO FromNode, CurrentEstimate
38		FROM Nodes WHERE Done = 0 AND Estimate < 9999999.999
39		ORDER BY Estimate LIMIT 1;
40
41		-- Stop if we have no more unvisited, reachable nodes.
42		IF FromNode IS NULL OR FromNode = EndNode THEN 
43			LEAVE While_Loop;
44		ELSE
45			ITERATE While_Loop;
46		END IF;
47		-- We are now done with this node.
48		UPDATE Nodes SET Done = 1 WHERE Id = FromNode;
49
50		-- Update the estimates to all neighbour node of this one (all the nodes
51		-- there are edges to from this node). Only update the estimate if the new
52		-- proposal (to go via the current node) is better (lower).
53
54		UPDATE Nodes
55		SET Estimate = CurrentEstimate + 1, Predecessor = FromNode
56		FROM Nodes n INNER JOIN dbo.mapSolarSystemJumps e ON n.Id = e.toSolarSystemID
57		WHERE Done = 0 AND e.fromSolarSystemID = FromNode AND (CurrentEstimate + 1) < n.Estimate;
58
59	END WHILE;
60
61	-- Select the results. We use a recursive common table expression to
62	-- get the full path from the start node to the current node.
63	CREATE VIEW BacktraceCTE(Id, Name, Distance, Path, NamePath)
64	AS
65	(
66	-- Anchor/base member of the recursion, this selects the start node.
67	SELECT n.Id, node.solarSystemName, n.Estimate, CAST(n.Id AS varchar(8000)),
68	CAST(node.solarSystemName AS varchar(8000))
69	FROM Nodes n JOIN mapSolarSystems node ON n.Id = node.solarSystemID
70	WHERE n.Id = StartNode
71
72	UNION ALL
73
74	-- Recursive member, select all the nodes which have the previous
75	-- one as their predecessor. Concat the paths together.
76	SELECT n.Id, node.solarSystemName, n.Estimate,
77	CAST(cte.Path + ',' + CAST(n.Id as varchar(10)) as varchar(8000)),
78	CAST(cte.NamePath + ',' + node.solarSystemName AS varchar(8000))
79	FROM Nodes n JOIN BacktraceCTE cte ON n.Predecessor = cte.Id
80	JOIN dbo.mapSolarSystems node ON n.Id = node.solarSystemID
81	);
82
83	SELECT Id, Name, Distance, Path, NamePath FROM BacktraceCTE
84	WHERE Id = EndNode OR EndNode IS NULL -- This kind of where clause can potentially produce
85	ORDER BY Id; -- a bad execution plan, but I use it for simplicity here.	
86	
87	
88	DROP TABLE Nodes;
89	-- COMMIT TRAN
90END$$
91DELIMITER;