A Scenario to Ponder #11
This time it's a pretty interesting scenario to solve. I have a table called the distance_tbl holding distance between different cities.
Here is the table definition:
create table #distance_tbl (city1 char(1), city2 char(1), distance int)
And the sample data:
insert into #distance_tbl values('A','B',200)
insert into #distance_tbl values('A','C',100)
insert into #distance_tbl values('C','B',90)
insert into #distance_tbl values('C','D',300)
insert into #distance_tbl values('C','E',200)
insert into #distance_tbl values('E','F',50)
insert into #distance_tbl values('F','D',50)
insert into #distance_tbl values('F','C',220)
Lets assume the information is pretty comprehensive and so the table is pretty huge.
I want to put this information to good use. So, I am planning to build a site where people can come and search for the shortest distance between two cities and also the route to go to the city.
The site will inturn use a query to get the information. Two paramters come from the user to the query. The start city and the end city, say @Start and @end and both are of type char(1).
How the result is presented, I leave it to your imagination. But here are a few examples on the information required for a given input.
Example 1:
Input: @Start = 'A', @end 'B'
Output: Distance = 190 and you go from A to C and C to B
Example 2:
Input: @Start = 'C', @End 'D'
Output: Distance = 270 and you go from C to F and F to D
A few rules to note:
In the table, A to C is 100 miles also means C to A is 100 miles and will not be stored as a seperate row.
If two different paths have the same shortest distance, then I need to get the path that touches the least number of cities.
The solution can be given in SQL Server 2000 or SQL Server 2005 and you may use temp tables, cursors or while loops, if necessary.
Posts
1 comments:
Here is an implementation that will work in SQL Server 2005. If you can think of a solution in SQL Server 2000 or a better solution do let me know.
declare @start char,@end char
set @start = 'c'
set @end = 'd';
with cte as
(
SELECT city1,city2,distance FROM #DISTANCE_TBL
union all
SELECT city2,city1,distance FROM #DISTANCE_TBL
),
cte1 as
(select city1 as start,city2 as dest, cast(city1 + '->' + city2 as varchar(100)) as pth,
distance
from cte where city1 = @start
union all
select a.start,b.city2,cast(pth + '->' + city2 as varchar(100)), a.distance + b.distance from cte1 as a, cte as b
where a.dest = b.city1 and charindex(b.city2 + '->', a.pth) = 0
)
select top 1 * from cte1
where dest = @end
order by distance, len(pth)
This solution is based on pattern matching in a string. I somehow don't like this solution as there are a few situations , though far-fetched, where it might fail.
And, for those who are following these puzzles, please do excuse me for being inactive for the past few days. My job is demanding my blogging time. And the situation is going to continue for a few more days :(
Wish me luck....
Post a Comment