2

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?

Community
  • 1
  • 1
Tom
  • 8,536
  • 31
  • 133
  • 232
  • Do I understand correctly that you want to retrieve *all* paths from *x* to *y*, ordered by length, rather than just the shortest one? – Fred Foo Mar 08 '11 at 15:55
  • @larsman that was what I wanted originally, but it appears to be too much asked - just the shortest one seems fine since I can repeat the process without the earlier returned nodes. – Tom Mar 08 '11 at 20:48
  • A simple extension of A* can be used to backtrack through all paths: http://stackoverflow.com/questions/5204444/how-to-find-the-best-three-routes-using-a-algorithm/5204532#5204532 (though the extension may be non-trivial in Java). This doesn't work with Dijkstra/graph A*, though. – Fred Foo Mar 08 '11 at 20:54

3 Answers3

5

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.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • I wish I could try it with a proven Java library. Do you happen to know of any such implementations of the Dijkstra's or A* algorithm in Java? The one I found had a hardcoded limitation of 26 nodes and it was just a prove of concept. – Tom Mar 08 '11 at 20:50
  • **Not tested**: try out the Java sample code for Russell & Norvig, http://code.google.com/p/aima-java/. You're looking for uniform-cost graph search (see my updated post). – Fred Foo Mar 08 '11 at 21:01
  • @larsmans I take it there is no existing library then? I might sound lazy for not immediately trying to create my own implementation but considering that 1) this path-finding is only a minor part of my project and 2) I have no experience/knowledge at all in this field --- I believe I really should use an already proven library – Tom Mar 08 '11 at 21:16
  • @Tom: The Jung library (http://jung.sf.net) includes Dijkstra's algorithm, but I thought you didn't want a full-blown framework. You're unlikely to find a much smaller library, since graph representations vary widely. – Fred Foo Mar 08 '11 at 21:20
  • @larsmans, I'm trying to use the jung library but cannot find a tree map implementation that is meant for dense graphs (they all state that they are suitable only for sparse graphs), see http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/class-use/Hypergraph.html#edu.uci.ics.jung.algorithms.shortestpath - any idea why? – Tom Mar 08 '11 at 21:49
  • @Tom: this is material for a new question. I don't use Jung extensively myself. – Fred Foo Mar 08 '11 at 22:24
2

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.

biziclop
  • 48,926
  • 12
  • 77
  • 104
  • Does the A* algorithm apply for this amount of waypoints in contrary to Dijkstra's? – Tom Mar 08 '11 at 15:36
  • @Tom A* is basically an improved variant of Dijkstra's where the next candidate is selected using a distance heuristic (in your case, the direct distance between two waypoints) rather than in no particular order. So yes, it is meant to be used in cases where Dijkstra's algorithm is too slow. – biziclop Mar 08 '11 at 15:38
  • that doesn't answer whether it is applicable for a situation with 500-1000 nodes, or if dijkstra's is. – Tom Mar 08 '11 at 15:42
  • @Tom Whether it is applicable depends on what sort of running time is acceptable for you and how good your implementation is. I don't know anything about that, so I can't give you a definite yes/no answer. All I can say is that A* is much faster than Dijkstra if you can find a suitable (admissible) heuristic and in your case, such a heuristic does exist. – biziclop Mar 08 '11 at 15:46
  • I guess a shortest path calculation from node1 to node2 should be calculated within 100 milliseconds when there are 1000 nodes each having a direct connection to an average of something around 5 nodes (if that matters). – Tom Mar 08 '11 at 15:50
0

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?

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • I don't have anything in mind. I'm not experienced in this field at all, which explains my questions. I'm looking for an already implemented algorithm in Java that can find the shortest path in a 2D world with 500+ nodes. – Tom Mar 08 '11 at 15:38
  • http://stackoverflow.com/questions/2733051/bellman-forge-dijkstras-prims-algorithm-kruskals-directed-acrylic-graph – Micromega Mar 08 '11 at 16:04
  • http://stackoverflow.com/questions/3818079/why-use-dijkstras-if-breadth-first-search-can-do-the-same-and-fast – Micromega Mar 08 '11 at 16:11