我在我的应用程序中使用了稍微修改过的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秒)，因为首先计算所有邻居是一个接一个，因为它不是“尝试”以其他方式到达目标目的地...
您能推荐我其他适合的算法吗？
我一直在寻找:
简单的例子在这里...)
拥有(只是可选的东西)会很棒:
-选择偏好最少的公交车更换次数或最少的时间
-选择其他方式的选择(如果旅行时间相似)
谢谢你的提示
最佳答案
听起来您在寻找A*。这是Djikstra的变体，它使用启发式方法来加快搜索速度。在某些合理的假设下，A *是最快的最优算法。只要确保始终break ties towards the endpoint即可。
还有一些A *的变体，它们可以在更短的时间内提供接近最佳的路径。例如，参见here和here。
Bellman-Ford(如您的问题中所建议的)往往比Djikstra或A *都慢-它主要用于存在负边权重的情况(此处未提供)。
关于java - Dijkstra算法的替代方案-图形中的最短路径，公交路线，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12665303/