在带有动态权重的图中查找最短路径

Question

我有以下情景：

我想找到两个城市A和B之间的航班。从A到B没有直达航班，因此我需要找到一条连接航班并且价格最低。

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

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

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

谢谢

- Thinh Phan

---

听起来像是一个相当简单的A*问题（你显然还必须在每个城市保留到达日期），但与其仅保留到达给定城市的最佳路径不同，您将不得不保留所有路径（尽管您可以删除那些比另一条路径到达时间更晚且更昂贵的路径）。 - Bernhard Barker

相关问题，虽然它最小化的是天数而不是成本。 - Bernhard Barker

Answer 1

我曾回答过一个非常类似的问题，我相信这里可以使用相同的思路。这个想法是使用一种针对互联网路由器设计的路由算法，这些路由器是动态的并且不断变化的。为此设计的算法是距离向量路由协议。

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

请注意，该算法存在缺点，主要是无限计数问题。

- amit

Answer 2

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

我不确定在您描述的详细级别上购买机票是否有太多可说的内容。

- David Eisenstat