航班时刻表算法

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。