using STDistance in SQL server to find shortest path in graph

Question

I have a table which contain information about edges of the graph in form of geometry linestring. Spatial result of query select * from edge look like this EACH linestring is created always from two geometry points with insert statement like:

INSERT INTO edge VALUES( geometry::Parse('LINESTRING(1 1 ,1 2)'))

In order to finding shortest path between two points I have implemented Dijkstra algorith according to Dijkstra in c#, However I have found out about STDistance() function which is ment to do the same thing just by executing simple query. Could anyone give me a hint how could I use STDistance with objects created like I described? Every example I find use linestrings created from 3 points.

I have difficulty using example in the situation I have lets say 3 linestrings as bellow:

INSERT INTO edge VALUES( geometry::Parse('LINESTRING(1 1 ,1 2)'))
INSERT INTO edge VALUES( geometry::Parse('LINESTRING(1 2 ,1 3)'))
INSERT INTO edge VALUES( geometry::Parse('LINESTRING(1 3 ,1 4)'))

and finding shortest path from 1 1 to 1 4

Edit: I have suceeded with combining all linestrings into one shape by:

SELECT geometry::UnionAggregate(linestring) FROM edge

i get shape :

0x000000000104160000002242C0E56A32834050D72864D98D714000000000003082400000000000B0784000000000000071400000000000A075402242C0E56A32834050D72864D98D7140CFB591AC8CBA83402B7FD245B3976B400000000000F087400000000000806F402242C0E56A32834050D72864D98D7140CFB591AC8CBA83402B7FD245B3976B40000000000000854000000000004053400000000000E06940000000000080504000000000009076400000000000C06340F89FD09A6BDC8140A4AC72B9CEDB69404AAD03D8122784408FC4879BE4996540CFB591AC8CBA83402B7FD245B3976B40F89FD09A6BDC8140A4AC72B9CEDB694000000000000071400000000000A075400000000000E06940000000000080504000000000001073400000000000C05E4000000000009076400000000000C06340000000000000854000000000004053404AAD03D8122784408FC4879BE49965400000000000688B40000000000040504004000000010000000001040000000108000000010A00000005000000FFFFFFFF0000000005000000000000000002000000000100000002000000000200000002000000000300000002

Now I use STDistance as follows:

SELECT (geometry::UnionAggregate(linestring)).STDistance(geometry::STGeomFromText('POINT(0 0)', 0)) FROM edge

However the return value is about distance between point (0,0) and presented shape, when my intend is to count edges length from one point to the other, any clues?

Answer 1

Code Kata. As others have said in comments STDistance will give you the minimum straight line distance between two geometry objects, not a path through a graph. Implementing Dijkstra in Sql is beyond me, but the brute force method is acceptable for small numbers of nodes such as you've demonstrated. This code calculates all paths within the graph from A to B and then selects the shortest.

Please note that this is a only a proof that it can be done, not a recommendation that it should be done. Your existing code in c# is probably simpler and quicker.

Thanks for giving me an opportunity to learn about geometry functions in sql server.

-- Declare and set parameters.
DECLARE @start geometry, @end geometry

SET @start = geometry::STGeomFromText('POINT(-1 1)', 0);
SET @end = geometry::STGeomFromText('POINT(1 3)', 0);

-- Caching of ST function results and for reversibility.
DECLARE @segments TABLE  (
edge geometry,
start_point geometry,
end_point geometry,
[weight] float
)
INSERT @segments
        ( edge, start_point, end_point, [weight])
SELECT e, e.STStartPoint(), e.STEndPoint(),  e.STLength() FROM edge UNION ALL 
-- Can traverse edges both ways unless we're in a directed graph?
SELECT e, e.STEndPoint(), e.STStartPoint(),  e.STLength() FROM edge 

-- We need to know number of edges for some bookkeeping later.
DECLARE @total_edges INT
SELECT @total_edges = COUNT(*) FROM edge;

-- Meat of the procedure. Find all sensible paths from @start to @end allowed by the graph, using a recursive common table expression.
WITH cte (path, start_point, end_point, [weight], segments_traversed) AS (
SELECT 
    edge AS path,
    start_point, 
    end_point, 
    [weight] ,
    1 AS segments_traversed
FROM 
    @segments 
WHERE 
    @start.STEquals(start_point) = 1 UNION ALL 
SELECT 
    c.path.STUnion(s.edge) AS PATH,
    s.start_point, 
    s.end_point, 
    s.[weight] + c.[weight] AS weight,
    c.segments_traversed + 1 AS segments_traversed
FROM cte c 
    INNER JOIN @segments s ON 
        -- next edge must start where this one ended.
        s.start_point.STEquals(c.end_point) = 1 AND 
        -- terminate paths that hit the endpoint.
        c.start_point.STEquals(@end) = 0 AND
        -- if we traveled more than the number of edges there's surely a better path that doesn't loop!    
        -- also acts as a guarantee of termination.  
        c.segments_traversed < @total_edges
)
SELECT TOP 1
    path 
FROM 
    cte c
WHERE 
    -- Restrict to paths ending at end point.
    c.end_point.STEquals(@end) = 1
ORDER BY 
    weight ASC