java - 适用于 500 多个航路点/节点的最短路径算法(例如 Dijkstra 算法)？

Question

我在这里询问了最短路径算法: 2D waypoint pathfinding: combinations of WPs to go from curLocation to targetLocation

(要了解我的情况，请阅读该问题以及本问题。)

看来 Dijkstra 最短路径算法能够满足我的需要。但是，我的路线图中大约有 500 到 1000 个节点。

到目前为止，我所看到的实现将节点数量限制在 50 个以下。我的问题是:我是否仍然应该使用 Dijkstra 最短路径算法，或者其他替代方案？ Java中有没有实现？

Answer 1

只有尝试过才知道。

1000 个节点实际上并不算多。 Dijkstra 算法在边的数量上具有线性复杂度，并且边的数量在最坏的情况下是节点数量的二次方。从您对图表的描述来看，很难判断有多少条边，但即使是完整的 1.000.000 也不是很大。

主要问题是您是否使用 priority queue 正确实现它.

编辑:Russell & Norvig ，第二版，在第 3 章和第 4 章中描述了一组通用搜索算法。他们所谓的统一成本图搜索本质上是 Dijkstra 算法。如果您按照他们的说明进行操作，则在需要时可以轻松地将算法扩展到 A* 搜索。