日期:2014-05-17  浏览次数:20529 次

求寻找最大路径的算法
有一个表路径表只有开始目标两列,记录可通行的两点
Start    Traget
A        B
B        C
A        D
C        E
C        B
E        C
根据给出的起点,寻找它能通行的最大路径。
例如 当前指定 Start列中 A 为起点,寻找能走通的最大路径
如:A-B-C-D-E-C  正确
   A-B-C-B-C    路径中不可以出现重复(B-C 出现了两次)
------解决方案--------------------
if object_id('[tb]') is not null drop table [tb]
create table [tb] (id int,name varchar(1),pid int)
insert into [tb]
select 1,'A',0 union all
select 2,'B',1 union all
select 3,'D',1 union all
select 4,'C',2 union all
select 5,'D',2 union all
select 6,'A',4 union all
select 7,'E',5 union all
select 8,'F',5
GO
;with cte
as
(
    select   *,[path]=cast([name]+'->' as varchar(100)) ,[level] = 1 from tb where pid = 0
    union all
    select a.*,  cast(c.[path]+a.[name]+'->' as varchar(100)),[level]+1 from cte c ,tb a where a.pid = c.id
)
select 

from cte
where len([path]) > 6 and right([path],3) = left([path],3)
/*
id          name pid         path           level
----------- ---- ----------- -------------- -----
6           A    4           A->B->C->A->     4

(1 行受影响)
*/

------------------------------------
-- Author : happyflystone  
-- Date   : 2010-04-06 
-- Version: Microsoft SQL Server 2005 - 9.00.2047.00 (Intel X86) 
--          Apr 14 2006 01:12:25 
--          Copyright (c) 1988-2005 Microsoft Corporation
--          Standard Edition on Windows NT 5.2 (Build 3790: Service Pack 2)
--      
------------------------------------

-- Test Data: ta
IF OBJECT_ID('[tb]') IS NOT NULL 
    DROP TABLE [tb]
Go
CREATE TABLE tb([cid] NVARCHAR(1),[pid] NVARCHAR(1))
Go
INSERT INTO tb
    SELECT 'A','B' UNION ALL
    SELECT 'A','D' UNION ALL
    SELECT 'B','C' UNION ALL
    SELECT 'B','D' UNION ALL
    SELECT 'C','A' UNION ALL
    SELECT 'D','E' UNION ALL