-2

I'm trying to implement Dijkstra's algorithm in order to find the shortest path between 2 points in a grid (x,y) but the problem is that I can only move up, down, right and left.

I have an ArrayList containing the x and ys of the points I need to pass on and another ArrayList of the points that are obstacles on the grid, I'm trying to write a function that returns an ArrayList of the movement needed in order to finish all the path.

In example: 1,1,1,2,3,4,1.. 1 being right 2 being left and 3 being up and finally 4 being down.

Can you please provide me with some hints and/or examples.

Basel JD
  • 275
  • 3
  • 17
  • 1
    For subgraphs of grids with unit length edges, you should not be using dijkstra; use BFS instead. The reason is that a priority queue would give you the exact same frontier as a simple queue. – G. Bach May 23 '14 at 13:34
  • @G.Bach I agree. A* search is one BFS (best-first search) algorithm. – Daniel May 23 '14 at 13:36
  • 1
    @Daniel Actually A* is an informed dijkstra (you get dijkstra when using A* with h(v)=0 for all v) – amit May 23 '14 at 13:41
  • I don't get what the first list is. If it's a list of points you must pass on, the problem sounds more like a traveling salesman problem. – Maurice Perry May 23 '14 at 13:44
  • @amit I thought that was the second list – Maurice Perry May 23 '14 at 13:46
  • 2
    Not sure why this question is being upvoted. Answering it in a comment and then deleting it should've been way enough, questions like this have been asked [dozens](http://stackoverflow.com/questions/23716285/shortest-path-on-a-grid-with-obstacles) [of](http://stackoverflow.com/questions/2311486/how-to-calculate-the-shortest-path-between-two-points-in-a-grid) [times](http://stackoverflow.com/questions/19463547/shortest-path-algo-unweighted-graph). All you need to do is search for "grid shortest path". – G. Bach May 23 '14 at 13:51
  • Maurice and amit are right though, your question could be interpreted to mean "I've got the graph, then I've got this set of vertices I must pass through, and another set of vertices I cannot pass through". Is this what you mean? – G. Bach May 23 '14 at 13:56
  • Basel, please clarify, does "an ArrayList containing the x and ys of the points I need to pass on" mean you have to visit all of those? Or is it just the opposite of a list of obstacles? (ie, list of walkable tiles) – harold May 23 '14 at 13:56
  • 1
    You know you should use Dijkstra's - okay, so where's the problem? It's a pretty straight-forward application of Dijkstra's and it should be pretty simple to convert any generic pseudo-code to Java code for your problem, and you could probably find Java code solving this exact problem if you were to look for it. Please try to ask more specific questions regarding the problems you're facing. – Bernhard Barker May 23 '14 at 14:24

1 Answers1

2

First off, know that Dijkstra's algorithm is for weighted graphs traditionally. It could still work with unit edges (all weight 1) but it may not be your most efficient solution.

Either way, whichever algorithm you use, you will need to treat your grid as a graph. To do this, make a set of edges. If there are no restrictions beyond "no diagonals" then your edges will be the connection between each point and its neighbors above, below, and next to it. You can then operate on the graph by iterating over the edges and points on the graph.

Adam Yost
  • 3,616
  • 23
  • 36