-
Notifications
You must be signed in to change notification settings - Fork 681
/
dbo.usp_Dijkstra.sql
117 lines (99 loc) · 4.33 KB
/
dbo.usp_Dijkstra.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
IF OBJECT_ID (N'dbo.usp_Dijkstra', 'P') IS NULL
EXECUTE('CREATE PROCEDURE usp_Dijkstra AS SELECT 1');
GO
ALTER PROCEDURE dbo.usp_Dijkstra (@StartNode int, @EndNode int = NULL)
AS
/*
http://www.hansolav.net/sql/graphs.html
Runs Dijkstras algorithm from the specified node.
@StartNode: Id of node to start from.
@EndNode: Stop the search when the shortest path to this node is found.
Specify NULL find shortest path to all nodes.
CREATE TABLE dbo.Node
(
Id int NOT NULL PRIMARY KEY,
Name varchar(50) NULL
)
CREATE TABLE dbo.Edge
(
FromNode int NOT NULL REFERENCES dbo.Node (Id),
ToNode int NOT NULL REFERENCES dbo.Node (Id),
[Weight] decimal (10, 3) NULL,
PRIMARY KEY CLUSTERED (FromNode ASC, ToNode ASC)
)
*/
BEGIN
-- Automatically rollback the transaction if something goes wrong.
SET XACT_ABORT ON
BEGIN TRAN
-- Increase performance and do not intefere with the results.
SET NOCOUNT ON;
-- Create a temporary table for storing the estimates as the algorithm runs
CREATE TABLE #Nodes
(
Id int NOT NULL PRIMARY KEY, -- The Node Id
Estimate decimal(10,3) NOT NULL, -- What is the distance to this node, so far?
Predecessor int NULL, -- The node we came from to get to this node with this distance.
Done bit NOT NULL -- Are we done with this node yet (is the estimate the final distance)?
)
-- Fill the temporary table with initial data
INSERT INTO #Nodes (Id, Estimate, Predecessor, Done)
SELECT Id, 9999999.999, NULL, 0 FROM dbo.Node
-- Set the estimate for the node we start in to be 0.
UPDATE #Nodes SET Estimate = 0 WHERE Id = @StartNode
IF @@rowcount <> 1
BEGIN
DROP TABLE #Nodes
RAISERROR ('Could not set start node', 11, 1)
ROLLBACK TRAN
RETURN 1
END
DECLARE @FromNode int, @CurrentEstimate int
-- Run the algorithm until we decide that we are finished
WHILE 1 = 1
BEGIN
-- Reset the variable, so we can detect getting no records in the next step.
SELECT @FromNode = NULL
-- Select the Id and current estimate for a node not done, with the lowest estimate.
SELECT TOP 1 @FromNode = Id, @CurrentEstimate = Estimate
FROM #Nodes WHERE Done = 0 AND Estimate < 9999999.999
ORDER BY Estimate
-- Stop if we have no more unvisited, reachable nodes.
IF @FromNode IS NULL OR @FromNode = @EndNode BREAK
-- We are now done with this node.
UPDATE #Nodes SET Done = 1 WHERE Id = @FromNode
-- Update the estimates to all neighbour node of this one (all the nodes
-- there are edges to from this node). Only update the estimate if the new
-- proposal (to go via the current node) is better (lower).
UPDATE #Nodes
SET Estimate = @CurrentEstimate + e.Weight, Predecessor = @FromNode
FROM #Nodes n INNER JOIN dbo.Edge e ON n.Id = e.ToNode
WHERE Done = 0 AND e.FromNode = @FromNode AND (@CurrentEstimate + e.Weight) < n.Estimate
END;
-- Select the results. We use a recursive common table expression to
-- get the full path from the start node to the current node.
WITH BacktraceCTE(Id, Name, Distance, Path, NamePath)
AS
(
-- Anchor/base member of the recursion, this selects the start node.
SELECT n.Id, node.Name, n.Estimate, CAST(n.Id AS varchar(8000)),
CAST(node.Name AS varchar(8000))
FROM #Nodes n JOIN dbo.Node node ON n.Id = node.Id
WHERE n.Id = @StartNode
UNION ALL
-- Recursive member, select all the nodes which have the previous
-- one as their predecessor. Concat the paths together.
SELECT n.Id, node.Name, n.Estimate,
CAST(cte.Path + ',' + CAST(n.Id as varchar(10)) as varchar(8000)),
CAST(cte.NamePath + ',' + node.Name AS varchar(8000))
FROM #Nodes n JOIN BacktraceCTE cte ON n.Predecessor = cte.Id
JOIN dbo.Node node ON n.Id = node.Id
)
SELECT Id, Name, Distance, Path, NamePath FROM BacktraceCTE
WHERE Id = @EndNode OR @EndNode IS NULL -- This kind of where clause can potentially produce
ORDER BY Id -- a bad execution plan, but I use it for simplicity here.
DROP TABLE #Nodes
COMMIT TRAN
RETURN 0
END
GO