查找两个城市之间的最短距离

cnjp1d6j  于 2021-08-01  发布在  Java
关注(0)|答案(2)|浏览(288)

我有两张table。第一个表包含城市:

Cities
a
b
c
d
f

另一张表显示了城市之间的距离:

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

我想找出给定表中两个城市之间的最短距离。我该怎么做?

t9eec4r0

t9eec4r01#

表之间没有公共列。此外,您还可以使用最短路径算法来实现这一点。请按以下链接执行:
https://www.mssqltips.com/sqlservertip/5540/using-tsql-to-find-the-shortest-distance-between-two-points/
基于t-sql的最短路径算法

jpfvwuh4

jpfvwuh42#

下面是使用cte查询两个城市的最短距离和出行路径。

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 |
+-----------+---------+-----------------+----------+

相关问题