500+个航路点/节点的最短路径算法(例如Dijkstra)? [英] Shortest path algorithm (eg. Dijkstra's) for 500+ waypoints/nodes?

问题描述

我在这里询问了最短路径算法: 2D航路点寻路:将WP组合到从curLocation转到targetLocation

I've asked about a shortest path algorithm here: 2D waypoint pathfinding: combinations of WPs to go from curLocation to targetLocation

(要了解我的情况，请同时阅读该问题和该问题.)

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

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.

到目前为止，我所看到的实现将节点的数量限制在50个以下.我的问题是:我是否仍应使用Dijkstra最短路径算法或替代方法? Java是否有任何实现?

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?

推荐答案

直到尝试为止，您都不知道.

1000个节点实际上并不是那么多. Dijkstra的算法在边数上具有线性复杂度，而边数在节点数上则是二次方.从对图形的描述中，很难说出有多少条边，但是即使是全部1.000.000也不是很大.

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.

修改: Russell& Norvig ，第二版，在第3章和第4章中介绍了一组通用搜索算法.它们所谓的统一成本图搜索本质上是Dijkstra的算法.如果遵循他们的指示，可以在需要时很容易地将算法扩展到A *搜索.

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.

这篇关于500+个航路点/节点的最短路径算法(例如Dijkstra)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！