求两地最短距离

Question

 
 出发地    目的地     里程    source  direct  Mile
     A        B     20 
    B        C    10 
    C        D    15 
    D        E    10 
    E        F    5 
    D        F    15 
    B        D    20 
    A        E    10 
    A        F    15 请用sql语句写一个算法，算出从A到C的最短距离？ 

Answer 1

---------------------------------
--  Author: liangCK 小梁
---------------------------------
 
--> 生成测试数据: @T
DECLARE @T TABLE ([source] VARCHAR(1),direct VARCHAR(1),Mile INT)
INSERT INTO @T
SELECT 'A','B',20 UNION ALL
SELECT 'B','C',10 UNION ALL
SELECT 'C','D',15 UNION ALL
SELECT 'D','E',10 UNION ALL
SELECT 'E','F',5 UNION ALL
SELECT 'D','F',15 UNION ALL
SELECT 'B','D',20 UNION ALL
SELECT 'A','E',10 UNION ALL
SELECT 'A','F',15--SQL查询如下:;WITH Liang AS
(
    SELECT
        [source] as [from],direct AS [to],Mile
    FROM @T
    UNION ALL
    SELECT
        direct,[source],Mile
    FROM @T
),
Liang2 AS
(
    SELECT
        [from],[to],
        Mile AS totalMile,
        CAST('.'+[from]+'.'+[to]+'.' AS VARCHAR(MAX)) AS path
    FROM Liang
    UNION ALL
    SELECT
        A.[from],B.[to],
        A.totalMile+B.Mile,
        CAST(A.path+B.[to]+'.' AS VARCHAR(MAX))
    FROM Liang2 AS A
        JOIN Liang AS B
            ON CASE WHEN A.path LIKE '%.'+B.[to]+'.%' 
                      THEN 1 ELSE 0 END=0
                AND A.[to]=B.[from]
),
Liang3 AS
(
    SELECT
        [from],[to],
        MIN(totalMile) AS MinMile
    FROM Liang2
    GROUP BY [from],[to]
)
SELECT B.*
FROM Liang3 AS A
   JOIN Liang2 AS B
       ON A.[from]=B.[from]
           AND A.[to]=B.[to]
           AND A.MinMile=B.totalMile
WHERE A.[from]='A'
    AND A.[to]='C'
OPTION(MAXRECURSION 0)
/*
from to    totalMile   path
---- ----  ---------- ----------------------------
A    C     30          .A.B.C.(1 行受影响)*/[/code]

Answer 2

---------------------------------
--  Author: liangCK 小梁
-----------------------------------> 生成测试数据: @T
DECLARE @T TABLE ([source] VARCHAR(1),direct VARCHAR(1),Mile INT)
INSERT INTO @T
SELECT 'A','B',20 UNION ALL
SELECT 'B','C',10 UNION ALL
SELECT 'C','D',15 UNION ALL
SELECT 'D','E',10 UNION ALL
SELECT 'E','F',5 UNION ALL
SELECT 'D','F',15 UNION ALL
SELECT 'B','D',20 UNION ALL
SELECT 'A','E',10 UNION ALL
SELECT 'A','F',15--SQL查询如下:;WITH Liang AS
(
    SELECT
        [source] as [from],direct AS [to],Mile
    FROM @T
    UNION ALL
    SELECT
        direct,[source],Mile
    FROM @T
),
Liang2 AS
(
    SELECT
        [from],[to],
        Mile AS totalMile,
        CAST('.'+[from]+'.'+[to]+'.' AS VARCHAR(MAX)) AS path
    FROM Liang
    UNION ALL
    SELECT
        A.[from],B.[to],
        A.totalMile+B.Mile,
        CAST(A.path+B.[to]+'.' AS VARCHAR(MAX))
    FROM Liang2 AS A
        JOIN Liang AS B
            ON CASE WHEN A.path LIKE '%.'+B.[to]+'.%'
                      THEN 1 ELSE 0 END=0
                AND A.[to]=B.[from]
),
Liang3 AS
(
    SELECT
        [from],[to],
        MIN(totalMile) AS MinMile
    FROM Liang2
    GROUP BY [from],[to]
)
SELECT B.*
FROM Liang3 AS A
  JOIN Liang2 AS B
      ON A.[from]=B.[from]
          AND A.[to]=B.[to]
          AND A.MinMile=B.totalMile
WHERE A.[from]='A'
    AND A.[to]='C'
OPTION(MAXRECURSION 0)
/*
from to    totalMile  path
---- ----  ---------- ----------------------------
A    C    30          .A.B.C.(1 行受影响)*/

Answer 3

create table ta([source] VARCHAR(1),direct VARCHAR(1),Mile INT) 
INSERT INTO ta 
SELECT 'A','B',20 UNION ALL 
SELECT 'B','C',10 UNION ALL 
SELECT 'C','D',15 UNION ALL 
SELECT 'D','E',10 UNION ALL 
SELECT 'E','F',5 UNION ALL 
SELECT 'D','F',15 UNION ALL 
SELECT 'B','D',20 UNION ALL 
SELECT 'A','E',10 UNION ALL 
SELECT 'A','F',15 
go--创建用户定义函数用于取每个父节点下子节点的采购配置信息
create function f_getChild(@ID VARCHAR(10))
returns @t table(ID VARCHAR(10),PID VARCHAR(10),Level INT,tmp int)
as
begin
    declare @i int
    set @i = 1
    insert into @t select direct,[source],@i,mile from ta where [source] = @ID
    
    while @@rowcount<>0
    begin
        set @i = @i + 1        
        insert into @t 
        select 
            a.direct,a.[source],@i ,mile + b.tmp
        from 
            ta a,@t b 
        where 
            a.[source]=b.id and b.Level = @i-1 and a.direct = 'C'
    end
    return
end
goselect top 1 tmp
from dbo.f_getChild('A')
where id ='C' 
order by tmp 
drop function f_getChild
drop table ta/*
tmp
-----------30*/

Answer 4

create table ta([source] VARCHAR(1),direct VARCHAR(1),Mile INT) 
INSERT INTO ta 
SELECT 'A','B',20 UNION ALL 
SELECT 'B','C',10 UNION ALL 
SELECT 'C','D',15 UNION ALL 
SELECT 'D','E',1 UNION ALL 
SELECT 'E','c',5 UNION ALL --modify
SELECT 'D','F',15 UNION ALL 
SELECT 'B','D',2 UNION ALL 
SELECT 'A','E',10 UNION ALL 
SELECT 'A','F',15 
go--创建用户定义函数
create function f_getChild(@ID VARCHAR(10))
returns @t table(ID VARCHAR(10),PID VARCHAR(10),Level INT,tmp int,col varchar(100))
as
begin
    declare @i int
    set @i = 1
    insert into @t select direct,[source],@i,mile,[source]+','+ direct from ta where [source] = @ID
    
    while @@rowcount<>0
    begin
        set @i = @i + 1        
        insert into @t 
        select 
            a.direct,a.[source],@i ,mile + b.tmp,col+','+ direct
        from 
            ta a,@t b 
        where 
            a.[source]=b.id and b.Level = @i-1 and @I < 10
    end
    return
end
goselect tmp,col
from dbo.f_getChild('A')
where id = 'C' and len(col) = len(replace(col,'C','')) + 1
order by tmp
select top 1 tmp,col
from dbo.f_getChild('A')
where id = 'C' and len(col) = len(replace(col,'C','')) + 1
order by tmpdrop function f_getChild
drop table ta/*
tmp         col
----------- ----------------------------------------------------------------------------------------------------
15          A,E,c
28          A,B,D,E,c
30          A,B,C
-- here
tmp         col
----------- ----------------------------------------------------------------------------------------------------
15          A,E,c
*/

Answer 5

if object_id('[tb]') is not null drop table [tb]
go
create table [tb]([source] varchar(1),[direct] varchar(1),[Mile] int)
insert [tb]
select 'A','B',20 union all
select 'B','C',10 union all
select 'C','D',15 union all
select 'D','E',10 union all
select 'E','F',5 union all
select 'D','F',15 union all
select 'B','D',20 union all
select 'A','E',10 union all
select 'A','F',15
go
--select * from [tb]with szx as
(
select s=source,d=direct,t=mile,p=cast(source+'-'+direct as varchar(8000)) from tb where source='A'
union all
select a.s,b.direct,a.t+mile,p=a.p+'-'+b.direct 
from szx a join tb b
on a.d=b.source and a.d<>'C' and charindex(b.direct,p)=0
)
select top 1 t as 最小距离,p as 路径 from szx where d='C' order by t
/*
最小距离        路径
----------- -----------------
30          A-B-C(1 行受影响)
*/

Answer 6

晕,怎么你们都做的那么复杂的呀,直接这样不就行了吗?create table ta([source] VARCHAR(1),direct VARCHAR(1),Mile INT) 
INSERT INTO ta 
SELECT 'A','B',20 UNION ALL 
SELECT 'B','C',10 UNION ALL 
SELECT 'C','D',15 UNION ALL 
SELECT 'D','E',10 UNION ALL 
SELECT 'E','F',5 UNION ALL 
SELECT 'D','F',15 UNION ALL 
SELECT 'B','D',20 UNION ALL 
SELECT 'A','E',10 UNION ALL 
SELECT 'A','F',15 
go
select A.source,A.direct directA,B.direct directB,(A.mile+B.mile) as mile from ta A inner join ta B on A.direct = B.source 
where (A.mile+B.mile) = (select min(A.mile+B.mile) from ta A inner join ta B on A.direct = B.source)