In a network, an item can have more than one superior. For example, the following data 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
CREATE PROCEDURE 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 city AS itinerary
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 -- WHILE
If the flights table 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, stop expanding the current route if the current cost exceeds the cost of the best route:
IF (SELECT SUM(cost) FROM #list) > @lowest_cost
CONTINUE
If the flights table 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
