最短距离问题

您可以使用递归公用表表达式在有向图上查找所需的路径。数据库表中的每一行表示一个有向边。每一行指定一个原点、一个终点，以及从原点到达终点的开销。根据问题的不同，开销可能表示距离、旅行时间或一些其它测量单位。使用递归，您可以通过此图形查看可能的路线。然后，您可以从可能的路线集中选择您感兴趣的路线。

例如，以查找 Kitchener 市和 Pembroke 市之间的可取驱车路线的问题为例。可能的路线有多条，每一条都会使您经过一组不同的中间城市。目标是找到最短的路线，以及将它们与合理的备用方案进行比较。

首先，定义一个表来表示此图形的边并为每个边插入一行。由于此图形的所有边都恰巧是双向的，所以也必须插入表示相反方向的边。通过选择初始行集可以实现这一点，但要将原点和终点互换。例如，一行必须表示从 Kitchener 到 Toronto 的行程，另一行表示从 Toronto 返回 Kitchener 的行程。

CREATE TABLE travel (
    origin      VARCHAR(10),
    destination VARCHAR(10),
    distance    INT,
  PRIMARY KEY ( origin, destination )
); 
INSERT INTO travel
  SELECT 'Kitchener',  'Toronto',    105 UNION
  SELECT 'Kitchener',  'Barrie',     155 UNION
  SELECT 'North Bay',  'Pembroke',   220 UNION
  SELECT 'Pembroke',   'Ottawa',     150 UNION
  SELECT 'Barrie',     'Toronto',     90 UNION
  SELECT 'Toronto',    'Belleville', 190 UNION
  SELECT 'Belleville', 'Ottawa',     230 UNION
  SELECT 'Belleville', 'Pembroke',   230 UNION
  SELECT 'Barrie',     'Huntsville', 125 UNION
  SELECT 'Huntsville', 'North Bay',  130 UNION
  SELECT 'Huntsville', 'Pembroke',   245; 
INSERT INTO travel   -- Insert the return trips
  SELECT destination, origin, distance
  FROM travel;

下一个任务是编写递归公用表表达式。由于旅程将从 Kitchener 开始，因此初始子查询会先选择从 Kitchener 出发的所有可能路线以及每一条路线的距离。

递归子查询可延伸路线。对于每一条路线，它都会添加从前面路段的终点继续延伸的路段，这样就增加了新路段的长度，从而可以保持每条路线的总运行开销。为了提高效率，如果路线满足以下任一条件，就会终止：

路径返回到起始位置。
路径返回到前面的位置。
路径到达最后的终点。

在当前示例中，任何路径都不应返回到 Kitchener，并且，如果到达 Pembroke，所有路径都应终止。

使用递归查询来研究循环图时，验证它们的结束条件是否完全正确非常重要。在这种情况下，由于一条路线可以包括两个中间城市间的任意大的往返行程数，因此上面的条件是不够的。下面的递归查询通过将任意给定路线中的最大路段数限制为七段来保证终止。

由于示例查询的关键是选择可行路线，因此主查询只选择比最短路线长小于 50% 的那些路线。

WITH RECURSIVE
    trip ( route, destination, previous, distance, segments ) AS
( SELECT CAST( origin || ', ' || destination AS VARCHAR(256) ),
         destination, origin, distance, 1
  FROM travel
  WHERE origin = 'Kitchener'
    UNION ALL
  SELECT route || ', ' || v.destination,
         v.destination,            -- current endpoint
         v.origin,                 -- previous endpoint
         t.distance + v.distance,  -- total distance
         segments + 1              -- total number of segments
  FROM trip t JOIN travel v ON t.destination = v.origin
  WHERE v.destination <> 'Kitchener'  -- Don't return to start
    AND v.destination <> t.previous   -- Prevent backtracking
    AND v.origin      <> 'Pembroke'   -- Stop at the end
    AND segments                      -- TERMINATE RECURSION!
          < ( SELECT count(*)/2 FROM travel ) )
SELECT route, distance, segments FROM trip
WHERE destination = 'Pembroke' AND
      distance < 1.5 * ( SELECT MIN( distance )
                         FROM trip
                         WHERE destination = 'Pembroke' )
ORDER BY distance, segments, route;

当针对上面的数据集运行此语句时，会生成下面的结果。

route	distance	segments
Kitchener, Barrie, Huntsville, Pembroke	525	3
Kitchener, Toronto, Belleville, Pembroke	525	3
Kitchener, Toronto, Barrie, Huntsville, Pembroke	565	4
Kitchener, Barrie, Huntsville, North Bay, Pembroke	630	4
Kitchener, Barrie, Toronto, Belleville, Pembroke	665	4
Kitchener, Toronto, Barrie, Huntsville, North Bay, Pembroke	670	5
Kitchener, Toronto, Belleville, Ottawa, Pembroke	675	4