在动态权重图中找到最短路径

Question

我有以下场景:

我想找到两个城市之间的航班:A和B.没有从A到B的直飞航班; 所以,我需要找到成本最低的转机航班.

此外,机票不固定.这取决于我购买它的时间; 例如,如果我早买它,价格会更便宜.

而且,时间也影响了飞行; 例如,5月31日上午7点只有一班从C到D的航班.如果飞机在5月31日上午8点从A飞到C,我会错过航班.因此,我将城市表示为图的顶点.如果从A到B的航班有效,则路径AB存在.权重将是机票费.

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

谢谢

Answer 1

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

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

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