ششمین چالش SQL (کوتاه ترین مسیر در گراف)

[محمد سلیم آبادی]

یافتن نزدیک ترین مسیر
ما قصد داریم که از شهر مبدا به شهر مقصد سفر کنیم. برای رسیدن به شهر مقصد چندین مسیر قابل انتخاب است. شهرها توسط جاده هایی که ممکن است یک طرفه یا دو طرفه باشند با همدیگر مرتبط شده اند. هر جاده ای یک مسافت دارد.
شهرها، جاده ها، یکطرفه یا دو طرفه بودن و مسافت آنها را به ما توسط یک گراف ارائه میدهند.
وظیفه ما پیدا کردن کوتاه ترین مسیر از مبدا به مقصد است.
اگر بطور مثال قصد ما حرکت از شهر A و رسیدن به شهر G است باشد، کوتاه ترین مسیر به شرح زیر است:
96837

شما طبق نیاز خود جدول یا جداول را برای ورود اطلاعات گراف طراحی کنید سپس کوئری خود را بر اساس آن جداول پیاده سازی کنید.

[baktash.n81@gmail.com]

خوب من جدول رو اینجوری طراحی کردم

CREATE TABLE [dbo].[Lines](
[LineID] [int] IDENTITY(1,1) NOT NULL,
[N1ID] [nvarchar](50) COLLATE Arabic_CI_AS NULL,
[N2ID] [nvarchar](50) COLLATE Arabic_CI_AS NULL,
[Distance] [int] NULL
)

SET IDENTITY_INSERT [dbo].[Lines] ON
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (1, N'A', N'B', 1000)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (2, N'B', N'A', 1000)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (3, N'B', N'H', 500)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (4, N'B', N'C', 100)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (5, N'C', N'B', 100)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (6, N'D', N'C', 100)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (7, N'D', N'E', 100)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (8, N'E', N'D', 100)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (9, N'E', N'H', 100)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (10, N'E', N'F', 100)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (11, N'F', N'G', 100)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (12, N'G', N'J', 200)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (13, N'G', N'A', 2000)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (14, N'J', N'H', 200)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (15, N'H', N'E', 100)
INSERT [dbo].[Lines] ([LineID], [N1ID], [N2ID], [Distance]) VALUES (16, N'H', N'B', 500)

SET IDENTITY_INSERT [dbo].[Lines] OFF


با این Script هم مسیر رو پیدا می کنم ...

declare @from nvarchar(1)
declare @to nvarchar(1)

set @from = 'A'
set @to = 'G';

with t (n1id,n2id,s ,sumdis,c)
as
(

select n1id,n2id,cast((n1id+'->'+n2id) as nvarchar(1000)),distance,1 as c from lines
where n1id=@from

union all

select t.n1id,lines.n2id,cast((t.s+'->'+lines.n2id) as nvarchar(1000)),distance+sumdis , c+1 from lines join t on lines.n1id=t.n2id
where c<16

)

select top 1 * from t where n2id=@to and n1id=@from order by 4

[محمد سلیم آبادی]

ممنون از پاسختون.
من تونستم با افزودن یک فیلتر بسیار ساده به کوئریتان سرعت اجرای آن را فوق العاده افزایش بدم. موضوع بر میگرده به فیلتر کردن "چرخه ها". همانطور که خودتون بهتر از من میدونید بین دو گره ی A و B چرخه وجود داره (به دلیل وجود دو مسیر یکی رفت و یکی برگشت). شما مانع از ادامه ی این چرخه های غیر ضروری و اضافه نشدین که همین باعث میشه تعداد سطرهای حاصل شده از این عبارت بازگشتی به ده ها هزار برسه! در حالی که با جلوگیری از ادامه چرخه ها میشه سطرهای خروجی را به کمتر از ده عدد کاهش داد!

فقط کافیه شرط charindex(lines.n2id,t.s)=0 را در ماده where یا join سلکت دوم در عبارت بازگشتی اضافه کنید. یعنی:

select t.n1id,lines.n2id,cast((t.s+'->'+lines.n2id) as nvarchar(1000)),distance+sumdis , c+1 from lines join t on lines.n1id=t.n2id
where c<16 and charindex(lines.n2id,t.s)=0

[محمد سلیم آبادی]

یک مساله جدید مرتبط:
"یافتن کوتاه ترین مسیر بین هر دو رأس"

یعنی هدف لیست کردن تمام زوج رأس های موجود همراه با کوتاه ترین مسیر بین آنهاست.
با در نظر گرفتن تعداد رأس های مثال (9 رأس)، تعداد زوج رأس ها باید برابر باشد با جایگشت 2 رأس از 9 رأس که طبق اصل شمارش، برابر است با 9 ضرب در 8 که مساویست با 72. البته با فرض اینکه بین تمام زوج گره ها ارتباط وجود دارد.