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