确定最快路线的算法？
确定最快路线的算法？
提问于 2011-12-19 16:37:03
假设我们从1到5，最短的路线是1-4-3-5 (总计: 60公里)。
我们可以使用迪克斯特拉算法来做到这一点。
现在的问题是，由于交通堵塞或其他因素，最短的路线并不总是最快的。
例如：
- 众所周知，1-2有频繁的交通堵塞，所以应该避免。
- 突然，一场车祸发生在4-3，所以它也应该避免。
- 等等..。
所以也许我们可以在1-4-5号公路上行驶，因为没有交通堵塞/事故，所以我们可以在5点到达。
这是一般的想法，我还没有想过更多的细节。
有什么算法可以解决这个问题吗？
回答 5
Software Engineering用户
回答已采纳
发布于 2011-12-19 19:58:17
既然你把交通拥堵带入了画面，小心不要被布雷斯悖论抓住。如果每个人都选择了最优路径，那么每个人的出行时间就会变得更糟。
Software Engineering用户
发布于 2011-12-19 16:42:36
是: Dijkstra
Dijkstra也同样适用于这种情况。
你只是用时间而不是距离作为每一个弧线的重量。
Software Engineering用户
发布于 2011-12-19 16:42:48
是。Dijkstra的算法将解决这个问题。
在您的情况下的问题是，您自动假定最短的路径等于距离，而实际上，它更恰当地等同于走一条路线的成本。
如果一条路径有一个路障，那么它的代价应该更高，而且算法仍然适用。
页面原文内容由Software Engineering提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://softwareengineering.stackexchange.com/questions/125966
复制相关文章
相似问题
腾讯云开发者
