Problem
I’m familiar with Graph Theory. However, I’m not clear on Shortest Path Algorithms. Can you provide more information and examples of working with these algorithms in SQL Server?
Solution
Graph theory is a branch of mathematics that studies structures called graphs, which are a way to model relationships between objects. They consist of nodes, also called vertices, and edges that connect those nodes. This theory is used in computer science, biology, logistics, and social networks analyses.
Shortest Path Algorithms are fundamental tools in computer science and graph theory. They are used to find the most efficient path between two points in a graph, where the graph can represent various real-world scenarios like:
- Transportation networks: Finding the fastest or shortest route between two locations.
- Computer networks: Determining the optimal path for data packets to travel.
- Social networks: Analyzing relationships and information propagation.
- Game AI: Planning character movement and decision-making.
This might mean the shortest or fastest route, the path requiring the least fuel, the lowest fare, or even the one that avoids speed traps.
How do you work with those algorithms in SQL Server without using external tools?
Terms and Definitions
Graph Nodes (Vertices): Points representing entities.
Graph Edges (links):Lines connecting pairs of nodes, representing relationships.
Graph Types
- Undirect: Edges have no direction, like friendship in a social network.
- Directed (Digraph): Edges have a direction, indicated by arrows, like links in a website.
- Weighted: Edges have weights, representing costs or distances.
- Bipartite: Nodes can be divided into two disjoint sets, and edges only connect nodes from different sets.
Special Graphs
- Tree: A connected graph with no cycles.
- Complete: Every pair of nodes is connected by an edge.
- Planar: Can be drawn on a plane without edges crossing.
Graph Properties
- Degree: The number of edges connected to a vertex.
- Path: The sequence of nodes connected by edges.
- Cycle: A path that starts and ends at the same vertex without repeating edges or nodes.
- Connectedness: Whether there’s a path between every pair of nodes.
- Acyclic: A graph with no cycles.
Graph Representations
- Adjacency Matrix: A two-dimensional matrix where rows and columns represent nodes and entries indicate the presence of an edge.
- Adjacency List: A list of lists where each vertex lists its neighboring nodes.
Graph Heuristics: Heuristics in graph theory are approximate methods or strategies used to solve complex graph problems efficiently. They are especially useful in scenarios where finding an exact solution is computationally expensive or impractical. A heuristic provides an estimate to guide algorithms, particularly in pathfinding and optimization problems. It is good to keep in mind that the heuristics should be admissible when they never overestimate the actual cost to reach the goal, and consistent to ensure that once a node is expanded, its cost will not need to be updated.
Negative Weights: Negative weights provide a way to model real-world phenomena involving savings, gains, or rewards, making them a powerful concept in graph theory. For example, in a financial transaction graph, negative weights can represent payments received or debt cancellations, or in a gaming scenario, moving to certain nodes might provide power-ups with negative weights or impose penalties as positive weights.
SQL Server Graph Database
Besides the fact that SQL Server has built-in Graph Tables, its intended use is when your application deals with complex, interconnected data with many-to-many relationships, like in social networks, fraud detection, and biological pathways. It is not designed for simple data that has primarily a one-to-many relationship; then it is preferred to use a traditional relational database because it is more efficient. Also, consideration should be given to the learning curve once SQL Server Graph tables leverage existing T-SQL syntax, understanding graph concepts and query patterns demands time to learn.
SQL Tables
I will work with four algorithms in the traditional relational database, not graph tables.
Create a table for the NODES:
CREATE TABLE [dbo].[GraphNodes](
[NodeId] [nvarchar](50) NOT NULL,
[x] [float] NOT NULL,
[y] [float] NOT NULL,
[ParentNode] nvarchar(50) NULL,
[g] [float] NULL,
[h] [float] NULL,
[f] AS ([g]+[h]) PERSISTED,
[IsClosed] [bit] NULL,
[IsOpened] [bit] NULL,
CONSTRAINT [PK__GraphNodes] PRIMARY KEY CLUSTERED
(
[NodeId] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY]
GOYou have to enter the Node Name and its x and y positions. The other columns will be used by the algorithms. For example, x could be the latitude and y the longitude for named cities.
Create a table for the EDGES:
CREATE TABLE [dbo].[GraphEdges](
[FromNode] [nvarchar](50) NOT NULL FOREIGN KEY REFERENCES GraphNodes(NodeId),
[ToNode] [nvarchar](50) NOT NULL FOREIGN KEY REFERENCES GraphNodes(NodeId),
[Cost] [float] NULL,
CONSTRAINT [PK__GraphEdges] PRIMARY KEY CLUSTERED
(
[FromNode] ASC,
[ToNode] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY]
GO
SQL Procedures
Use the following stored procedure to enter values in the edges. This sets the edges as bi or unidirectional, and whether they should be deleted or not.
-- =============================================
-- Author: SCP - MSSQLTips
-- Create date: 20241218
-- Description: Graph Edges data entry
-- =============================================
CREATE OR ALTER PROCEDURE [dbo].[uspGraphEdges]
(@NodeFrom nvarchar(50)
,@NodeTo nvarchar(50)
,@Cost float
,@IsOneWay bit
,@ToDelete bit)
AS
BEGIN
SET NOCOUNT ON;
BEGIN TRY
IF LEN(@NodeFrom) = 0 OR LEN(@NodeTo) = 0 OR @NodeFrom = @NodeTo OR @Cost IS NULL
RETURN;
IF @ToDelete = 1
DELETE FROM [dbo].[GraphEdges]
WHERE [FromNode] = @NodeFrom AND
[ToNode] = @NodeTo;
ELSE BEGIN
IF EXISTS
(SELECT 1
FROM [dbo].[GraphEdges]
WHERE ([FromNode] = @NodeFrom AND [ToNode] = @NodeTo) OR
([FromNode] = @NodeTo AND [ToNode] = @NodeFrom))
UPDATE [dbo].[GraphEdges]
SET [Cost] = @Cost
WHERE (([FromNode] = @NodeFrom AND [ToNode] = @NodeTo) OR
([FromNode] = @NodeTo AND [ToNode] = @NodeFrom)) AND
[Cost] <> @Cost;
ELSE IF @IsOneWay = 1
INSERT INTO [dbo].[GraphEdges]
([FromNode],[ToNode],[Cost])
VALUES (@NodeFrom,@NodeTo,@Cost);
ELSE
INSERT INTO [dbo].[GraphEdges]
([FromNode],[ToNode],[Cost])
VALUES (@NodeFrom,@NodeTo,@Cost)
,(@NodeTo,@NodeFrom,@Cost);
END;
RETURN;
END TRY
BEGIN CATCH
IF @@TRANCOUNT > 0
BEGIN
ROLLBACK TRANSACTION;
END
-- Print error information.
PRINT 'Error: ' + CONVERT(varchar(50), ERROR_NUMBER()) +
', Severity: ' + CONVERT(varchar(5), ERROR_SEVERITY()) +
', State: ' + CONVERT(varchar(5), ERROR_STATE()) +
', Procedure: ' + ISNULL(ERROR_PROCEDURE(), '-') +
', Line: ' + CONVERT(varchar(5), ERROR_LINE());
PRINT ERROR_MESSAGE();
END CATCH;
END
GOSQL Function
This function calculates the heuristics values of the nodes. If the x and y values are longitude and latitude, we will apply the haversine formula; otherwise, the Euclidean.
-- =============================================
-- Author: SCP - MSSQLTips
-- Create date: 20241217
-- Description: Graph Heuristic calculation
-- =============================================
CREATE OR ALTER FUNCTION [dbo].[ufnGraphHeuristic]
(@NodeFrom nvarchar(50)
,@NodeTo nvarchar(50)
,@IsLatLong bit)
RETURNS float
AS
BEGIN
DECLARE @X1 float
,@Y1 float
,@X2 float
,@Y2 float;
SELECT @X1 = x
,@Y1 = y
FROM [dbo].[GraphNodes]
WHERE [NodeId] = @NodeFrom;
SELECT @X2 = x
,@Y2 = y
FROM [dbo].[GraphNodes]
WHERE [NodeId] = @NodeTo;
IF @IsLatLong = 0
RETURN SQRT(POWER(@X2 - @X1, 2) + POWER(@Y2 - @Y1, 2));
-- Earth's radius in km
DECLARE @R float = 6371;
DECLARE @LatDiff float = RADIANS(@X2 - @X1);
DECLARE @LonDiff float = RADIANS(@Y2 - @Y1);
DECLARE @A float;
SET @A = POWER(SIN(@LatDiff / 2), 2) +
COS(RADIANS(@X1)) * COS(RADIANS(@X2)) *
POWER(SIN(@LonDiff / 2), 2);
RETURN @R * 2 * ATN2(SQRT(@A), SQRT(1 - @A));
END
GOAlgorithms
I will work with four algorithms in the relational database, not using graph tables.
A-star (A*) Algorithm
This algorithm works similarly to Dijkstra´s algorithm with an additional heuristic for the distance between nodes, and thus is normally faster once it is goal-oriented. The constraint is the fact that all edges must not be negative.
-- =============================================
-- Author: SCP - MSSQLTips
-- Create date: 20241218
-- Description: Graph A-star (A*) Algorithm
-- =============================================
CREATE OR ALTER PROCEDURE [dbo].[uspGraphAstar]
(@StartNode nvarchar(50)
,@TargetNode nvarchar(50)
,@IsLatLong bit)
AS
BEGIN
SET NOCOUNT ON;
BEGIN TRY
IF LEN(@StartNode) = 0 OR
LEN(@TargetNode) = 0 OR
@StartNode = @TargetNode OR NOT EXISTS
(SELECT 1 FROM [dbo].[GraphNodes] WHERE [NodeId] = @StartNode) OR NOT EXISTS
(SELECT 1 FROM [dbo].[GraphNodes] WHERE [NodeId] = @TargetNode)
RETURN;
IF EXISTS (SELECT 1 FROM [GraphEdges] WHERE [Cost] < 0) BEGIN
PRINT ('This algorithm is not suitable for negative values. Use the Bellman-Ford algorithm instead.')
RETURN
END;
DECLARE @CurrentNode nvarchar(50)
,@G float;
UPDATE [dbo].[GraphNodes]
SET [ParentNode] = NULL
,[g] = NULL
,[h] = NULL
,[IsClosed] = 0
,[IsOpened] = 0;
UPDATE [dbo].[GraphNodes]
SET [ParentNode] = NULL
,[g] = 0
,[h] = [dbo].[ufnGraphHeuristic] (@StartNode,@TargetNode,@IsLatLong)
,[IsOpened] = 1
WHERE [NodeId] = @StartNode;
WHILE EXISTS
(SELECT 1
FROM [dbo].[GraphNodes]
WHERE [IsOpened] = 1) BEGIN
SELECT TOP 1 @CurrentNode = [NodeId]
,@G = G
FROM [dbo].[GraphNodes]
WHERE [f] IS NOT NULL AND
[IsClosed] = 0
ORDER BY F;
IF @CurrentNode = @TargetNode BEGIN
BREAK;
END
UPDATE [dbo].[GraphNodes]
SET [IsOpened] = 0
,[IsClosed] = 1
WHERE [NodeId] = @CurrentNode;
WITH cteDist AS
(SELECT Cost ct
,FromNode fn
,ToNode tn
FROM [dbo].[GraphEdges]
WHERE [FromNode] = @CurrentNode)
UPDATE [dbo].[GraphNodes]
SET [IsOpened] = 1
,[IsClosed] = 0
,[ParentNode] = @CurrentNode
,[g] = @G + ct
,[h] = [dbo].[ufnGraphHeuristic] ([NodeId],@TargetNode,@IsLatLong)
FROM cteDist
WHERE ([g] > @G + ct OR
[g] IS NULL) AND
[NodeId] = tn;
END;
WITH OutputPath AS
(SELECT NodeId AS ClosedNode
,ParentNode AS ClosedParent
,1 as LevelOrder
,[g]
FROM [dbo].[GraphNodes]
WHERE [IsOpened] = 1 AND
[NodeId] = @TargetNode
UNION ALL
SELECT C.NodeId
,C.ParentNode
,P.LevelOrder + 1 AS LevelOrder
,C.G
FROM [dbo].[GraphNodes] C INNER JOIN
OutputPath P ON
C.NodeId = P.ClosedParent
WHERE [IsClosed] = 1)
SELECT ClosedNode
,G AS Cost
FROM OutputPath
ORDER BY LevelOrder desc;
RETURN;
END TRY
BEGIN CATCH
IF @@TRANCOUNT > 0
BEGIN
ROLLBACK TRANSACTION;
END
-- Print error information.
PRINT 'Error: ' + CONVERT(varchar(50), ERROR_NUMBER()) +
', Severity: ' + CONVERT(varchar(5), ERROR_SEVERITY()) +
', State: ' + CONVERT(varchar(5), ERROR_STATE()) +
', Procedure: ' + ISNULL(ERROR_PROCEDURE(), '-') +
', Line: ' + CONVERT(varchar(5), ERROR_LINE());
PRINT ERROR_MESSAGE();
END CATCH;
END
GOBellman-Ford Algorithm
This algorithm is to be used if negative weights exist.
-- =============================================
-- Author: SCP - MSSQLTips
-- Create date: 20241218
-- Description: Graph Bellman-Ford Algorithm
-- =============================================
CREATE OR ALTER PROCEDURE [dbo].[uspGraphBellmanFord]
(@StartNode nvarchar(50))
AS
BEGIN
SET NOCOUNT ON;
BEGIN TRY
IF LEN(@StartNode) = 0 OR NOT EXISTS
(SELECT 1 FROM [dbo].[GraphNodes] WHERE [NodeId] = @StartNode)
RETURN;
UPDATE [dbo].[GraphNodes]
SET [ParentNode] = NULL
,[g] = CASE WHEN [NodeId] = @StartNode
THEN 0
ELSE 1E6
END
,[h] = NULL
,[IsClosed] = 0
,[IsOpened] = 0;
DECLARE @i int
,@From nvarchar(50)
,@To nvarchar(50)
,@Mx int
,@v1 float
,@v2 float
,@Cost float;
SET @Mx = (SELECT COUNT(*) FROM [dbo].[GraphNodes]);
SET @i = 1;
WHILE @i < @Mx BEGIN
DECLARE crsBF CURSOR FAST_FORWARD READ_ONLY FOR
SELECT [FromNode]
,[ToNode]
,[Cost]
FROM [dbo].[GraphEdges];
OPEN crsBF
FETCH NEXT FROM crsBF INTO @From,@To,@Cost;
WHILE @@FETCH_STATUS = 0
BEGIN
SELECT @v1 = [g] FROM [GraphNodes] WHERE [NodeId] = @From;
SELECT @v2 = [g] FROM [GraphNodes] WHERE [NodeId] = @To;
UPDATE [GraphNodes]
SET [g] = CASE WHEN @v2 > @v1 + @Cost
THEN @v1 + @Cost
ELSE @v2
END
WHERE [NodeId] = @To;
FETCH NEXT FROM crsBF INTO @From,@To,@Cost;
END
CLOSE crsBF
DEALLOCATE crsBF
SET @i += 1;
END;
IF EXISTS
(SELECT 1
FROM [GraphNodes] D JOIN
[dbo].[GraphEdges] G ON
D.NodeId = G.ToNode JOIN
[GraphNodes] D2 ON
G.FromNode = D2.NodeId
WHERE D.g > G.Cost + D2.g)
PRINT 'Graph contains a negative weight cycle';
ELSE
PRINT 'Shortest paths computed successfully';
SELECT [NodeId]
,[x]
,[y]
,[g]
FROM [dbo].[GraphNodes]
RETURN;
END TRY
BEGIN CATCH
IF @@TRANCOUNT > 0
BEGIN
ROLLBACK TRANSACTION;
END
-- Print error information.
PRINT 'Error: ' + CONVERT(varchar(50), ERROR_NUMBER()) +
', Severity: ' + CONVERT(varchar(5), ERROR_SEVERITY()) +
', State: ' + CONVERT(varchar(5), ERROR_STATE()) +
', Procedure: ' + ISNULL(ERROR_PROCEDURE(), '-') +
', Line: ' + CONVERT(varchar(5), ERROR_LINE());
PRINT ERROR_MESSAGE();
END CATCH;
END
GODijkstra’s Algorithm
This algorithm computes the shortest path between two nodes whenever all edge weights are non-negative.
-- =============================================
-- Author: SCP - MSSQLTips
-- Create date: 20241218
-- Description: Graph Dijkstra's Algorithm
-- =============================================
CREATE OR ALTER PROCEDURE [dbo].[uspGraphDijkstra]
(@StartNode nvarchar(50))
AS
BEGIN
SET NOCOUNT ON;
BEGIN TRY
IF LEN(@StartNode) = 0 OR NOT EXISTS
(SELECT 1 FROM [dbo].[GraphNodes] WHERE [NodeId] = @StartNode)
RETURN;
IF EXISTS (SELECT 1 FROM [GraphEdges] WHERE [Cost] < 0) BEGIN
PRINT ('This algorithm is not suitable for negative values. Use the Bellman-Ford algorithm instead.')
RETURN
END;
UPDATE [dbo].[GraphNodes]
SET [ParentNode] = NULL
,[g] = CASE WHEN [NodeId] = @StartNode
THEN 0
ELSE 1E6
END
,[h] = NULL
,[IsClosed] = 0
,[IsOpened] = 1;
DECLARE @CurrentNode nvarchar(50)
,@CurrentD float;
WHILE EXISTS
(SELECT 1
FROM [dbo].[GraphNodes]
WHERE [IsOpened] = 1) BEGIN
SELECT TOP 1 @CurrentNode = [NodeId]
,@CurrentD = [g]
FROM [dbo].[GraphNodes]
WHERE [IsOpened] = 1
ORDER BY [g];
UPDATE [dbo].[GraphNodes]
SET [IsOpened] = 0
WHERE [NodeId] = @CurrentNode;
WITH CteCur AS
(SELECT [ToNode] AS NodeTo
,[Cost] AS NodeD
FROM [dbo].[GraphEdges]
WHERE [FromNode] = @CurrentNode)
UPDATE [dbo].[GraphNodes]
SET [g] = NodeD + @CurrentD
,[ParentNode] = @CurrentNode
FROM CteCur
WHERE [g] > NodeD + @CurrentD AND
[NodeId] = NodeTo;
END
SELECT [NodeId]
,[x]
,[y]
,[g]
FROM [dbo].[GraphNodes]
RETURN;
END TRY
BEGIN CATCH
IF @@TRANCOUNT > 0
BEGIN
ROLLBACK TRANSACTION;
END
-- Print error information.
PRINT 'Error: ' + CONVERT(varchar(50), ERROR_NUMBER()) +
', Severity: ' + CONVERT(varchar(5), ERROR_SEVERITY()) +
', State: ' + CONVERT(varchar(5), ERROR_STATE()) +
', Procedure: ' + ISNULL(ERROR_PROCEDURE(), '-') +
', Line: ' + CONVERT(varchar(5), ERROR_LINE());
PRINT ERROR_MESSAGE();
END CATCH;
END
GOFloyd-Warshall Algorithm
This algorithm computes the shortest paths between all pairs of nodes, with no restrictions for negative edge weights.
-- =============================================
-- Author: SCP - MSSQLTips
-- Create date: 20241218
-- Description: Graph Floyd-Warshall Algorithm
-- =============================================
CREATE OR ALTER PROCEDURE [dbo].[uspGraphFloydWarshall]
AS
BEGIN
SET NOCOUNT ON;
BEGIN TRY
IF NOT EXISTS
(SELECT 1 FROM [dbo].[GraphNodes])
RETURN;
DECLARE @i int
,@j int
,@k int
,@Mx int
,@v1 float
,@v2 float
,@v3 float
,@columns nvarchar(MAX)
,@sql nvarchar(MAX);
DECLARE @Input
TABLE (Cf nvarchar(50)
,Ct nvarchar(50)
,Cg float
,Cx int
,Cy int);
INSERT INTO @Input
(Cf
,Ct
,Cg)
SELECT N2.NodeId AS C1
,N1.NodeId AS C2
,CASE WHEN N1.NodeId = N2.NodeId
THEN 0
ELSE 1E6
END AS Cost
FROM [dbo].[GraphNodes] N1 CROSS JOIN
[dbo].[GraphNodes] N2;
UPDATE @Input
SET [Cg] = [COST]
FROM [dbo].[GraphEdges]
WHERE [Cf] = [FromNode] AND
[Ct] = [ToNode];
WITH CteF AS
(SELECT ROW_NUMBER() OVER(ORDER BY [NodeId]) n
,[NodeId] i
FROM [dbo].[GraphNodes])
UPDATE @Input
SET Cx = n
FROM CteF
WHERE Cf = i;
WITH CteT AS
(SELECT ROW_NUMBER() OVER(ORDER BY [NodeId]) n
,[NodeId] i
FROM [dbo].[GraphNodes])
UPDATE @Input
SET Cy = n
FROM CteT
WHERE Ct = i;
SET @Mx = (SELECT COUNT(*) FROM [dbo].[GraphNodes]);
SET @k = 1;
WHILE @k <= @Mx BEGIN
SET @i = 1;
WHILE @i <= @Mx BEGIN
SET @j = 1;
WHILE @j <= @Mx BEGIN
SET @v1 = (SELECT [Cg] FROM @Input WHERE [Cx] = @i AND [Cy] = @j);
SET @v2 = (SELECT [Cg] FROM @Input WHERE [Cx] = @i AND [Cy] = @k);
SET @v3 = (SELECT [Cg] FROM @Input WHERE [Cx] = @k AND [Cy] = @j);
IF @v1 > @v2 + @v3
UPDATE @Input
SET [Cg] = @v2 + @v3
WHERE [Cx] = @i AND
[Cy] = @j;
SET @j += 1;
END
SET @i += 1;
END
SET @k += 1;
END
-- =================================================================================
SELECT *
INTO #TempInputTable
FROM @Input;
SELECT @columns = STRING_AGG(QUOTENAME(Cf), ',') WITHIN GROUP (ORDER BY Cf)
FROM (SELECT DISTINCT Cf FROM @Input) AS DistinctCols;
SET @sql = 'SELECT Cf, ' + @columns + '
FROM (SELECT Cf
,Ct
,Cg
FROM #TempInputTable) AS SourceTable
PIVOT (MAX(Cg) FOR Ct IN
(' + @columns + ')) AS PivotTable
ORDER BY Cf;';
EXEC sp_executesql @sql;
DROP TABLE #TempInputTable;
RETURN;
END TRY
BEGIN CATCH
IF @@TRANCOUNT > 0
BEGIN
ROLLBACK TRANSACTION;
END
-- Print error information.
PRINT 'Error: ' + CONVERT(varchar(50), ERROR_NUMBER()) +
', Severity: ' + CONVERT(varchar(5), ERROR_SEVERITY()) +
', State: ' + CONVERT(varchar(5), ERROR_STATE()) +
', Procedure: ' + ISNULL(ERROR_PROCEDURE(), '-') +
', Line: ' + CONVERT(varchar(5), ERROR_LINE());
PRINT ERROR_MESSAGE();
END CATCH;
END
GOExample – European Cities Hub
Let’s suppose that a logistics company has branches in those cities and dispatches goods following fixed routes between them.
Let’s choose random cities in Europe and some distance between them to test the algorithms. The first thing to do is to add them as our NODES. I will use x as latitude and y as longitude.
INSERT INTO [dbo].[GraphNodes]
([NodeId],[x],[y])
VALUES ('Berlin', 52.5200, 13.4050)
,('Brussels', 50.8503, 4.3517)
,('Frankfurt', 50.1109, 8.6821)
,('Geneva', 46.2044, 6.1432)
,('Lisbon', 38.7169, -9.1399)
,('Lyon', 45.7600, 4.8400)
,('Madrid', 40.4168, -3.7038)
,('Marseille', 43.2965, 5.3698)
,('Milan', 45.4642, 9.1900)
,('Munich', 48.1351, 11.5820)
,('Paris', 48.8566, 2.3522)
,('Prague', 50.0755, 14.4378)
,('Rome', 41.9028, 12.4964)
,('Vienna', 48.2082, 16.3738);
GONow, we need to enter our EDGES data. I will use the stored procedure because it is important to ensure that the connections between the cities are not only in one direction. The stored procedure requires the node from, node to, an indication if it is one-way, and if you intend to delete the edge.
EXECUTE [dbo].[uspGraphEdges] 'Lisbon','Madrid',638,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Madrid','Lyon',1272,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Madrid','Marseille',1143,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Madrid','Paris',1268,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Paris','Brussels',294,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Paris','Frankfurt',592,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Brussels','Frankfurt',409,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Lyon','Geneva',162,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Marseille','Milan',587,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Milan','Rome',681,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Milan','Munich',551,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Geneva','Paris',546,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Geneva','Milan',412,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Geneva','Frankfurt',585,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Frankfurt','Munich',383,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Frankfurt','Berlin',570,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Frankfurt','Prague',552,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Berlin','Prague',354,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Munich','Prague',363,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Munich','Vienna',458,0,0;
EXECUTE [dbo].[uspGraphEdges] 'Vienna','Prague',312,0,0;
GOFor example, what is the best way to send an item from ROME to LISBON using all algorithms?
EXECUTE [dbo].[uspGraphAstar] 'Rome','Lisbon',1;
EXECUTE [dbo].[uspGraphDijkstra] 'Rome';
EXECUTE [dbo].[uspGraphBellmanFord] 'Rome';
EXECUTE [dbo].[uspGraphFloydWarshall];
What about from BERLIN to MADRID?
EXECUTE [dbo].[uspGraphAstar] 'Berlin','Madrid',1;
Next Steps
- WIKIPEDIA – Graph theory
- MICROSOFT – SQL Graph Overview
- WIKIPEDIA – A-star algorithm
- WIKIPEDIA – Bellman-Ford algorithm
- WIKIPEDIA – Dijkstra´s algorithm
- WIKIPEDIA – Floyd-Warshall algorithm
Sebastião Pereira has over 40 years of experience in database development including T-SQL, algorithm design, machine learning and bringing innovative mathematical formulas to SQL Server. He started his career at a transnational fast-moving consumer goods (FMCG) company as an employee then later transitioning into a consultant role. He eventually founded his own company to develop software solutions for the healthcare industry. Sebastião is a respected award-winning author on MSSQLTips.com extending SQL Server capabilities beyond traditional workloads.
- MSSQLTips Awards
- Author of the Year – 2025
- Trendsetter (25+ tips) – 2025
- Rookie of the Year – 2024
I have always wondered how this was done. Your example assumes a straight line between the start and end points. Could you do a follow-up on this showing how to handle non-straight lines? For example, I live in Houston, TX and want to drive to an address in San Antonia, TX. How would we handle the turns getting out of my neighborhood and onto the freeway, then off the freeway and through the neighborhoods to the destination?
Hello Chuck, to obtain what you want it is necessary to treat all streets and intersections like points on a giant map made of dot and lines, including directions. It is the same as I did linking cities but now linking streets, much more detailed. Then you can apply the Dijkstra’s Algorithm to find the shortest path to where you want to go. My very best regards!
Hi Sebastião,
thanx for the interesting article.
Why do not use the SQL Server Graph tables ?
Hello Oleg, normally Graph tables in SQL is used to complex many-to-many relationships, like in social networks. Graph tables are powerful, but they take time to learn and aren’t as straightforward as regular SQL tables. Regards, Sebastião