Dijkstra算法备选方案-图中最短路径，总线路线

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 (我看不见) 直截了当的例子)

最好有(只是可选的东西)：-选择选择最少的巴士改变或最小的时间-选择寻找替代方式(如果旅行时间是相似的)

谢谢你的小费

Answer 1

听起来你在找*。这是贾克斯特拉的一个变体，它使用启发式来加快搜索速度。在某些合理的假设下，A*是最快的最优算法。只需确保总是断开与端点的联系。

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

行李员-福特 (如你的问题中所建议的)往往比贾克斯特拉或A*慢--它主要用于负边权，而这里没有。

Answer 2

也许是一种算法？请参阅：算法

也许是收缩等级？见：等级制度。

收缩层次结构由非常好的、非常快速的开放源码路由机(OSRM)实现：

http://project-osrm.org/

通过OpenTripPlanner：

http://opentripplanner.com/

A*由多个路由系统实现。用谷歌搜索就行了。

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

Answer 3

算法将非常适合这一点；它通过使用启发式方法获得更好的性能。

下面是一个简单的入门教程：链接