SQLite Forum

Recursive query to find the shortest path
Login

Recursive query to find the shortest path

(1) By Balaji Ramanathan (balaji) on 2021-05-01 17:31:57 [link] [source]

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.

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;

(2) By Balaji Ramanathan (balaji) on 2021-05-01 22:34:49 in reply to 1 [link] [source]

This is a very curious observation, but I thought I would post it here hoping that I can learn something from this. The final query (the actual SELECT) in the code above is:

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;

I realized that the first join condition is not needed because all the paths start from the specified origin anyways. So, I got rid of that, and made my final select as below:

SELECT O, OtoD || D as Path, D, ShortestDistance FROM ShortestPath INNER JOIN OD ON ShortestPath.D = OD.destination ORDER BY ShortestDistance Limit 1;

Surprise, surprise! The query takes 3 times as long to complete after this change. I am at a loss to find any reason why removing a useless, redundant join condition would cause a query to take longer, and that too significantly longer. I increased the limit in the recursive part fo 500000 for the tests, and instead of taking about 9 seconds to run, the query takes 25 seconds to run without the useless join condition. I ran the tests a dozen tests to make sure I was not seeing the effect of some system lag on my computer or something like that.

If somebody can provide me a plausible reason why asking SQLite to do extra, useless stuff enables it to accomplish a task 3 times faster, I am all ears! Thank you.

(3) By Keith Medcalf (kmedcalf) on 2021-05-01 23:34:35 in reply to 2 [link] [source]

EXPLAIN QUERY PLAN (.eqp on) and EXPLAIN (.eqp full) may shed light.

(4) By Balaji Ramanathan (balaji) on 2021-05-02 20:39:54 in reply to 1 [link] [source]

So, is there no clean way to find the shortest path more reliably than by setting a high enough limit in the recursive query and hoping for the best? I found a 12-step shortest path between two places using 500000 as the limit (takes about 10 seconds to run), and the previous best was a 10-step solution that about 1000 miles longer when I set the limit at 250000. I really don't want to just experiment with the limit when I know that the correct way to find the shortest path is to prune branches based on what I have already found. Thank you.

(5) By Keith Medcalf (kmedcalf) on 2021-05-03 02:30:01 in reply to 4 [link] [source]

That is correct. A recursive query is an exhaustive search and barring artificial restrictions (such as LIMIT) will only exit once the recursion is exhausted. Unlike programmatic recursion, there is no way to "prune" branches based on what you have already found.

In other words, if you take, for example, map routing software searching for a route from point A to point B. The correct approach is not to LIMIT the number of steps in the recursion but to prohibit further searching of branches that are "too long", where you compute "too long" before asking the question. It may be, for example, that your search defines "too long" as a path distance more than X times the "as the crow flies" distance between point A and point B. If this does not generate a useful answer, then increase X. Lather rinse and repeat until an acceptable solution is found (or the search has taken so long in elapsed time that you can declare that you cannot get there from here).

(7) By Balaji Ramanathan (balaji) on 2021-05-03 13:43:11 in reply to 5 [link] [source]

OK, that is disappointing, but at least, it looks like I am not missing anything. Thank you, Keith.

(6) By anonymous on 2021-05-03 13:41:41 in reply to 1 [link] [source]

Perhaps this helps? https://github.com/abetlen/sqlite3-bfsvtab-ext

(8) By Balaji Ramanathan (balaji) on 2021-05-04 13:07:24 in reply to 6 [link] [source]

Thanks, that looks very interesting. I will take a look.

(9) By J-L Hainaut (JLHainaut) on 2021-05-05 15:45:41 in reply to 8 [link] [source]

You could also be interested by this reference:

https://staff.info.unamur.be/dbm/Documents/Tutorials/SQLfast/SQLfast-Case31-Shortest-path.pdf

It doesn't use recursive CTE's but a simple loop that implements Dijkstra's algorithm (complexity O(NlogN)) working on an SQLite database.

(10) By Balaji Ramanathan (balaji) on 2021-05-07 04:04:20 in reply to 9 [link] [source]

Thank you. Obviously, with looping, it is trivial to find the shortest path. You don't even need SQL to do it at all. I was hoping that there was some way to do something similar to dyjkstra's algorithm using a recursive query in SQL. Without the ability to do branch pruning, recursive CTE's are a lot less useful than I had thought they would be.

(11) By Keith Medcalf (kmedcalf) on 2021-05-07 04:56:36 in reply to 10 [link] [source]

-- see https://learnsql.com/blog/get-to-know-the-power-of-sql-recursive-queries/

create table edges
(
    fromNode    integer not null,
    toNode      integer not null,
    distance    real    not null default 1,
    speed       real    not null default 1,
    primary key (fromNode, toNode)
) without rowid;

insert into edges(fromNode, toNode, distance, speed) values
    (1, 2, 100,  40),
    (1, 3,  70,  50),
    (2, 3,  20,  40),
    (3, 2,  20,  40),
    (3, 4,  40,  50),
    (2, 5,  30,  50),
    (4, 5,  20,  40),
    (5, 6,  20,  20),
    (4, 6,  80, 100);

.parameter init
.parameter set :start 1
.parameter set :end 6
.parameter set :maxHops 10
.parameter set :maxCost 10
.parameter set :maxDistance 250

with paths (startAt, endAt, visited, hops, pathDistance, pathCost)
  as (
         select :start                      as startAt,
                :start                      as endAt,
                '/' || :start || '/'        as visited,
                0                           as hops,
                0                           as pathDistance,
                0                           as pathCost
      union all
         select startAt                     as startAt,
                toNode                      as endAt,
                visited || toNode || '/'    as visited,
                hops + 1                    as hops,
                pathDistance + distance     as pathDistance,
                pathCost + distance / speed as pathCost
           from paths, edges
          where fromNode == endAt
            and instr(visited, '/' || toNode || '/') == 0
            and instr(visited, '/' || :end || '/') == 0
            and hops < :maxHops
            and pathCost < :maxCost
            and pathDistance < :maxDistance
       order by pathCost
    )
select startAt, endAt, visited, hops, pathDistance, pathCost
  from paths
 where startAt == :start
   and endAt == :end
;

The ORDER BY in the recursive part selects which paths to open first.

(12) By J-L Hainaut (JLHainaut) on 2021-05-07 15:11:47 in reply to 10 [link] [source]

You are right, finding the shortest path through the brute force method (depth-first graph traversal while avoiding circuits) is easy to express with a CTE but implementing Dijkstra's algorithm is far less trivial. The main obstacle is that the current resultset of a CTE (the set of rows already computed) is "append only": one can augment it through the recursive member of the CTE but there is no way to delete or update its rows.

Personally, I'm (almost) sure that it is possible to design a CTE that simulates 'delete' and 'update' operations, for example by adding a 'version' attribute to its rows, and by selecting their last version, just like in a historical database. But I guess that the expression would be particularly complex, not to mention poorer performance. Sometimes, a carefully crafted procedural solution can be clearer and faster that its equivalent declarative expression !

As to your observation "You don't even need SQL to do it at all.", you also are right. Anyway, it's even possible to solve the shortest path problem through a Turing machine ;).

(13) By Balaji Ramanathan (balaji) on 2021-05-11 23:20:59 in reply to 12 [source]

Actually, I am not looking to update the records already created or delete any of them, I am just looking for a way to control what gets added to the resultset based on the current contents of the resultset, but currently, it looks like even that is not possible with a recursive CTE. You can only control what gets added using global criteria that have to be decided upon a priori. Somewhat disappointing, but I learned something important about recursive CTE's that was not obvious in the documentation. Thank you to everyone on this forum who contributed to this learning.