java - Dijkstra algorithm alternatives - graph, bus routes 中的最短路径

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* .它是 Djikstra 的一个变体，它使用启发式方法来加速搜索。在某些合理的假设下，A* 是最快的最优算法。只要确保始终 break ties towards the endpoint .

还有 A* 的变体，可以在更短的时间内提供接近最优的路径。参见示例 here和 here .

---

Bellman-Ford (如您的问题中所建议) 往往比 Djikstra 或 A* 慢 - 它主要在存在负边权重时使用，而此处没有。