slavikmanukyan
10/30/2017 - 7:16 PM

airport_rotes_script.sql

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