SQL-图，树，层次结构和递归查询(2)

来源：未知责任编辑：责任编辑发表时间:2015-09-17 09:42　点击:次

Select * from SubsCTE where cycle=1;--仅返回有循环的路径行

案例五：无向图返回最短路径，以道路系统为例

Roads表结构：City1, City2, Distance(距离)--表示城市1与城市2的距离

思路：先将无向道路图转换成有向图，将一行变成两行，再递归查询所有从出发城市能够到达的城市路径和距离，查询过程中为避免死循环，应对循环做出判断，当路径包含子路径时即不再循环，再按照出发城市，到达城市进行分组，获取最小路径，最后再选择出所有出发城市，到达城市和最短路径。

With Roads2

(

--将无向图变为有向图，每行产生两行

Select city1 as From_City, city as To_City, distance from dbo.Roads

Union all

Select city2, city1, distance from dbo.Roads

RoadsPath as

(

--先选择所有出发和到达城市

Select from_city, to_city, distance,

Cast('.' + from_city +'.' + to_City +'.' as varchar(max)) as Path

From Roads2

Union all

--再递归执行已到达城市所能到达的后续城市

Select F.from_city, T.to_city, F.distance + T.distance,

Cast(F.path +T.to_city +'.' as varchar(max)) as Path

From RoadPaths as F

Join Roads2 as T

--递归死循环判断，当父级路径已经包含能到达的城市时，不再进行递归循环

On (Case When F.path like '%.' + T.to_city +'.%' then 1 else o end)=0

And F.to_city = T.from_city www.2cto.com

RoadsMinDist --用于选取出最短路径

(

Select from_city, to_city, Min(distance) as minDist

From RoadPaths

Group by from_city, to_city

)

Select RP.*

From RoadMinDist as RMD

Inner join RoadPaths as RP

On RMD.from_city = RP.from_city

And RMD.to_city = RP.to_city

And RMD.MinDist= RP.distance

作者 Chao Hong