如何找到两个机场之间的最短距离/旅行时间？

问题描述：

这个问题是由我创建的，与我的同事讨论过，似乎没有人有任何想法。因此，想到，我可以问问这里的专家。如何找到两个机场之间的最短距离/旅行时间？

我有如下表 FlightInfo和领域是

Start 
Destination 
Flight_Duration

的目标是找出两个城市之间的最短飞行。挑战并非所有城市都有直飞航班。（例如：PHL到PVA - >费城到上海）。您必须在底特律（DTW）或芝加哥（ORD）连接

您将如何着手编写SQL语句？

示例表内容

PHL DTW 2.25

DTW PVG 15.15

PHL ORD 3.15

ORD PVG 16.20

问题缺乏相关细节 - 表格，数据，预期输出。你希望我们为你攻入SABER，或者什么？ – 2010-08-09 22:32:53

在各种SQL变体中存在Dijkstra算法的现有实现。 – relet 2010-08-09 22:35:10

最短路径问题：http://en.wikipedia.org/wiki/Shortest_path_problem – 2010-08-09 22:37:56

答

蛮力：

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

insert into @t 
    ([from], [to], [time]) 
values 
('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])) 
     or 
     (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 
17.4 PHL-DTW DTW-PVG

编辑注：我已经修改了CTE的执行情况，其中一个是弹性的周期，其实也是正确的。

你的表现里程可能会有所不同（如'在真实情况下不这样做'）。这更像是一个学术活动，就像问题一样。 – 2010-08-09 23:18:24

感谢Remus Rusanu。欣赏它。 – user373215 2010-08-10 00:01:01

答

我会做一个假设，你可以从任何得到单机场到最多三个航班中的任何一个机场。在极少数例外情况下，这可能不是真的，但这真的是一个问题吗？我不这么认为，但是如果你觉得你需要的话，你可以考虑添加另一个连接。

Table flights: 
origin  VARCHAR 
destination VARCHAR 
start  DATETIME 
end   DATETIME

和查询：

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 
LIMIT 1

这是三个航班组合。两个航班和一个航班的类似SQL（少连接）。然后，结合这三个查询并采取最佳结果。

您可能希望在航班之间添加一些最小延迟。 Some_reasonable_values_not_to_have_too_many_rows_in_join - 搜索飞行时间比例如飞行时间长的飞行组合是否合理？三天？

如何找到两个机场之间的最短距离/旅行时间？

相关推荐