How to find the shortest distance/ travel time between two airports?

The problem was created by me, discussed with my co-workers and no one seem to have an idea. Thus, thought, I can ask the experts here.

I've the following table FlightInfo and the fields are

Start Destination Flight_Duration

The goal is to find out, the shortest flight between two cities. The challenge is not all cities have direct flights. (Example: PHL to PVA ->Philadelphia to Shangai). You have to connect in Detroit (DTW) or Chicago (ORD)

How will you go about writing an SQL statement?

Example table contents

PHL DTW 2.25

DTW PVG 15.15

PHL ORD 3.15

ORD PVG 16.20

-------------Problems Reply------------

Brute force:

declare @t table (
[from] char(3),
[to] char(3),
[time] float);

insert into @t
([from], [to], [time])
('PHL', 'DTW', 2.25),
('DTW', 'PVG', 15.15),
('PHL', 'ORD', 3.15),
('ORD', 'PVG', 16.20);

declare @src char(3) = 'PHL',
@dst char(3) = 'PVG';

with cteAnchor as (
select case @src
when [from] then [to]
when [to] then [from]
end as [layover], [time]
, [time] as [total]
, cast([from]+'-'+[to] as varchar(max)) as [path]
, 1 as [flights]
from @t
where @src in ([from], [to]))
, cteRecursive as (
select [layover], [time], [total], [path], [flights]
from cteAnchor
union all
select case r.layover
when [from] then [to]
when [to] then [from]
end as [layover]
, t.[time]
, t.[time] + r.[total] as [total]
, r.[path] + ' ' +t.[from]+'-'+t.[to] as [path]
, r.[flights] + 1
from @t t
join cteRecursive r
on (t.[from] = r.[layover] and 0 = charindex(t.[to], r.[path]))
(t.[to] = r.[layover] and 0 = charindex(t.[from], r.[path]))
select top(1) [flights], [total], [path] from cteRecursive
where @dst = [layover]
order by [total] asc;


total path

Edit note: I have modified the implementation of the CTE with one which is resilient to cycles and is also actually correct.

I would make an assumption that you may get from any single airport to any another one in at most three flights. It is possible that it won't be true in few very exceptional cases, but is this really a problem? I don't think so, however you may consider adding another join if you feel you need it.

Table flights:
origin VARCHAR
destination VARCHAR

And query:

SELECT *, f3.end - f1.end AS duration
FROM flights AS f1
INNER JOIN flights AS f2
ON f1.destination = f2.origin AND f1.end < f2.start
INNER JOIN flights AS f3
ON f2.destination = f3.origin AND f2.end < f3.start
WHERE f1.start BETWEEN some_reasonable_values_not_to_have_too_many_rows_in_join
AND f2.start BETWEEN some_reasonable_values_not_to_have_too_many_rows_in_join
AND f3.start BETWEEN some_reasonable_values_not_to_have_too_many_rows_in_join
AND f1.origin = your_desired_origin
AND f3.destination = your_desired_destination
ORDER BY duration ASC

This is for combination of three flights. Similar SQL for two flights and one flight (less joins). Then, union those three queries and take the best result.

You may want to add some minimal delay between flights. Some_reasonable_values_not_to_have_too_many_rows_in_join - does it make sense to search flight combinations that take longer than e.g. three days?

Category:sql Views:3 Time:2010-08-09
Tags: sql sql server

Related post

  • Shortest distance travel - common meeting point 2011-08-23

    I came across this problem wherein there are a number of houses on a 2-D grid (their coordinates are given) and we essentially have to find which house can be used as a meeting point so that the distance traveled by everyone minimizes. Let us assume

  • how to have object always travel the shortest distance towards/to point it is already following 2012-02-20

    a. I have an object. b. when the user touches the screen it will ease/tween to the users touch coordinate. c. if the user drags their finger then the object will follow that path simply by traversing the path made by the input data from the motion ev

  • Shortest distance between a point and a line segment 2009-05-11

    I need a basic function to find the shortest distance between a point and a line segment. Feel free to write the solution in any language you want; I can translate it into what I'm using (Javascript). EDIT: My line segment is defined by two endpoints

  • Shortest distance between points algorithm 2009-10-21

    Given a set of points on a plane, find the shortest line segment formed by any two of these points. How can I do that? The trivial way is obviously to calculate each distance, but I need another algorithm to compare. --------------Solutions----------

  • Shortest distance between two line segments 2010-05-13

    I need a function to find the shortest distance between two line segments. A line segment is defined by two endpoints. So for example one of my line segments (AB) would be defined by the two points A (x1,y1) and B (x2,y2) and the other (CD) would be

  • Shortest distance between points on a toroidally wrapped (x- and y- wrapping) map? 2010-06-14

    I have a toroidal-ish Euclidean-ish map. That is the surface is a flat, Euclidean rectangle, but when a point moves to the right boundary, it will appear at the left boundary (at the same y value), given by x_new = x_old % width Basically, points are

  • Finding distance travelled by robot using Optical Flow 2010-06-18

    I'm working on a project right now in which we are developing an autonomous robot. I have to basically find out the distance travelled by the robot between any 2 intervals. I'm using OpenCV, and using the Optical Flow functions of OpenCV, I'm able to

  • Distance travelled by a robot using Optical Flow 2010-07-06

    is there a way to find out the distance travelled by a robot using Optical Flow? For example, using OpenCV, I'm able to find out the velocity of each pixel between 2 images taken by a camera. However, I don't know where to go with this to find out th

  • Calculating the shortest distance(perpendicular distance) between a point and a line 2010-10-02

    Possible Duplicate: Shortest distance between a point and a line segment Hi, I have a point A, and a Line with two endpoint B,C. I want to know how I can calculate the shortest distance between point A and the line formed within B and C. Pseudo-code

  • Android: optimal way to find shortest distance between Point and Rect? 2011-01-21

    Seems like there should be some convenient way to do this? I couldn't find one, so I threw together the below algorithm. Is it memory/computationally optimal? Thanks: Edit: Original algorithm was stupidly wrong, maybe this is better? public static fl

  • Calculate real time distance traveled using google maps 2011-03-21

    There is a requirement to find the real time distance traveled using google maps. This should be calculated by the phone app itself. When I mean real time, I mean for example if the user is traveling to point A, the user can get to the point in many

  • What is shortest distance between 2 nodes in a matrix? 2011-03-27

    I have a matrix 5x5 (25 nodes). Is there a formula that I can find the shortest distance between 2 node i and j in the matrix ? Note: distance between 1 node and its neighbor is 1 unit. ================= In my observation, there are many paths with t

  • Shortest distance to rectangle caching 2011-05-30

    I have a list of rectangles that don't have to be parallel to the axes. I also have a master rectangle that is parallel to the axes. I need an algorithm that can tell which rectangle is a point closest to(the point must be in the master rectangle). t

  • How do you calculate the line of shortest distance between two sets of line segments that passes through a known point? 2011-05-30

    Given two sets of line segments (xa1..N,ya1..N) and (xb1..N,yb1..N) that represent the upper and lower surfaces of a geology unit, and a known point (xc1,yc1) within the geology unit, how do I find the line of shortest distance between (xa,ya) and (x

  • What is the best way to calculate distance travelled over a period of time? 2011-07-18

    I am trying to calculate the distance elapsed over a period of time in an app for the Android platform. What is the best way to do this? At the moment, I am implementing LocationListener interface. I am overriding the method onLocationChanged I am cu

  • Finding shortest distance / route on map 2011-08-09

    In Actionscript, I'm trying to work out the best way to create the shortest route between two point on the map above. I have all the distances. Algorithms like A* I dont think are relevant as it is near impossible to work out the heuristic distance.

  • Shortest distance pair with points given on a line? 2011-08-09

    Can someone suggest an algorithm to find out the shortest distance pair of unsorted, colinear points? I've got one solution which does this in O(nlogn) by just doing the closest pair of points in 2D and applying to the line. However, can this be done

  • Is it possible to make an HTML5 Trip Meter that tracks distance traveled? 2011-10-06

    I'm trying to develop a webapp that users can run on their mobile phone to track the distance they've traveled. Think of it as something like RunKeeper, but in webapp form. The following article describes an easy way to create a Trip Meter with HTML5

  • how to calculate distance travelled 2011-11-15

    I am developing an application in which I need to calculate the distance travelled. I am facing a problem while calculating the distance. Here is my code: locationmanager.requestLocationUpdates(bestProvider,0,0,new Listener()); public class Listener

Copyright (C), All Rights Reserved.

processed in 0.150 (s). 11 q(s)