In the example in the preceding section, each item had only one superior. In a network, an item can have more than one superior. The following data, for example, is a representation of airline flights among a number of cities:
Departure Destination --------- ------------- Chicago New York Chicago Milwaukee Denver Chicago Seattle Chicago Seattle Denver Seattle San Francisco
A common problem you can have with this data is finding all routes between a given pair of cities:
Itineraries ---------------------------------- Seattle, Chicago, New York Seattle, Denver, Chicago, New York
A few changes to the example in the preceding section can accomplish this:
These changes are illustrated in the following example (not from pubs):
create proc route (@current char(20), @dest char(20), @maxlevel int = 5) as set nocount on declare @level int create table #stack (city char(20), level int) create table #list (city char(20), level int) insert #stack values (@current, 1) select @level = 1 while @level > 0 begin if exists (select * from #stack where level = @level) begin select @current = city from #stack where level = @level delete from #stack where level = @level and city = @current delete from #list where level >= @level if exists(select * from #list where city = @current) continue insert #list values(@current, @level) if(@current = @dest) begin select itinerary = city from #list continue end insert #stack select destination, @level 1 from flights where departure = @current and @level < @maxlevel if @@rowcount > 0 select @level = @level 1 end else select @level = @level - 1 end
In this example, when @level is greater than 0, the process follows several steps:
The IF EXISTS statement at the beginning of the WHILE loop skips the current city if it's already in the current itinerary.
If the flights table in the preceding example also contains cost information, the lowest cost route can be found by saving the current itinerary if its total cost is less than the best cost so far:
select @cost = sum(cost) from #list if @cost < @lowest_cost begin @lowest_cost = @cost truncate table #best_route insert #best_route select * from #list end
For greater efficiency, you can stop expanding the current route if the current cost far exceeds the cost of the best route:
if (select sum(cost) from #list) > @lowest_cost continue
If the flights table also includes a departure and arrival time, you can add an IF statement to expand only the routes that have a departure time at least one hour after the arrival time of the current route:
if ((select sum(cost) from #list) > @lowest_cost) and datediff(hh, departuretime, @arrivaltime) > 1) continue