航班時刻表算法

Question

我有一個所有直飛航班的清單。從這裏我想獲得航班從A到B的連接。什麼是適合這個問題的算法或數據結構？謝謝。

Answer 1

基本上，這是遍歷一個圖的問題，其中每個出發或到達將是一個節點，並且每個飛行都是一個邊。您通常會將成本應用於邊緣 - 取決於用戶的偏好，「成本」可能是機票的成本（以獲得最低價格）或飛行時間（以獲得最短的飛行時間）。在同一機場的抵達和離開將通過其停留時間（並且從價格角度來看，該邊緣通常會具有零成本）的成本邊緣來連接。

Answer 2

直接航班文件產生一個圖。節點是機場。邊緣位於有直飛航班的機場之間，並說每條邊都有重量。您想要找到A和B之間的所有簡單路徑，並且可能最終會收集路徑集合。您可以只對圖形進行深度優先搜索。編碼圖的一些常見方式是鄰接列表（即，對於每個節點，存在邊的節點的列表）;以及其他編碼方法。或N×N矩陣（對於N個節點）位置（i，j）中的值告訴你節點i和節點j之間邊緣的成本。

鑑於該數據結構。您可以使用從節點A開始的深度優先搜索並終止於節點B.您需要確保阻止算法重新訪問已經在當前路徑上的節點以防止循環。

Answer 3

經典問題Shortest path problem。如果你正在尋找算法，也有在維基百科頁面中列出的幾個選項，或者有算法，如ACO的選項，但它取決於使用情況和如何提供解決方案。

爲清晰起見，請注意，這是一個在traveling salesman problem的變化，結果是NP-complete。