Shortest path algorithm (eg. Dijkstra's) for 5

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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?