计算最小路径在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表

回答

相关问题