-4

I am developing a project which helps a person to find out the bus route with bus no and details of switches between the buses. I am able to find the route till single switch but more then that I am not able to do so. please help.

Now my quest is how to GO "SARAI" from "Cantt"? Using the same table.

Column Bus_Stop_Up is having the bus route in upwards and Bus_Stop_Down is having the bus route Downwards.

Result should be like "Cantt(781)->Dwarka(764)->Nehruplace(456)->SARAI"

Details of table are mention below:

CREATE TABLE [dbo].[bustable]
(
   [Sr] [int] NULL
   [bus_no] [varchar](50) NULL,
   [Bus_Stop_Up] [varchar](50) NULL,
   [Bus_Stop_Up_Id] [int] NULL,
   [Bus_Stop_Down] [varchar](50) NULL,
   [Bus_Stop_Down_Id] [int] NULL,
)

Table data

||Sr    | bus_no | Bus_Stop_Up |    Bus_Stop_Down | Bus_Stop_Up_Id | Bus_Stop_Down_Id||              
-------------------------------------------------------------------------------------------------------------
||1     | 781    | DWARKA      |  NEW DELHI       |  1             |    1            ||
||2     | 781    | Airport     |  Cantt           |  2             |    2            ||
||3     | 781    | Cantt       |  Airport         |  3             |    3            ||
||4     | 781    | NEW DELHI   |  DWARKA          |  4             |    4            ||
||5     | 764    | DWARKA      |  NEHRU PLACE     |  1             |    1            ||
||6     | 764    | NEHRUPLACE  |  DWARKA          |  2             |    2            ||
||7     | 456    | NEHRU PLACE |  SARAI           |  1             |    1            ||
||8     | 456    | SARAI       |  NEHRU PLACE     |  2             |    2            ||
VINEET SARASWAT
  • 13
  • 2
  • 1
    Calm down. Don't shout in all-caps. – The Paramagnetic Croissant Jul 26 '14 at 10:34
  • Take a look at this post: http://stackoverflow.com/questions/7105879/graph-problems-connect-by-nocycle-prior-replacement-in-sql-server – Stefan Steiger Jul 26 '14 at 10:36
  • Time to brush up on your graph theory. If the total number of stops is not enormous: build the graph in memory, and then find the shortest path. See also Travelling Salesman, – Richard Jul 26 '14 at 10:37
  • @Richard TSP is an unrelated problem. A simple graph-search algorithm to minimize total path cost will do, e.g. Dijkstra's or A*. – Dai Jul 26 '14 at 10:40

1 Answers1

0

I have posted such a thing a little while ago, here: Graph problems: connect by NOCYCLE prior replacement in SQL server?

You'll find further going tips here, where i cross-posted the question:
http://social.msdn.microsoft.com/Forums/sqlserver/en-US/32069da7-4820-490a-a8b7-09900ea1de69/is-there-a-nocycle-prior-replacement-in-sql-server?forum=transactsql

Graph

CREATE TABLE [dbo].[T_Hops](
    [UID] [uniqueidentifier] NULL,
    [From] [nvarchar](1000) NULL,
    [To] [nvarchar](1000) NULL,
    [Distance] [decimal](18, 5) NULL
) ON [PRIMARY]

GO




      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'A'              ,'E'              ,10.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'E'              ,'D'              ,20.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'A'              ,'B'              ,5.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'B'              ,'C'              ,10.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'C'              ,'D'              ,5.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'A'              ,'F'              ,2.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'F'              ,'G'              ,6.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'G'              ,'H'              ,3.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'H'              ,'D'              ,1.00000              );

Now I can query the best connection from point x to point y like this:

WITH AllRoutes 
(
     [UID]
    ,[FROM]
    ,[To]
    ,[Distance]
    ,[Path]
    ,[Hops]
)
AS
(
    SELECT 
         [UID]
        ,[FROM]
        ,[To]
        ,[Distance]
        ,CAST(([dbo].[T_Hops].[FROM] + [dbo].[T_Hops].[To]) AS varchar(MAX)) AS [Path]
        ,1 AS [Hops]
      FROM [dbo].[T_Hops]
      WHERE [FROM] = 'A'

    UNION ALL


    SELECT 
         [dbo].[T_Hops].[UID]
        --,[dbo].[T_Hops].[FROM]
        ,Parent.[FROM]
        ,[dbo].[T_Hops].[To]
        ,CAST((Parent.[Distance] + [dbo].[T_Hops].[Distance]) AS [decimal](18, 5)) AS distance
        ,CAST((Parent.[Path] + '/' + [dbo].[T_Hops].[FROM] + [dbo].[T_Hops].[To]) AS varchar(MAX)) AS [Path]
        ,(Parent.[Hops] + 1) AS [Hops]
     FROM [dbo].[T_Hops]
     INNER JOIN AllRoutes AS Parent 
            ON Parent.[To] = [dbo].[T_Hops].[FROM] 

)

SELECT TOP 100 PERCENT * FROM AllRoutes


/*
WHERE [FROM] = 'A' 
AND [To] = 'D'
AND CHARINDEX('F', [Path]) != 0 -- via F
ORDER BY Hops, Distance ASC
*/

GO
Stefan Steiger
  • 78,642
  • 66
  • 377
  • 442