5

我有以下情况：

我想找两个城市之间的航班：A和B。没有从A到B的直飞航班；所以，我需要找到一个成本最低的中转航班。

另外，机票也不是固定的。这取决于我购买它的时间；例如，如果我早点购买，价格会更便宜。

此外，时间也会影响飞行；例如，5 月 31 日早上 7 点从 C 到 D 只有一班航班。如果飞机在 5 月 31 日早上 8 点从 A 飞到 C，我会错过航班。出于这个原因，我将城市表示为图的顶点。如果存在从 A 到 B 的有效航班，则路径 AB 存在。重量将是机票费用。

对我的问题有什么想法或建议吗？

谢谢

4

2 回答 2

4

我曾经回答过一个非常相似的问题，我很确定在这里可以使用相同的想法。这个想法是使用路由算法，专为互联网路由器设计 - 这是动态且不断变化的。为其设计的算法是距离矢量路由协议。

建议的实现基本上是 Bellman-Ford 算法的分布式版本，一旦每条边的权重发生变化，它就会自行修改，以获得新的最优路径。

请注意，该算法有缺点，主要是计数到无穷大问题。

于 2013-05-31T15:05:11.377 回答
1

处理在正确时间不在正确位置的通常方法是使节点代表特定时间的特定位置。然后从 C 到 D 的航班在 5 月 30 日晚上 9 点起飞并在 5 月 31 日早上 7 点到达，对应于从节点 C_May30_9PM 到 D_May31_7AM 的弧。您还需要与等待相对应的弧线，例如 D_May31_7AM 到 D_May31_8AM。

我不确定您所描述的详细程度关于购买门票有什么要说的。

于 2013-05-31T14:36:03.860 回答