文章/答案/技术大牛

发布

社区首页 >问答首页 >在具有动态权的图中寻找最短路径

问在具有动态权的图中寻找最短路径
EN

Stack Overflow用户

提问于 2013-05-31 22:23:58

回答 2查看 3.5K关注 0票数 5

我有以下场景：

我想找两个城市之间的航班:A和B。A和B之间没有直达航班，所以我需要找一个最便宜的转机航班。

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

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

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

谢谢

shortest-path

algorithm

graph

graph-algorithm

回答 2

Stack Overflow用户

回答已采纳

发布于 2013-05-31 23:05:11

这个想法是使用一种路由算法，专为互联网路由器而设计-这些路由器是动态的，不断变化。为此设计的算法是。

请注意，该算法有回调，主要是count to infinity problem。

票数 4

Stack Overflow用户

发布于 2013-05-31 22:36:04

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

我不确定在你所描述的细节水平上，关于买票有什么可说的。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/16859624

复制

相似问题

问在具有动态权的图中寻找最短路径
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在具有动态权的图中寻找最短路径EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在具有动态权的图中寻找最短路径
EN