CREATE TABLE cities (
id int not null identity(1,1) primary key,
name varchar(256)
)
CREATE TABLE airport_routes (
from_city int,
to_city int,
distance int,
constraint fk_from_city foreign key (from_city) references cities (id),
constraint fk_to_city foreign key (to_city) references cities (id),
)
INSERT INTO cities (name) VALUES
('Yerevan'),
('Moscow'),
('Kiev'),
('Doha'),
('Beijing'),
('Paris'),
('Barcelona'),
('Madrid'),
('London'),
('Los Angeles'),
('New York')
INSERT INTO airport_routes (from_city, to_city, distance) VALUES
(1, 2, 2000),
(1, 3, 2500),
(1, 4, 4000),
(2, 4, 5000),
(2, 6, 5500),
(2, 7, 6500),
(2, 8, 6600),
(2, 9, 7500),
(3, 4, 3000),
(3, 6, 2500),
(3, 7, 2800),
(3, 8, 4000),
(4, 5, 8000),
(4, 10, 12000)
CREATE VIEW city_distance_view AS
SELECT
n1.id AS start_id,
n1.name AS start_name,
n2.id AS destination_id,
n2.name AS destination_name,
l.distance AS distance
FROM
cities n1
JOIN airport_routes l ON (n1.id = l.from_city)
JOIN cities n2 ON (l.to_city = n2.id);
WITH search_path (path_ids, length, is_visited) AS
(
SELECT
CAST((CAST(start_id AS VARCHAR(10)) + ',' + cast(destination_id AS VARCHAR(10))) as varchar(255)),
distance,
CASE WHEN start_id = destination_id
THEN 1
ELSE 0 END
FROM
city_distance_view
UNION ALL
SELECT
cast((path_ids + ',' + CAST(d.destination_id AS VARCHAR(10))) as varchar(255)),
f.length + d.distance,
CASE WHEN (CHARINDEX(CAST(d.destination_id AS VARCHAR(10)) + ',', f.path_ids) > 0) OR
(CHARINDEX(',' + CAST(d.destination_id AS VARCHAR(10)), f.path_ids) > 0)
THEN 1
ELSE 0 END
FROM
city_distance_view d,
search_path f
WHERE
SUBSTRING(f.path_ids, LEN(f.path_ids) - CHARINDEX(',', REVERSE(f.path_ids)) + 2, LEN(f.path_ids)) = cast(d.start_id AS VARCHAR(10))
AND f.is_visited = 0
)
SELECT TOP 1 path_ids, length
FROM search_path
where
SUBSTRING(path_ids, 1, CHARINDEX(',', path_ids) - 1) = '1' AND
SUBSTRING(path_ids, LEN(path_ids) - CHARINDEX(',', REVERSE(path_ids)) + 2, LEN(path_ids)) = '5'
ORDER BY length