# SQL shortest path

2021-01-05 19:41:37

Friends who have studied algorithms , We should have encountered the shortest path evaluation problem . Simply speaking , There are many routes from the starting point to the destination , Algorithm is required to find the shortest path .

If you are using SQL , How to solve this kind of problem ？

So let's look down , Soon there will be an answer .

Let's look at the sample table first ,dist It stores the distance from the destination to the destination , We want to Calculate from a The shortest distance from ground to other places .

```sp      ep      distance
------  ------  ----------
a       b                5
a       c                1
b       c                2
b       d                1
c       d                4
c       e                8
d       e                3
d       f                6```

Because we have to enumerate all possible routes , So using recursion is the easiest solution . stay SQL Please refer to ——SQL The recursive expression of .

In recursive expressions , The initial data should be a list that can be derived from a The point directly to the location and the corresponding distance , There are a -> b、a -> c These two routes .

```SELECT
*,
CAST(CONCAT(a.sp, ' -> ', a.ep) AS CHAR(100)) AS path
FROM
dist a
WHERE sp = 'a' ```

Field path Recorded from a The distance from the point of departure to other places .

about a A point that cannot be reached directly , You can go to your destination through a point you reach directly . such as , from a -> d The route is a -> b -> d and a -> c -> d Two article .

Through the following SQL But list all the routes ：

```WITH RECURSIVE t (sp, ep, distance, path) AS
(SELECT
*,
CAST(CONCAT(a.sp, ' -> ', a.ep) AS CHAR(100)) AS path
FROM
dist a
WHERE sp = 'a'
UNION ALL
SELECT
t.sp,
b.ep,--  The destination of the current route is the starting point of the next destination
t.distance + b.distance,--  The sum of the distances of the current route
CAST(
CONCAT(t.path, ' -> ', b.ep) AS CHAR(100)
) AS path
FROM
t
INNER JOIN dist b
ON b.sp = t.ep
AND INSTR(t.path, b.ep) <= 0)

SELECT * FROM t```

about “a -> b” For this route ,b yes a The destination to be reached . If this route adds d , become “a -> b -> d”, that b It's arrival d The starting point before .

stay SQL Added conditions to `INSTR(t.path, b.ep) <= 0` , It is mainly to prevent the loop from appearing the dead loop . however , There is no loop in our data , There is no problem without this condition .

above SQL Output >>>

```sp      ep      distance  path
------  ------  --------  ----------------------
a       b              5  a -> b
a       c              1  a -> c
a       c              7  a -> b -> c
a       d              6  a -> b -> d
a       d              5  a -> c -> d
a       e              9  a -> c -> e
a       d             11  a -> b -> c -> d
a       e             15  a -> b -> c -> e
a       e              8  a -> c -> d -> e
a       e              9  a -> b -> d -> e
a       f             11  a -> c -> d -> f
a       f             12  a -> b -> d -> f
a       e             14  a -> b -> c -> d -> e
a       f             17  a -> b -> c -> d -> f  ```

from a There may be multiple routes to other places , If we just want to find the shortest distance ,SQL It can be written like this ：

```SELECT
sp,
ep,
MIN(distance) AS distance
FROM
t
GROUP BY sp,
ep;

sp      ep      distance
------  ------  ----------
a       b                5
a       c                1
a       d                5
a       e                8
a       f               11```

It's better to show the route corresponding to the shortest distance , A little bit of adjustment . complete SQL as follows ：

```WITH RECURSIVE t (sp, ep, distance, path) AS
(SELECT
*,
CAST(CONCAT(a.sp, ' -> ', a.ep) AS CHAR(100)) AS path
FROM
dist a
WHERE sp = 'a'
UNION ALL
SELECT
t.sp,
b.ep,
t.distance + b.distance,
CAST(
CONCAT(t.path, ' -> ', b.ep) AS CHAR(100)
) AS path
FROM
t
INNER JOIN dist b
ON b.sp = t.ep
AND INSTR(t.path, b.ep) <= 0),
t1 AS
(SELECT
*,
row_number () over (
PARTITION BY sp,
ep
ORDER BY distance
) AS rn
FROM
t)

SELECT
sp,
ep,
path,
distance
FROM
t1
WHERE rn = 1 ```

Final result >>>

```sp      ep      path             distance
------  ------  ---------------  ----------
a       b       a -> b                     5
a       c       a -> c                     1
a       d       a -> c -> d                5
a       e       a -> c -> d -> e           8
a       f       a -> c -> d -> f          11```

The source and reprint of the original text are detailed in the text , If there is any infringement , Please contact the yunjia_community@tencent.com Delete .

Original publication time ： 2020-12-19

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

https://chowdera.com/2021/01/20210102191429107j.html