当前位置:网站首页>SQL shortest path

SQL shortest path

2021-01-05 19:41:37 Daydreamer

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

This article is from WeChat official account. - SQL Realization (gh_684ee9235a26) , author :SQL Back garden

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 .

版权声明
本文为[Daydreamer]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/01/20210102191429107j.html

随机推荐