Shorthest path with obstacles

Question

We are given N x N minefield (2d array), the coordinates where the mines are are given in another M x 2 array. what is the best algorithm for finding the shortest path from the upper left angle to the lower right angle without stepping on a mine in the minefield?

Answer 1

This is a shortest path problem, and can be solved by reducing the problem to a graph:

G=(V,E)
V = { (x,y) | for all x,y such that (x,y) is not a mine } 
E = { ((x1,y1),(x2,y2)) | (x1,y1) is adjacent to (x2,y2) }

Now when you have the graph, you need to apply some shortest path algorithm.

• The simplest one would be BFS (since your graph is unweighted). This is pretty simple to implement and always finds the fastest path if such exist.
• A bit more complex approach would be bi-directional BFS. In here, you do a BFS from the start node (0,0) and the end node (n,n) - and finish when the two fronts of the algorithms find each other. The path is than given by concatting the first with the reverse of the 2nd. This approach is likely to be faster than regular BFS, but a bit harder to program.
• You can use informed algorithm such as A* search algrotihm, with manhattan distances as heuristic functions (assuming you can go only up/down/right/left, no diagonals). This will likely be faster than both alternatives, but is harder to code.

---

I would start from BFS if you have no experience with it, and later move on to more advanced algroithms.

In pseudo code:

BFS(x_source,y_source, x_target,y_target):
   queue = empty new queue
   queue.add(Pair(x_source,y_source))
   parent= new dictionary
   parent.add(source, None)
   while (queue.empty() == false): 
      curr = queue.dequeue()
      currX = curr.first
      currY = curr.second
      if (currX == x_target && currY == y_target)
          return getPath(dict, curr)
      for each neighbor u of curr: //u is a pair of (x,y) coordinates of adjacent cell
          if u is not a key in parent:
             parent[u] = curr
             queue.add(u)

The above BFS fills the parent dictionary, and the path is returned by the following getPath() function, which basically traverses the dictionary until it finds the "root" (which is the original source node).

getPath(dict, target):
   sol = [] //empty list
   curr = target
   while curr != None:
         sol.addFirst(curr)
         curr = dict.get(curr)

Answer 2

This problem can be solved using dijkstra algorithm. First remove all incoming paths to mine node, then proceed with shortest path to the bottom right corner node.