0

我有一个图形，它保存为两个表，名称为 Edge 和 Node，在 SQL 中如下所示：

Node table:
Id Name
10 A
11 B
12 C

Edge Table:
From To Weight
10 11 0.3
10 14 0.2
10 12 0.5
11 12 0.6
12 10 0.8

例如，从节点 10 到节点 12 的路径的一种可能解决方案如下：

From    To  Weight  Path
10  12  0.9 10,11,12

现在，我想找出图形节点之间的最长路径（对于任何可能的路径）。

我用负边缘改变了dijkstra，它循环了，不返回任何结果。

是否有任何程序或算法来找出所需的结果？

4

1 回答 1

1

最近我遇到了类似的问题，并尝试使用 SQL recursive CTE query 找到最长的路径。请参考给定的文章。

我尝试针对您的问题修改上述解决方案，并获取所有可能路径的列表，如以下输出屏幕所示

在此处输入图像描述

如果这是您想要达到的结果，我可以继续在 SQL Server 上描述我的解决方案

引用的 SQL 查询计算给定两个节点的最长路径。所以首先我们需要定义所有可能的起始节点和目标节点

下面的查询列出了所有可能集合的组合

select Nodes_From.Id as [From], Nodes_To.Id as [To]
from LongestPath_Nodes as Nodes_From
inner join LongestPath_Nodes as Nodes_To
    on Nodes_From.Id <> Nodes_To.Id

请注意，这不包括“14”，例如，因为它不在节点表中（因此在给定的测试数据中实际上存在一致性问题）

因此，通过创建SQL 游标，我可以遍历每个节点集（从节点到节点的组合）并执行存储过程，其中包括 SQL 代码，计算参考文章中给定两个节点的最长路径

我还创建了一个表格来存储路径的总重量

Create Table LongestPath_Routes ([weight] decimal(10,1), path varchar(100))

如下面的 SQL 脚本所示，我一开始就清除了这个表。然后为存储过程中的每个从到节点集填充它最后在游标执行完成后，我通过根据权重列排序来查询表以获得最长路径（也可能是最短路径）

truncate table LongestPath_Routes

DECLARE @From TinyInt
DECLARE @To TinyInt

DECLARE PathCursor CURSOR FAST_FORWARD FOR
    select Nodes_From.Id as [From], Nodes_To.Id as [To]
    from LongestPath_Nodes as Nodes_From
    inner join LongestPath_Nodes as Nodes_To
        on Nodes_From.Id <> Nodes_To.Id

OPEN PathCursor

FETCH NEXT FROM PathCursor INTO @From, @To

WHILE @@FETCH_STATUS = 0
BEGIN
set nocount on
 EXEC LongestPath_Calculate_for_Nodes @From, @To
set nocount off

 FETCH NEXT FROM PathCursor INTO @From, @To
END

CLOSE PathCursor
DEALLOCATE PathCursor 

select * from LongestPath_Routes order by [weight] desc

我希望这个解决方案可以帮助你

于 2018-03-30T15:15:05.650 回答