Algorithme de dijkstra sur SQL Server pour placement optimal

* Bonjour, *

Pour un projet on m'a demandé de faire un algo de placement optimal d'un centre commercial (distance entre et population des villes)

Je me suis amusé à le faire en T-SQL et je n'ai pas trouvé de vrai procédure sur le net. Il y avait une partir sur le plus court chemin écrites par un utilisateur SwePerso sur sqlteam.com mais je l'ai modifié pour le pousser plus loin.

Voici le code si cela vous intéresse:

Code:

1
2
3
4
5
6
7
8
9
10
CREATE TABLE [dbo].[Nodes] (
       [NodeID] [int] IDENTITY (1, 1) NOT NULL ,
       [NodeName] [varchar] (20)  NOT NULL ,
       [Cost] [int] NULL ,
       [PathID] [int] NULL ,
       [Calculated] [tinyint] NOT NULL,
       [Population] INT NULL,
       [Score] INT
) ON [PRIMARY]
GO

Code:

1
2
3
4
5
6
7
CREATE TABLE [dbo].[Paths] (
       [PathID] [int] IDENTITY (1, 1) NOT NULL ,
       [FromNodeID] [int] NOT NULL ,
       [ToNodeID] [int] NOT NULL ,
       [Cost] [int] NOT NULL
) ON [PRIMARY]
GO

Code:

1
2
3
4
5
6
ALTER TABLE [dbo].[Nodes] WITH NOCHECK ADD
       CONSTRAINT [PK_Nodes] PRIMARY KEY  CLUSTERED
       (
             [NodeID]
       )  ON [PRIMARY]
GO

Code:

1
2
3
4
5
6
ALTER TABLE [dbo].[Paths] WITH NOCHECK ADD
       CONSTRAINT [PK_Paths] PRIMARY KEY  CLUSTERED
       (
             [PathID]
       )  ON [PRIMARY]
GO

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ALTER TABLE [dbo].[Paths] ADD
       CONSTRAINT [FK_Paths_FromNodes] FOREIGN KEY
       (
             [FromNodeID]
       ) REFERENCES [dbo].[Nodes] (
             [NodeID]
       ),
       CONSTRAINT [FK_Paths_ToNodes] FOREIGN KEY
       (
             [ToNodeID]
       ) REFERENCES [dbo].[Nodes] (
             [NodeID]
       )
GO

Code:

1
2
3
4
5
6
7
CREATE TABLE [dbo].[PathsMatrix] (
       [MatPathID] [int] IDENTITY (1, 1) NOT NULL ,
       [FromNodeID] [int] NOT NULL ,
       [ToNodeID] [int] NOT NULL ,
       [Cost] [int]  NULL
) ON [PRIMARY]
GO

-----------------------------------------------------------------

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
CREATE PROCEDURE dbo.uspDijkstraInitializeMap
AS
 
DELETE
FROM   Paths
 
DBCC CHECKIDENT (Paths, RESEED, 0)
 
DELETE
FROM   Nodes
 
DBCC CHECKIDENT (Nodes, RESEED, 0)
GO

Code:

1
2
3
4
5
6
7
8
CREATE PROCEDURE dbo.uspDijkstraClearMap
AS
 
UPDATE Nodes
SET    PathID = NULL,
       Cost = NULL,
       Calculated = 0
GO

Code:

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
CREATE PROCEDURE dbo.uspDijkstraAddPath
(
       @FromNodeName VARCHAR(20),
       @ToNodeName VARCHAR(20),
       @Cost INT
)
AS
 
SET NOCOUNT ON
 
DECLARE      @FromNodeID INT,
       @ToNodeID INT,
       @PathID INT
 
SELECT @FromNodeID = NodeID
FROM   Nodes
WHERE  NodeName = @FromNodeName
 
IF @FromNodeID IS NULL
       BEGIN
             INSERT Nodes
                    (
                           NodeName,
                           Calculated
                    )
             VALUES (
                           @FromNodeName,
                           0
                    )
 
             SELECT @FromNodeID = SCOPE_IDENTITY()
       END
 
SELECT @ToNodeID = NodeID
FROM   Nodes
WHERE  NodeName = @ToNodeName
 
IF @ToNodeID IS NULL
       BEGIN
             INSERT Nodes
                    (
                           NodeName,
                           Calculated
                    )
             VALUES (
                           @ToNodeName,
                           0
                    )
 
             SELECT @ToNodeID = SCOPE_IDENTITY()
       END
 
SELECT @PathID = PathID
FROM   Paths
WHERE  FromNodeID = @FromNodeID
       AND ToNodeID = @ToNodeID
 
IF @PathID IS NULL
       INSERT Paths
             (
                    FromNodeID,
                    ToNodeID,
                    Cost
             )
       VALUES (
                    @FromNodeID,
                    @ToNodeID,
                    @Cost
             )
ELSE
       UPDATE Paths
       SET    Cost = @Cost
       WHERE  FromNodeID = @FromNodeID
             AND ToNodeID = @ToNodeID
GO

--------------------------------------------------------

Code:

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
CREATE PROCEDURE dbo.uspDijkstraResolve
(
       @FromNodeName VARCHAR(20),
       @ToNodeName VARCHAR(20)
)
AS
 
SET NOCOUNT ON
 
INSERT INTO PathsMatrix (FromNodeID, ToNodeID)
VALUES ((SELECT NodeID FROM nodes WHERE NodeName = @FromNodeName) , (SELECT NodeID FROM nodes WHERE NodeName = @ToNodeName) )
 
DECLARE @MatPathID INT = (SELECT TOP 1 MatPathID FROM PathsMatrix ORDER BY MatPathID DESC)
 
EXEC dbo.uspDijkstraClearMap
 
DECLARE      @FromNodeID INT,
       @ToNodeID INT,
       @NodeID INT,
       @Cost INT,
       @PathID INT
 
SELECT @FromNodeID = NodeID,
       @NodeID = NodeID
FROM   Nodes
WHERE  NodeName = @FromNodeName
 
IF @FromNodeID IS NULL
       BEGIN
             SELECT @FromNodeName = ISNULL(@FromNodeName, '')
             RAISERROR ('From node name ''%s'' can not be found.', 16, 1, @FromNodeName)
             RETURN
       END
 
SELECT @ToNodeID = NodeID
FROM   Nodes
WHERE  NodeName = @ToNodeName
 
IF @ToNodeID IS NULL
       BEGIN
             SELECT @ToNodeName = ISNULL(@ToNodeName, '')
             RAISERROR ('To node name ''%s'' can not be found.', 16, 1, @ToNodeName)
             RETURN
       END
 
UPDATE Nodes
SET    Cost = 0
WHERE  NodeID = @FromNodeID
 
WHILE @NodeID IS NOT NULL
       BEGIN
             UPDATE       ToNodes
             SET          ToNodes.Cost =      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,
                           ToNodes.PathID = 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 = @NodeID
                           AND (ToNodes.Cost IS NULL OR FromNodes.Cost + Paths.Cost < ToNodes.Cost)
                           AND ToNodes.Calculated = 0
 
             UPDATE FromNodes
             SET    FromNodes.Calculated = 1
             FROM   Nodes AS FromNodes
             WHERE  FromNodes.NodeID = @NodeID
 
             SELECT @NodeID = NULL
 
             SELECT TOP 1 @NodeID = Nodes.NodeID
             FROM         Nodes
             WHERE        Nodes.Calculated = 0
                           AND Nodes.Cost IS NOT NULL
             ORDER BY     Nodes.Cost
       END
 
CREATE TABLE #Map
             (
                    RowID INT IDENTITY(-1, -1),
                    FromNodeName VARCHAR(20),
                    ToNodeName VARCHAR(20),
                    Cost INT
             )
 
IF EXISTS (SELECT NULL FROM Nodes WHERE NodeID = @ToNodeID AND Cost IS NULL)
       BEGIN
             SELECT FromNodeName,
                    ToNodeName,
                    Cost
             FROM   #Map
 
             DROP TABLE #Map
 
             RETURN
       END
 
WHILE @FromNodeID <> @ToNodeID
       BEGIN
             SELECT       @FromNodeName = FromNodes.NodeName,
                           @ToNodeName = ToNodes.NodeName,
                           @Cost = ToNodes.Cost,
                           @PathID = ToNodes.PathID
             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 = @ToNodeID
 
             INSERT #Map
                    (
                           FromNodeName,
                           ToNodeName,
                           Cost
                    )
             VALUES (
                           @FromNodeName,
                           @ToNodeName,
                           @Cost
                    )
 
             SELECT @ToNodeID = Paths.FromNodeID
             FROM   Paths
             WHERE  Paths.PathID = @PathID
       END
UPDATE PathsMatrix
SET Cost = (SELECT max(Cost) FROM #Map)
WHERE MatPathID = @MatPathID
 
 
DROP TABLE #Map
GO

---------------------------

Code:

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
CREATE PROCEDURE dbo.uspDijkstraCreateMatrix
 
AS
 
SET NOCOUNT ON
 
IF EXISTS (SELECT 1 FROM PathsMatrix)
BEGIN
TRUNCATE TABLE  PathsMatrix
END
 
DECLARE @From VARCHAR(20),
             @To  VARCHAR(20)
 
DECLARE cursorNodes CURSOR FOR
SELECT FromNode.NodeName, ToNode.NodeName
FROM nodes as FromNode
CROSS JOIN nodes as ToNode
WHERE FromNode.NodeName <> ToNode.NodeName
 
OPEN cursorNodes
FETCH NEXT FROM cursorNodes INTO @From,
              @To
 
WHILE @@FETCH_STATUS = 0
BEGIN
EXEC dbo.uspDijkstraResolve @FromNodeName = @From,
       @ToNodeName = @To
 
FETCH NEXT  FROM cursorNodes INTO @From,
              @To
END
 
CLOSE cursorNodes
DEALLOCATE cursorNodes

--------------------

Code:

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
CREATE PROCEDURE dbo.uspDijkstraCalculateOptimal
 
AS
 
DECLARE @FromNodeID VARCHAR(20)
 
 
DECLARE cursorNodes CURSOR FOR
SELECT FromNode.NodeID
FROM nodes as FromNode
 
 
OPEN cursorNodes
FETCH NEXT FROM cursorNodes INTO @FromNodeID
 
WHILE @@FETCH_STATUS = 0
BEGIN
UPDATE Nodes SET Score = (SELECT SUM((N.Population)*P.Cost)
FROM Nodes N
JOIN PathsMatrix P ON P.FromNodeID = N.NodeID
WHERE N.NodeID = @FromNodeID) WHERE Nodes.NodeId = @FromNodeID
 
FETCH NEXT  FROM cursorNodes INTO @FromNodeID
 
END
 
CLOSE cursorNodes
DEALLOCATE cursorNodes
 
SELECT NodeName, Score
FROM Nodes
ORDER BY Score DESC
 
-------------------------
 
-- delete previous map
 
EXEC dbo.uspdijkstrainitializemap
 
-- create a new map
 
EXEC dbo.uspdijkstraaddpath 'Mauguio', 'St Aunès', 2
EXEC dbo.uspdijkstraaddpath 'St Aunès', 'Mauguio', 2
 
EXEC dbo.uspdijkstraaddpath 'Mauguio', 'Mudaison', 3
EXEC dbo.uspdijkstraaddpath 'Mudaison', 'Mauguio', 3
 
EXEC dbo.uspdijkstraaddpath 'Mauguio', 'Candillargues', 6
EXEC dbo.uspdijkstraaddpath 'Candillargues', 'Mauguio', 6
 
EXEC dbo.uspdijkstraaddpath 'Mauguio', 'La Grande Motte', 4
EXEC dbo.uspdijkstraaddpath 'La Grande Motte', 'Mauguio', 4
 
EXEC dbo.uspdijkstraaddpath 'Mauguio', 'Pérols', 6
EXEC dbo.uspdijkstraaddpath 'Pérols', 'Mauguio', 6
 
EXEC dbo.uspdijkstraaddpath 'Candillargues', 'Lansargues', 3
EXEC dbo.uspdijkstraaddpath 'Lansargues', 'Candillargues', 3
 
EXEC dbo.uspdijkstraaddpath 'Lansargues', 'St Just', 4
EXEC dbo.uspdijkstraaddpath 'St Just', 'Lansargues', 4
 
EXEC dbo.uspdijkstraaddpath 'St Just', 'Lunel', 7
EXEC dbo.uspdijkstraaddpath 'Lunel', 'St Just', 7
 
EXEC dbo.uspdijkstraaddpath 'Pérols', 'Lattes', 6
EXEC dbo.uspdijkstraaddpath 'Lattes', 'Pérols', 6
 
-- Create matrix of distances
 
EXEC dbo.uspDijkstraCreateMatrix
 
-- UPDATE populations
 
UPDATE nodes SET POPULATION = 16307 WHERE NodeName = 'Mauguio'
UPDATE nodes SET POPULATION = 3041 WHERE NodeName = 'St Aunès'
UPDATE nodes SET POPULATION = 2498 WHERE NodeName = 'Mudaison'
UPDATE nodes SET POPULATION = 1401 WHERE NodeName = 'Candillargues'
UPDATE nodes SET POPULATION = 8440 WHERE NodeName = 'La Grande Motte'
UPDATE nodes SET POPULATION = 8509 WHERE NodeName = 'Pérols'
UPDATE nodes SET POPULATION = 2744 WHERE NodeName = 'Lansargues'
UPDATE nodes SET POPULATION = 2851 WHERE NodeName = 'St Just'
UPDATE nodes SET POPULATION = 25277 WHERE NodeName = 'Lunel'
UPDATE nodes SET POPULATION = 15927 WHERE NodeName = 'Lattes'
 
 
-- Placement Optimale
 
EXEC dbo.uspDijkstraCalculateOptimal

* Merci *

Salut Evan,

intéressant !

Puis-je le poster sur mon blog, avec mention de l'auteur ???? (et du contexte, ça vous fera de la pub...)

A +

Salut Frédéric,

Avec grand plaisir. Je l'ai fait dans le cadre des cours CNAM Recherche opérationnelle et aide à la décision

Comme j'ai un parcours un peu particulier et je n'ai pas fait de la programmation avant de me lancer dans une carrière de DBA j'étais obligé de passer par le T-SQL pour faire mon projet d'algorithmes.

C'était rigolo de voir la tête du prof quand je l'ai présenté :lol:

Comme quoi le T-SQL est un outil puissant même pour les algos traditionnellement traitées par des langages de programmation séquentielle.

Le seul souci, si on veut vraiment avoir des perfs qui correspondent aux autres langages, c'est qu'on passe par des écritures disques pour faire cela. Pour améliorer mon code pour faire cela j'imagine qu'on pouvait passer par des variables tables au lieu des vraies tables. Ceci permettra d'écrire les données dans la mémoire et éviter les E/S. :ccool:

C'est intéressant, j'ai parcouru rapidement mais ça mérite que je m'y repenche plus en avant.
Merci du partage.

Citation:

Envoyé par evanbarke

Pour améliorer mon code pour faire cela j'imagine qu'on pouvait passer par des variables tables au lieu des vraies tables. Ceci permettra d'écrire les données dans la mémoire et éviter les E/S. :ccool:

Détrompe toi... variables tables ou tables temporaire... Même combat, elles sont toutes écrites dans la tempsdb et journaliées. Tu peut le voir en faisant :
Code:

1 2 3 4 SELECT * FROM tempdb.INFORMATION_SCHEMA.TABLES GO DECLARE @T TABLE (C INT) SELECT * FROM tempdb.INFORMATION_SCHEMA.TABLES
ou elle apparaissent avec un nom en #???????? ou ??????? est de l'hexadécimal...

Avec beaucoup de données, il est plus avantageux d'utiliser des tables temporaires indexées; En effet, elles disposent de statistiques alors que les variables tables sont évaluées à 1 seule ligne en cardinalité...

A +

Ah bah, j'ai appris quelque chose. Merci. N'y a-t-il pas de possibilité du tout de stocker ses infos en mémoires et pas écrire sur le disque (Sans utiliser un outil comme ceci)? Je suis d'accords avec toi par contre. Si on veut faire des gros calculs avec beaucoup de données si sera mieux d'utiliser la structure que j'ai fait au début pour profiter des indexes.

C'est pas grave car très peu de chose sont journalisées, si les tables sont peu volumineuses... Pour appel, toutes les opérations relationnelles sont faites en RAM !

A +

Exacte! Merci encore. Donc voilà. Rien à faire alors :lol: Bon week-end!

Et voilà :

http://blog.developpez.com/sqlpro/p1...norme/dijkstra

J'ai fait quelques modification mineures, surtout sur les curseurs et remplacé la table temporaire par une variable table...

(en sus je t'ai désigné vendeur de peau de kangourou... !)

A +

Haha excellent!

Cependant, étant sud-africain, vendeur de peaux de springbok aurait été plus réaliste mais comme tu veux :bravo:

C'est sympa! J'espère que ça va aider quelqu'un.

Mince, je te pensais australien !

A +

Un australien!!! Quel horreur!! HAHA :lol: