航班时间表算法

Question

3

我有一份所有直达航班的清单。现在我想要获取从A到B并带有中转的航班信息。请问这个问题需要使用什么样的算法或数据结构？谢谢。

- fastcodejava

2

你是否关心连接数量、整体旅行时间和最小化中转时间？ - jball

1

这听起来像是一道作业题？ - Ryan K

2

这个对你有用吗？https://dev59.com/1XVD5IYBdhLWcg3wL4iM - stacker

3个回答

3

直达航班文件会生成一个图。节点是机场，边是直接有航班的机场之间的连线，并且每条边都有一个权重。您想要找到 A 和 B 之间的所有简单路径，并可能希望最终得到一组路径。您可以对该图进行深度优先搜索。

编码图的几种常见方式是邻接表（即对于每个节点，列出其相邻节点列表）或 NxN 矩阵（对于 N 个节点，位置 (i, j) 上的值告诉您节点 i 和节点 j 之间的边的成本）。

在给定这些数据结构的情况下，您可以从节点 A 开始使用深度优先搜索并在节点 B 处终止搜索。您需要确保防止算法重新访问当前路径上已经存在的节点，以避免出现循环。

- vicatcu

1

经典问题最短路径问题。如果您正在查看算法，维基百科页面中列出了一些选项，或者可以选择ACO等算法，但这取决于用例和解决方案应如何提供。

为了清晰起见，请注意这是旅行商问题的变体，因此是NP完全问题。

- gpampara

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jerry Coffin · Accepted Answer

基本上，这是遍历图的问题，其中每个出发或到达都将是一个节点，每个航班都将是一条边。您通常会为边分配成本--根据用户的喜好，“成本”可能是机票费用（以获得最低价格）或飞行时间（以获得最短飞行时间）。在同一个机场进行出发和到达将通过成本为停留时间的边连接起来（从价格的角度来看，该边通常具有零成本）。