計算最小路徑在SQL表

我在做這個練習的問題長度計算最小路徑在SQL表

Friend1  Friend2  GradeOfFriendship

我需要創建一個其中我必須獲得對稱元組的觸發器，例如：

Luc Mark 

Mark Luc

兩個表中的

。

如果有那麼兩個人之間的直接接觸他們的GradeOfFriendship = 1

如果有一對人，然後GradeOfFriendship = 0之間沒有接觸。

在其他情況下，GradeOfFriendship必須被計算爲在連接這兩個人的所有可能路徑的最小距離（我們必須考慮這個表作爲有向圖）

我的問題不是獲得對稱的元組，但如何計算兩個人之間的所有可能路徑。例如：

Luc  Marc 1 
    Marc John 1 
    Luc  John 2

我正在使用SQL Server。目前我沒有任何想法如何解決這個問題 - 我認爲我必須使用一些遞歸功能，但我不知道如何......

來源

2015-06-19 user5020555

這是朋友和成績之間的外部聯接

來源

2015-06-19 17:49:37 Juan

例子，我不認爲只有用外與朋友和檔次加入我可以解決這個問題 – user5020555

你能場景添加到http://sqlfiddle.com/？ – Juan

你在朋友中有遞歸關係嗎？ – Juan

這是創建遞歸炒網絡的一種方式：

;with DATA as (
    select Person1, Person2, 1 as Grade from Friends 
    union 
    select Person2, Person1, 1 as Grade from Friends 
), 
CTE as (
    select Person1, Person2, Grade, 
    convert(varchar(max), '|' + Person1 + '|' + Person2 +'|') as Path 
    from DATA 
    union all 
    select C.Person1, D.Person2, C.Grade+1, C.Path+D.Person2+'|' 
    from CTE C join DATA D on C.Person2 = D.Person1 
    where C.Person1 <> D.Person2 and C.Path not like '|%'+D.Person2 +'%|' 
) 

select Person1, Person2, min(Grade) 
from CTE 
group by Person1, Person2 
order by 1,3,2

第一CTE稱爲數據是存在的，這樣就沒有必要有friedships輸入兩種方式爲朋友表。如果你已經擁有了這些方法，那麼你可以放棄它。

稱爲CTE的第二個CTE是遞歸的，它獲取從一個人到另一個人的所有路徑。名稱由|分隔的路徑列是否有防止友誼圈圈的無限循環。

最終選擇只挑選朋友之間的最短路徑。

在SQL Fiddle

來源

2015-07-18 12:39:59

計算最小路徑在SQL表

回答

相關問題