迪杰斯特拉算法的替代方案 - 图中的最短路径，公交路线

Question

我在我的应用程序中使用了略微修改的Dijkstra算法，但它非常缓慢，我知道一定有更好的方法。我的输入数据是公交车站点，并指定了它们之间的旅行时间（约400个节点和800条路径，最大结果深度= 4（最多4次公交换乘或没有）。

输入数据（公交路线）：

bus_id | location-from | location-to | travel-time | calendar_switch_for_today
XX | A | B | 12 | 1
XX | B | C | 25 | 1
YY | C | D | 5  | 1
ZZ | A | D | 15 | 0

dijkstraResolve(A,D, '2012-10-10') -> (XX,A,B,12),(XX,B,C,25),(YY,C,D,5) 
=> one bus change, 3 bus stops to final destination
* A->D cant be used as calendar switch is OFF

作为一种更复杂的图形，例如主城市（节点）与不同城市有170个连接的情况下，Dijkstra算法会变慢（需要超过5秒），因为它首先逐个计算所有邻居，而不是“尝试”通过其他方式到达目标地点...。

你能推荐我其他适合的算法吗？

我看了一下：

- http://xlinux.nist.gov/dads//HTML/bellmanford.html（速度更快吗？） - http://jboost.sourceforge.net/examples.html（这里没有直接的例子...）

如果有以下可选项，将会很棒： - 选择最小数量的公交换乘或最短时间 - 查看替代路线（如果旅行时间相似）

感谢您的建议。

- Martin V.

---

你如何知道有更好的方法？ - hakre

为什么不使用A*算法？该算法通过使用启发式算法实现更好的性能：http://www.policyalmanac.org/games/aStarTutorial.htm。 - LanguagesNamedAfterCofee

@hakre：因为有很多更好的方法，例如在前30个城市中，80%的公交换乘发生在那里，或者算法不应该处理返回原始位置的路线...我会看一下A*算法，谢谢。 - Martin V.

Answer 1

也许可以使用A*算法？参见：http://en.wikipedia.org/wiki/A-star_algorithm 也许可以使用缩减层次图算法？参见：http://en.wikipedia.org/wiki/Contraction_hierarchies。

缩减层次图算法被非常好的、非常快速的开源路由机OSRM所实现：http://project-osrm.org/，以及OpenTripPlanner：http://opentripplanner.com/。

A*算法被许多路由系统所实现。只需在Google上搜索即可。

OpenTripPlanner是一个多模式路由系统，并且据我所见，应该与您的项目非常相似。

- AlexBottoni

---

OpenTripPlanner对于这个特定的情况来说有点过于繁琐，但知道它的存在还是很好的，也许将来我们会使用它，如果它能给我们带来好处的话。 - Martin V.

Answer 2

听起来你正在寻找 A*。它是Djikstra的变种，使用启发式算法加速搜索。在一定的合理假设下，A*是最快的最优算法。只要确保始终 朝着终点打破平局。

还有一些A*的变体可以在更短的时间内提供接近最优的路径。例如，看看 这里 和 这里。

---

Bellman-Ford (正如您在问题中建议的) 往往比Djikstra或A*慢 - 它主要用于负边权的情况，而这里没有。

- BlueRaja - Danny Pflughoeft

Answer 3

对于这个问题，A*算法是一个很好的选择；它通过使用启发式方法来实现更好的性能。

这里有一个简单的教程，可以帮助你入门：链接

- LanguagesNamedAfterCofee