专栏首页SQL实现SQL 求最短路径

SQL 求最短路径

研究过算法的朋友,应该都遇到过最短路径求值的问题。简单来说,就是从出发地到目的地有多条路线可走,要求使用算法找出最短路径。

如果使用的是 SQL ,怎么解决这类问题?

接着往下看,很快就有答案了。

先看示例表,dist 存储了目的地到出发地的距离,我们要计算出从 a 地出发到其它地点的最短距离

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

由于要穷举所有可能的路线,因此使用递归是最简单的解决方案。在 SQL 中用递归请参考——SQL 的递归表达式

在递归表达式中,初始的数据应该是列举出能从 a 点直接到达的地点及相应的距离,目前有 a -> b、a -> c 这两条路线。

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

字段 path 记录了从 a 点出发到其它地点的距离。

对于 a 点不能直接到达的地点,可通过直接到达的点再转到目的地。比如,从 a -> d 的路线就有 a -> b -> d 和 a -> c -> d 两条。

通过下面的 SQL 可穷举出所有路线:

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)
    
SELECT * FROM t

对于 “a -> b” 这条路线而言,b 是 a 要到达的目的地。假如这条路线加入了 d ,变成 “a -> b -> d”,那么 b 就成了到达 d 前的出发点。

在 SQL 中加入了条件 INSTR(t.path, b.ep) <= 0 , 主要是防止有环路而出现死循环。不过,在我们的数据中没有环路,不加这个条件也没有任何问题。

上面 SQL 的输出 >>>

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  

从 a 出发到其它地点有可能存在多条路线,如果我们只要找出最短路线的距离,SQL 可以这么写:

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

最好是能把最短距离对应的路线也给展示出来,稍微做一点调整。完整的 SQL 如下:

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 

最终的结果 >>>

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

本文分享自微信公众号 - SQL实现(gh_684ee9235a26),作者:SQL 后花园

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最短路径(一)——多源最短路径

    引出问题:多源最短路径的问题 暑假,小文准备去一些城市旅游。为了节省经费以及方便计划旅程,小文希望知道任意两个城市之间的最短路径。假如有四个城市八条公路。 我们...

    深度学习思考者
  • Dijkstra算法求单源最短路径

    在一个连通图中,从一个顶点到另一个顶点间可能存在多条路径,而每条路径的边数并不一定相同。如果是一个带权图,那么路径长度为路径上各边的权值的总和。两个顶点间路径长...

    Dabelv
  • Dijkstra算法求图中最短路径

    在此借用上一篇文章[深度优先搜索(DFS)两点之间的可行路径](深度优先搜索(DFS)两点之间的可行路径)中的例子:

    带萝卜
  • Floyd是咋求图的最短路径?

    在图论中,在寻路最短路径中除了Dijkstra算法以外,还有Floyd算法也是非常经典,然而两种算法还是有区别的,Floyd主要计算多源最短路径。

    bigsai
  • 7.6 最短路径

    1、假若要在计算机上建立一个交通资讯系统则可以采用图的结构来表示实际的交通网络。

    小林C语言
  • 7.6 最短路径

    2、考虑到交通图的有向行(如航运,逆水和顺水时的船速就不一样)带权有向图中,称路径上的第一个顶点为源点,最后一个顶点为终点。

    小林C语言
  • Asynchronous dynamic programming (ASYNCHDP) 算法求最短路径

    如果节点$x$位于$s$到$t$的最短路径上,那么$x$到$t$的路径也必须是$x$和$t$之间的最短路径。这种“分而治之”(devide-and-conque...

    mwangblog
  • 最短路径生成树计数+最短路径生成树

    最短路径生成树计数。 我们应该先明白什么是最短路径生成树,不会戳这里。 计数方法明显是要使用乘法原理计数,也就是说我们可以得出每一步的方案数再乘进答案中。

    风骨散人Chiam
  • 最短路径问题

    第一题:求不重复路径的个数 How many possible unique paths are there A robot is located at th...

    程序员小王
  • 单源最短路径

     单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。 一.最短路径的最优...

    用户1154259
  • C++构造无向图&求最短路径源码

    用vector<edge> es[MAX]表示点,每个点队列里放着点的相邻边和到边的距离。 以下源码经过测试可运行 #include <iostream> #i...

    kalifa_lau
  • 图论--最短路径生成树(求最小边权和)

    风骨散人Chiam
  • 2602 最短路径问题

    题目描述 Description 平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个...

    attack
  • 最短路径算法java

    上次写的博客,自己发现存在着一个比较大的问题,讲解的没有透彻。 还是举昨天的Dijkstra算法来讲吧。 昨天讲到是每一个循环找出一个点,花式这么说,但是后...

    萌萌哒的瓤瓤
  • 最短路径-Dijkstra算法

    Dijkstra算法,又称"迪杰斯特拉算法",是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层...

    仙士可
  • acm-最短路径算法

    能力有限,只是研究了两种fioyd和Dijkstra算法,还有一个BellmanFord得下次接触了,

    我在鹅厂做安全
  • [图]最短路径-Floyd算法

    <!--more--> > Floyd算法(Floyd-Warshall algorithm)又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之...

    王荣胜
  • [图]最短路径-Dijkstra算法

    2.BFS可能会是Dijkstra算法的实质,BFS使用的是队列进行操作,而Dijkstra采用的是优先队列。

    王荣胜
  • 迷宫的最短路径

    题意:给定一个大小为N * M的迷宫,迷宫由通道与墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需要的最下步数。

    杨鹏伟

扫码关注云+社区

领取腾讯云代金券