500 的最短路径算法（例如 Dijkstra's）航路点/节点？
我在这里询问了最短路径算法： 2D 路径点寻路：WP 的组合从 curLocation 到 targetLocation
（要了解我的情况，请阅读该问题以及本问题。）
看来 Dijkstra 最短路径算法能够满足我的需要。但是，我的路线图中大约有 500 到 1000 个节点。
到目前为止，我所看到的实现将节点数量限制在 50 个以下。我的问题是：我是否仍然应该使用 Dijkstra 最短路径算法或替代方案？ Java中有没有实现？
I've asked about a shortest path algorithm here:
2D waypoint pathfinding: combinations of WPs to go from curLocation to targetLocation
(To understand my situation, please read that question as well as this one.)
It appears that the Dijkstra shortest path algorithm would be able to do what I need. However, I have about 500 to 1000 nodes in my routes map.
The implementations I have seen so far limited the amount of nodes to something under 50. My question is: should I still use the Dijkstra shortest path algorithm, or an alternative? Are there any implementations in Java?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
只有尝试过才知道。
1000 个节点实际上并不算多。 Dijkstra 算法在边的数量上具有线性复杂度，并且边的数量在最坏的情况下是节点数量的二次方。根据您对图表的描述，很难判断有多少条边，但即使完整的 1.000.000 条也不是很大。
主要关心的是您是否使用 优先级正确实现它队列。
编辑：Russell & Norvig，第二版，在第 3 章和第 4 章中描述了一组通用搜索算法。他们所谓的统一成本图搜索本质上是 Dijkstra 算法。如果您遵循他们的说明，如果需要，您可以很容易地将算法扩展到 A* 搜索。
You don't know until you've tried.
1000 nodes isn't really that much. Dijkstra's algorithm has linear complexity in the number of edges and the number of edges is at worst quadratic in the number of nodes. From your description of the graph, it's hard to tell how many edges there are, but even the full 1.000.000 isn't very large.
The main concern is that you implement it properly, using a priority queue.
Edit: Russell & Norvig, 2nd ed., describe a set of generic search algorithms in chapter 3 and 4. What they call uniform cost graph search is essentially Dijkstra's algorithm. If you follow their instructions, you can extend the algorithm to A* search quite easily if the need arises.
度量二维世界中的最短路径查找是 A* 算法的教科书示例。您的启发函数应该是从每个航路点到目标的直线距离。
Shortest path finding in a metric 2D world is a textbook example of the A* algorithm. Your heuristic function should be the straight line distance from each waypoint to your target.
dijkestra 算法不是 prim 或 kruskal，当后者仅使用边缘时，它正在整体计算 mst。您还想到其他哪种算法？
dijkestra algorithm isn't prim or kruskal it is calculating a mst in whole when the latter only uses an edge. which other algorithm do u have in mind?