c# - 如何获得两个城市之间的最低票价

Question

我有下表

Source  Destination   Fare
A         B            10
B         C            5
B         D            1
D         C            1
A         D            1

现在我想编写一个查询，它会给出两个城市之间的最低票价。

例如，如果我想去 A->C，那么最低票价是 2 A->D->C

这个问题用什么MS-Sql查询。

Answer 1

试试这个:

;WITH Paths AS (
   -- Anchor query: get first step
   SELECT CAST(CONCAT(Source, '->', Destination) AS VARCHAR(MAX)) AS Path, 
          Destination, Fare, 
          IIF(Destination = 'C', 1, 0) AS Terminate
   FROM mytable
   WHERE Source = 'A'

   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

这是一种蛮力方法:它使用递归 CTE 来获取所有可能的路径。然后使用 RANK 我们可以选择最低票价的。

Demo here