这个算法相当简单。首先，使用 fares 表中的数据填充 faretemp 表，作为初始的航程。然后，取到我们刚才插入的所有数据，使用它们建立所有可能的二航程（two-hop）路径。重复这一过程，直至在两个节点之间创建了新路径。
循环过程将在节点间所有可能的路径都被描述之后退出。假如我们只对某个开始条件感爱好，那么我们还可以限制第一次的插入从而减少装载数据的量。下面是发现路径的代码：
truncate table faretemp;
begin
-- initial connections
insert into faretemp
select depart,arrive,1,depart','arrive,price from fares;
while sql%rowcount > 0 loop
insert into faretemp
select depart,arrive,hops,route,price from nexthop
where (depart,arrive)
not in (select depart,arrive from faretemp);
end loop;
end;
/
show errors;
select * from faretemp order by depart,arrive;
可以在表 A 中查看输出。
前面的数据有一个小问题。数据是点之间最短路径（最小航程数）的集合。然而，从伦敦到圣保罗的航程却不是最便宜的一个。
要解决最便宜的费用问题，需要对我们的循环做一个改进，当在一个航程中发现一个更便宜的路线时使用这个路线代替原来的路线。修改后的代码如下：
truncate table faretemp;
declare
l_count integer;
begin
-- initial connections
insert into faretemp
select depart,arrive,1,depart','arrive,price from fares;
l_count := sql%rowcount;
while l_count > 0 loop
update faretemp
set (hops,route,price) =
(select hops,route,price from nexthop
where depart = faretemp.depart
and arrive = faretemp.arrive)
where (depart,arrive) in
(select depart,arrive from nexthop
where price < faretemp.price);
l_count := sql%rowcount;
insert into faretemp
select depart,arrive,hops,route,price from nexthop
where (depart,arrive)
not in (select depart,arrive from faretemp);
l_count := l_count + sql%rowcount;
end loop;
end;
/
show errors;
select * from faretemp order by depart,arrive;
可能在表 B 中查看输出。
算法发现LHR、JFK、GRU 路线比 LHR、GRU 路线便宜，所以用前者代替了后者。循环将在没有更便宜的费用，并且没有其它可能路线时退出。
|
