如何找到兩個機場之間的最短距離/旅行時間？

這個問題是由我創建的，與我的同事討論過，似乎沒有人有任何想法。因此，想到，我可以問問這裏的專家。如何找到兩個機場之間的最短距離/旅行時間？

我有如下表 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

來源

2010-08-09 user373215

問題缺乏相關細節 - 表格，數據，預期輸出。你希望我們爲你攻入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:14:43

你的表現里程可能會有所不同（如'在真實情況下不這樣做'）。這更像是一個學術活動，就像問題一樣。 – 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 - 搜索飛行時間比例如飛行時間長的飛行組合是否合理？三天？

來源

2010-08-09 22:48:13 skalee

如何找到兩個機場之間的最短距離/旅行時間？

回答

相關問題