Shortest-path

0

Please login or register to vote for this query.

(click on this box to dismiss)

Anime and Manga

Q&A for anime and manga fans

CREATE TABLE #mytable
    ([Source] varchar(1), [Destination] varchar(1), [Fare] int)
;
    
INSERT INTO #mytable
    ([Source], [Destination], [Fare])
VALUES
    ('A', 'B', 10),
    ('B', 'C', 5),
    ('B', 'D', 1),
    ('D', 'C', 1),
    ('A', 'D', 1)
    
;WITH Paths AS (
   -- Anchor query: get first step
   SELECT CAST(CONCAT(Source, '->', Destination) AS VARCHAR(MAX)) AS Path, 
          Destination, Fare, 0 AS Terminate
   FROM #mytable
   WHERE Source = 'B'

   UNION ALL

   -- Recursive part: get next step
   SELECT CAST(CONCAT(Path, '->', t.Destination) AS VARCHAR(MAX)) AS Path, 
          t.Destination, Fare = t.Fare + p.Fare, 
          IIF(t.Destination = 'C', 1, 0) AS Terminate
   FROM #mytable AS t
   JOIN Paths AS p ON t.Source = p.Destination
   WHERE p.Destination <> 'C'
)
SELECT Path, Fare
FROM (
  SELECT Path, Fare,
         RANK() OVER (ORDER BY Fare) AS rnk
  FROM Paths
  WHERE Terminate = 1) AS t
WHERE t.rnk = 1

Enter Parameters

Options:
Switch to meta site
loading Hold tight while we fetch your results