#title 최단경로찾기

아래의 지도에서 집에서 학교로가는 최단경로를 찾아보자.
노드간 연결된 선 근처의 숫자는 거리다.

attachment:최단경로찾기/network.png
--출처: https://www.youtube.com/watch?v=tZu4x5825LI

{{{
--drop table #edge
create table #edge(
    from_point nvarchar(20)
,   to_point nvarchar(20)
,   distance int
)
go

insert into #edge values
    (N'집', N'미용실', 5)
,   (N'집', N'슈퍼마켓', 10)
,   (N'집', N'영어학원', 9)
,   (N'미용실', N'집', 5)
,   (N'미용실', N'슈퍼마켓', 3)
,   (N'미용실', N'은행', 11)
,   (N'슈퍼마켓', N'집', 10)
,   (N'슈퍼마켓', N'미용실', 3)
,   (N'슈퍼마켓', N'레스토랑', 3)
,   (N'슈퍼마켓', N'은행', 10)
,   (N'슈퍼마켓', N'영어학원', 7)
,   (N'영어학원', N'집', 9)
,   (N'영어학원', N'슈퍼마켓', 7)
,   (N'영어학원', N'은행', 7)
,   (N'영어학원', N'학교', 12)
,   (N'레스토랑', N'슈퍼마켓', 3)
,   (N'레스토랑', N'은행', 4)
,   (N'은행', N'레스토랑', 4)
,   (N'은행', N'슈퍼마켓', 10)
,   (N'은행', N'미용실', 11)
,   (N'은행', N'영어학원', 7)
,   (N'은행', N'학교', 2)
,   (N'학교', N'은행', 2)
,   (N'학교', N'영어학원', 12)
go
}}}

최단경로찾기
{{{
--집에서 학교로 가는 최단경로찾기
declare
    @start_point nvarchar(20)
,   @end_point nvarchar(20)

set @start_point = N'집'
set @end_point = N'학교'

;with cte
as
(
    select
        from_point
    ,   to_point
    ,   distance
    ,   distance distance_sum
    ,   1 step
    ,   convert(nvarchar(4000), from_point) path
    from #edge
    where from_point = @start_point
    union all
    select
        a.from_point
    ,   a.to_point
    ,   a.distance
    ,   a.distance + b.distance_sum
    ,   b.step + 1 step
    ,   convert(nvarchar(4000), b.path + '->' + a.from_point)
    from #edge a
        inner join cte b
            on a.from_point = b.to_point
            and b.path not like '%' + b.to_point + '%'
    where 1=1
    and a.from_point <> @end_point
)
select 
    path + '->' + to_point path
,   distance_sum 
,   step
from cte
where to_point = @end_point
order by distance_sum
option (maxrecursion 0);
}}}

attachment:최단경로찾기/result.png

'집->미용실->슈퍼마켓->레스토랑->은행->학교'가 최단경로다.