SQLite Forum

Recursive query to find the shortest path
Login
Hi,

    I have written the following query to find the shortest path between two points in a travel log (table trip contains a bunch of trips between different points, and nodes and edges are created from this table).  I am able to run this with the LIMIT 1000 or LIMIT 10000 line to stop the recursion, but what I would really like to do is make sure that once I find a path from the origin to the destination, I cut off any path that is longer than the path I have already found (because there is no chance that will be shortest path since all the distances are positive).  But when I try to create another WHERE condition that refers to ShortestPath (commented out in the code below), I get an error about multiple references to the recursive query.

    What is the correct way to get this done?  As you can tell, I am somewhat new to recursive queries and I have gone through the examples on the SQLite site (which is how I managed to get at least as far as I have managed to, so thank you very much for the effort that went into putting that very informative page together), but this has stumped me. Thank you.

<code>
WITH RECURSIVE OD (
    Origin,
    Destination
)
AS (
    VALUES (
        'Some City',
        'Some Other City'
    )
),
edges (
    startpoint,
    endpoint,
    distance
)
AS (
    SELECT Places1.PlaceName AS startpoint,
           Places2.PlaceName AS endpoint,
           min(distance) AS distance
      FROM trip
           INNER JOIN
           Place Places1 ON Places1.PlaceID = trip.Origin
           INNER JOIN
           Place Places2 ON Places2.PlaceID = trip.Destination
     GROUP BY startpoint,
              endpoint
),
ShortestPath (
    O,
    D,
    OtoD,
    ShortestDistance
)
AS (
    SELECT OD.origin AS O,
           edges.endpoint AS D,
           OD.origin || '-' AS OtoD,
           edges.Distance AS ShortestDistance
      FROM edges
           INNER JOIN
           OD ON edges.startpoint = OD.Origin
    UNION ALL
    SELECT ShortestPath.O AS O,
           edges.endpoint AS D,
           ShortestPath.OtoD || ShortestPath.D || '-' AS OtoD,
           ShortestPath.ShortestDistance + edges.distance AS ShortestDistance
      FROM ShortestPath
           INNER JOIN
           edges ON ShortestPath.D = edges.startpoint
     WHERE instr(OtoD, edges.endpoint) = 0
/*           and ShortestDistance <= (select min(ShortestDistance)
       FROM ShortestPath 
       INNER JOIN
       OD ON ShortestPath.O = OD.origin AND 
             ShortestPath.D = OD.destination)*/
     limit 10000
)
SELECT O,
       OtoD || D as Path,
       D,
       ShortestDistance
  FROM ShortestPath 
       INNER JOIN
       OD ON ShortestPath.O = OD.origin AND 
             ShortestPath.D = OD.destination
 ORDER BY ShortestDistance
 Limit 1;
 </code>