30 thoughts on “How to get shortest connection between two cities”

1. Could you share the TTR route data for testing? I suspect your problem is that you used “UNION ALL” instead of “UNION” in your recursive query. But I’m too lazy to enter all that data by hand. 🙂

2. https://www.depesz.com/wp-content/uploads/2012/06/ttr.dump.gz

3. Isn’t ðis easier & faster wiþ recursive WITH queries?

4. @Leonadro:
   did you read the blogpost?
   I wrote, at least twice, that I tried, but couldn’t make it. If you can provide such query – I will gladly see/review it.

5. Hell,

   You will find a query implementing such thing with WITH RECURSIVE in the .zip file available here: http://www.postgresql-sessions.org/_media/requetes_sessions_postgresql.zip

   It was done by my ex-coworker Jean-Michel Souchard.

6. Hello… sorry for the typo…

7. @Thomas:

   downloaded, and grep’ped for RECURSIVE – but it’s not in english, so I can’t really find out which of the queries you have in mind.

8. There’s a SQL file with Dijkstra in its filename 😉

9. Hmm. Indeed, after working over this, there’s no way to do it with recursive queries. The problem is that the key piece of information that lets you cut you search short is knowing the best currently-known length for a given route. And that sort of information simply isn’t available via WITH RECURSIVE, since that mechanism works purely iteratively based on either UNION or UNION ALL.

   Interestingly, you *can* use the same iterative technique to solve the problem directly, much like you might have done before WITH RECURSIVE to generate transitive closures:

   create temporary table full_routes (
   from_city text, to_city text, length numeric, path text[]
   );

   — base case

   insert into full_routes
   select r.from_city, r.to_city, r.length, array [ r.from_city, r.to_city ]
   from all_routes r;

   — repeat the following two steps until insertion inserts zero rows

   — add new routes only if they are shorter than the current route
   insert into full_routes
   select f.from_city, r.to_city, f.length + r.length, f.path || r.to_city
   from all_routes r, full_routes f
   where r.from_city = f.to_city
   and r.to_city all ( f.path )
   and f.length + r.length (select min(f2.length) from full_routes f2
   where f.from_city = f2.from_city
   and f.to_city = f2.to_city);

   This method *is* able to use the length to decide when to stop, and therefore generates many many less possible routes than recursive method, which must keep going and going, generating many billions of paths and running out of memory. (There are only 1616 shortest paths between cities, counting both directions of each route, but you can easily demonstrate that the recursive query generates at least millions by running the query with progressively higher LIMIT clauses.)

   I’m rather sad to see that WITH RECURSIVE can’t be used to run something as simple as a depth-first search with weighted edges. I hadn’t realized it was that limited. But, at least it does take care of some basic graph problems.

10. After puzzling over the link from Mr. Reiss: This file appears to implement exactly the same method that is included in the blog post above, and on a sufficiently connected graph it would fail the same way. It must enumerate every possible path through the graph before eliminating any.

11. @Thomas:
    Got your translation in mail – still – the query uses columns which I don’t quite understand (cp_deb/cp_fin).

    Plus – this is *very* slow. For the 12 edges it has it takes over 2ms to calculate on my machine.

    Maybe I’m doing something wrong – but can you try to modify the query, and run it on my dataset (it’s linked in a comment) to try to find the routes Duluth-Toronto and Vancouver-Miami?

12. @Thomas:

    re the comment from J. Prevost – are you sure this is different approach? If what J. Prevost wrote is true – well, I did it, and it works, but it’s too slow for any use.

    The major problem is that there is no logic to prune obviously wrong routes.

13. I think the cp_deb and cp_fin are simply secondary parts of the keys for locations. The point of departure and the destination are specified by (ville_deb, cp_deb) and (ville_fin, cp_fin), respectively.

14. Hi Depesz,

    I often read your blog and I had a little think about this. I’m not very experienced with CTEs/Window functions let alone the recursive form, but after loading your generously keyed data, I came up with this (seems quick to me)

    WITH RECURSIVE
    findpath AS (
      SELECT 'Vancouver'::text AS from_city, 'Miami'::text AS to_city
    ),
    multiroutes AS (
      SELECT
        m.from_city,
        m.to_city,
        ARRAY[m.from_city, m.to_city] AS full_route,
        LENGTH AS total_length,
        m.to_city = f.to_city AS solved,
        MIN(CASE WHEN m.to_city = f.to_city THEN LENGTH ELSE NULL END) OVER () AS min_solve
      FROM findpath f
      JOIN all_routes m USING (from_city)
      UNION ALL
      SELECT
        m.from_city,
        n.to_city,
        m.full_route || n.to_city,
        m.total_length + n.length,
        n.to_city = f.to_city AS solved,
        MIN(CASE WHEN n.to_city = f.to_city THEN m.total_length + n.length ELSE NULL END) OVER () AS min_solve
      FROM findpath f
      JOIN multiroutes m USING (from_city)
      JOIN all_routes n ON m.to_city = n.from_city AND NOT m.solved AND n.to_city <> ALL( m.full_route) AND (m.min_solve IS NULL OR m.min_solve IS NOT NULL AND m.total_length + n.length <= m.min_solve)
    ),
    solution AS (
      SELECT
        m.from_city,
        m.to_city,
        m.full_route,
        m.total_length,
    	MIN(m.total_length) OVER () AS best_length
      FROM multiroutes m JOIN findpath f USING (to_city)
    )
    SELECT * FROM solution WHERE total_length = best_length;

    I'm using:
    PostgreSQL 9.1.4 on x86_64-unknown-linux-gnu, compiled by gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3, 64-bit

15. Seems it removed my from between n.to_city and ALL

16. Great post!

    PS Hubert, which SQL highlighter do you use for your posts?

17. @Pavel:
    WP-Syntax plugin. It uses GeSHi, afaik.

18. @Mark:
    Is there a (not equal to) missing between “n.to_city” and “ALL( m.full_route)” in your query? I added it and then it works. Where should the “from between n.to_city and ALL” be inserted? That’s not valid syntax either, perhaps it removed some characters in your comment?

    Your query takes 2264ms while Depesz function for the same route takes 71ms, not that fast, but it works.

19. Have you tried pgRouting? It has shortest path and traveling salesman.

20. @Stephen Mather:
    pgRouting relies on C functions, the implementation is not in SQL or PL/pgSQL.

21. Hi Depesz,

    Apparently I was trying an approach very similar to yours. Even without having a sub-query to get the best distance so far, this is still useful since it prunes all the edges after the destination is matched.

    with recursive t(src, dest, edge, route, distance, best_distance)
    as
    (
    — Source city, Target City, Current City (initially the Source City), Cumulative route (initially only Source City), Cumulative Distance, Best Distance
    select ‘a’, ‘e’, ‘a’, ‘{“a”}’::text[], 0, 2147483647
    union all
    select t.src, t.dest, r.city2, route || array[r.city2], t.distance + r.distance,
    case when t.dest = r.city2 then least(t.distance + r.distance, t.best_distance) else t.best_distance end
    from t
    join test.route2 r on r.city1 = t.edge and not(r.city2 = any(route)) and t.distance + r.distance < best_distance
    )
    select *
    from t
    where t.route[array_upper(t.route, 1)] = 'e' — Compare to Destination City
    order by distance asc
    limit 1;

    Where the data is created using this:

    create table test.route
    (
    city1 text,
    city2 text,
    distance int
    );

    insert into test.route values
    ('a', 'b', 5),
    ('b', 'c', 4),
    ('b', 'h', 2),
    ('c', 'h', 3),
    ('c', 'd', 5),
    ('d', 'e', 3),
    ('e', 'f', 2),
    ('e', 'a', 5),
    ('f', 'g', 1),
    ('f', 'a', 2);

    create view test.route2
    as
    select city1, city2, distance
    from test.route
    union all
    select city2, city1, distance
    from test.route;

22. @Mark:

    ok. got the time to analyze your query.

    It’s really nice, but with larger datasets the performance will degrade.

    Reason is very simple – min_solve doesn’t propagate to next iterations of the recursive query.

    It can be easily visible when you’ll change findpath CTE to be:

    SELECT ‘Helena’::TEXT as from_city, ‘Toronto’::TEXT as to_city

    and then make the final query, instead of querying solution:

    SELECT * FROM multiroutes WHERE 2 = array_upper(full_route, 1) ORDER BY full_route;

    then run the query, increment “2=”, rerun, and so on.

    With 3= – we see that all rows have min_solve = 12.

    with 4= – it correctly finds shorter path – 11 elements.

    but then – 5= min_solve is again null.

    Of course your condition in join in multiroute CTE did excellent job at filtering out paths – so it can actually finish finding even longest paths in my TTR example, but if the map was larger – it would lag pretty badly.

    We can see, that when searching for Duluth-Toronto, final multiroute CTE contains 125 routes.
    On the other hand – my function, for the same path, has at most 13.

    A bit longer trip – Helena-Toronto – your query considers 304 paths, function – 47.

    For the long, cross-continent route – Vancouver-Miami – query considers 27677 routes, function – 243.

    Still – all that aside – I bow before your skill – it is great application of window functions and CTE.

23. @Tzvi:

    I reformatted your query, and modified it so that it works not against your test table, but against the tables that I used in this blogpost:

    WITH recursive t(src, dest, edge, route, LENGTH, best_length)
    AS
    (
        -- Source city, Target City, Current City (initially the Source City), Cumulative route (initially only Source City), Cumulative length, Best length
        SELECT 'Duluth', 'Toronto', 'Duluth', '{Duluth}'::text[], 0, 2147483647
        UNION ALL
        SELECT t.src, t.dest, r.to_city, route || array[r.to_city], t.length + r.length,
            CASE WHEN t.dest = r.to_city THEN least(t.length + r.length, t.best_length) ELSE t.best_length END
        FROM t
            JOIN all_routes r ON r.from_city = t.edge AND NOT(r.to_city = any(route)) AND t.length + r.length < best_length
    )
    SELECT *
    FROM t
    WHERE t.route[array_upper(t.route, 1)] = 'e' -- Compare to Destination City
    ORDER BY LENGTH ASC
    LIMIT 1;

    Result – definitely not good. Started it, and killed after ~ 10 seconds, with no results. Sorry – it might behave nicely when you have 10 routes, but it doesn’t work when you have more.

24. Well, I had a little bit more of a think about it, and whilst not as few paths as the function solution, there is a significant reduction in the search tree.

    WITH RECURSIVE
    findpath AS (
        SELECT 'Vancouver'::text AS from_city, 'Miami'::text AS to_city
    ),
    multiroutes AS (
        SELECT
            m.from_city,
            m.to_city,
            ARRAY[m.from_city, m.to_city] AS full_route,
            LENGTH AS total_length,
            m.to_city = f.to_city AS solved,
            MIN(CASE WHEN m.to_city = f.to_city THEN LENGTH ELSE NULL END) OVER () AS min_solve,
            LENGTH AS best_to_length
        FROM findpath f
            JOIN all_routes m USING (from_city)
        UNION ALL
        SELECT
            m.from_city,
            n.to_city,
            m.full_route || n.to_city,
            m.total_length + n.length,
            n.to_city = f.to_city AS solved,
            MIN(CASE WHEN n.to_city = f.to_city THEN m.total_length + n.length ELSE NULL END) OVER () AS min_solve,
            MIN(m.total_length + n.length) OVER (PARTITION BY n.to_city) AS best_to_length
        FROM findpath f
            JOIN multiroutes m USING (from_city)
            JOIN all_routes n ON m.to_city = n.from_city AND n.to_city <> ALL( m.full_route) AND (m.min_solve IS NULL OR m.min_solve IS NOT NULL AND m.total_length + n.length <= m.min_solve)
        WHERE NOT m.solved
            AND m.total_length = m.best_to_length
    ),
    solution AS (
        SELECT
            m.from_city,
            m.to_city,
            m.full_route,
            m.total_length,
            MIN(m.total_length) OVER () AS best_length
        FROM multiroutes m JOIN findpath f USING (to_city)
    )
    SELECT * FROM solution WHERE total_length = best_length;

    The main difference here is the tracking of the best path length for the to_city in the multiroutes CTE and using that to limit which new paths are added to the search tree. This brings the intermediate search space down to approx 2300 rows instead of the nearly 28000. It also reduced my execution time from 1300ms down to 200ms (warm).

    It has been an interesting exercise in using SQL to solve a problem.

25. @Mark:

    WOW again. This query ran for me, for the Vancouver-Miami route in 21ms (my function needed ~70!). And this is done while still taking into consideration 2282 routes (10 times as many as function).

    But – as good as it is, I think I found a way to make it faster:

    WITH RECURSIVE
    findpath AS (
        SELECT 'Vancouver'::text AS from_city, 'Miami'::text AS to_city
    ),
    multiroutes AS (
        SELECT
            m.from_city,
            m.to_city,
            ARRAY[m.from_city, m.to_city] AS full_route,
            LENGTH AS total_length,
            m.to_city = f.to_city AS solved,
            MIN(CASE WHEN m.to_city = f.to_city THEN LENGTH ELSE NULL END) OVER () AS min_solve,
            LENGTH AS best_to_length
        FROM findpath f
            JOIN all_routes m USING (from_city)
        UNION ALL
        SELECT
            m.from_city,
            n.to_city,
            m.full_route || n.to_city,
            m.total_length + n.length,
            n.to_city = f.to_city AS solved,
            least(
                m.min_solve,
                MIN(CASE WHEN n.to_city = f.to_city THEN m.total_length + n.length ELSE NULL END) OVER ()
            ) AS min_solve,
            MIN(m.total_length + n.length) OVER (PARTITION BY n.to_city) AS best_to_length
        FROM findpath f
            JOIN multiroutes m USING (from_city)
            JOIN all_routes n ON m.to_city = n.from_city AND n.to_city <> ALL( m.full_route) AND (m.min_solve IS NULL OR m.min_solve IS NOT NULL AND m.total_length + n.length <= m.min_solve)
        WHERE NOT m.solved
            AND m.total_length = m.best_to_length
    ),
    solution AS (
        SELECT
            m.from_city,
            m.to_city,
            m.full_route,
            m.total_length,
            MIN(m.total_length) OVER () AS best_length
        FROM multiroutes m JOIN findpath f USING (to_city)
    )
    SELECT * FROM solution WHERE total_length = best_length;

    Took (best result); 9.5ms for Vancouver-Miami, and it considered only 847 routes.

    The difference is usage of least() for calculation of min_solve to prevent reappearance of “null” in min_solve column for next iterations of loop.

26. I always forget about least and greatest 🙂

27. Now how do I get the query code in iterative commits between Mark and Depesz into a github repo (just starting out learning SQL queries, but am familiar with Dikstra’s alg and A*s

    Splendid post and comments

28. I’ll attempt to do justice to the post and the iterative query updates at https://github.com/victusfate/FriendlySQL

29. Ok you can see the relative commits and history of the query here (the diff view was helpful to me since I’m not as quick to notice differences in the text/comments)

    Mark Guyatt’s first version:
    https://github.com/victusfate/FriendlySQL/blob/8b74560661f4ba8efc1ee70d3c7f9e3fd282f1c7/MarkGuyattDepeszShortestPathQuery.sql

    Mark’s second version after Depesz comments:
    https://github.com/victusfate/FriendlySQL/commit/69b3ee56f04fc825d5e6cbbd9adabba23984d1e2

    Depesz updates:
    https://github.com/victusfate/FriendlySQL/commit/abba78b6b42608994383759eb07a06c610b0741d

30. Very cool.

Comments are closed.