CODEWITHSUNDEEP
sqlsql-server
Sri Ch
Sri Ch

Reputation: 11

Find shortest distance between two cities

I have two tables. The first table has cities:

Cities
a
b
c
d
f

And other table has distances between cities:

start city     destination city      distance
1                     2                 100
1                     3                 150
2                     4                 215
3                     4                 125
3                     5                 210

I want to find shortest distance between two cities of the given table. How can I do that?

Upvotes: 1

Views: 1214

Answers (2)

Venkataraman R
Venkataraman R

Reputation: 12969

Below is the query which uses CTE to arrive at the shortest distance and the travel path for two cities.

DECLARE @cities table(id int IDENTITY(1,1), city varchar(30))

insert into @cities(city)
VALUES
('a'),
('b'),
('c'),
('d'),
('f');

DECLARE @citydistance table(startcity int, destinationcity int, distance int)

insert into @citydistance
VALUES
(1  , 2 , 100),
(1  , 3 , 150),
(2  , 4 , 215),
(3  , 4 , 125),
(3  , 5 , 210);

;with cte_citypaths as
(
SELECT cd.startcity as startcity, cast((sc.city + '->'+ sd.city) as varchar(max)) as travel, cd.destinationcity destinationcity, distance
from @citydistance as cd
CROSS APPLY (SELECT city from @cities as c WHERE c.id = cd.startcity) as sc
CROSS APPLY (SELECT city from @cities as c WHERE c.id = cd.destinationcity) as sd
union all
select cte.startcity, cast((cte.travel + '->'+  sd.city) as varchar(max)) as travel,cd.destinationcity, cte.distance + cd.distance 
from @citydistance as cd
join cte_citypaths as cte
on cte.destinationcity = cd.startcity
CROSS APPLY (SELECT city from @cities as c WHERE c.id = cd.startcity) as sc
CROSS APPLY (SELECT city from @cities as c WHERE c.id = cd.destinationcity) as sd
)
SELECT startcity, travel, destinationcity, distance
from
(
select sc.city as startcity, cte.travel, sd.city as destinationCity, cte.distance,
row_number() over (partition by sc.city, sd.city order by distance) as rnk
from cte_citypaths as cte
CROSS APPLY (SELECT city from @cities as c WHERE c.id = cte.startcity) as sc
CROSS APPLY (SELECT city from @cities as c WHERE c.id = cte.destinationcity) as sd
) as t
where rnk = 1


+-----------+---------+-----------------+----------+
| startcity | travel  | destinationcity | distance |
+-----------+---------+-----------------+----------+
| a         | a->b    | b               |      100 |
| a         | a->c    | c               |      150 |
| a         | a->c->d | d               |      275 |
| a         | a->c->f | f               |      360 |
| b         | b->d    | d               |      215 |
| c         | c->d    | d               |      125 |
| c         | c->f    | f               |      210 |
+-----------+---------+-----------------+----------+

Upvotes: 0

Rahul Mandelia
Rahul Mandelia

Reputation: 11

Your tables do not have a common column between the two. Also, you can use the shortest path algorithm to implement this. Follow the below link to implement it:

https://www.mssqltips.com/sqlservertip/5540/using-tsql-to-find-the-shortest-distance-between-two-points/

Shortest path Algorithm Using T-SQL

Upvotes: 1

Related Questions