Find the shortest way in 2D array

Question

I am searching for an algorithm that allow me to find shortest way between the points 'T' and 'C'.

##############################
#.....T........###############
#.......................#.#..#
#.#######################.#..#
#.....##......##......#....###
#...####..##..##..##..#..#...#
#.........##......##.....#.C.#
##############################

I have been recently introduced to this kind of problems. I found an almost similar problem to this one here which was solved with Lee-Algorithm, but couldn't apply it for my case.

Some other friends recommended me to use a recursive algorithm, but I still not familiar with that.

Can you please give me a general idea how this should be solved and what kind of algorithm should be applied?

Answer 1

The problem you're trying to solve is known as path finding.

---

One of the recommended algorithms is A*.

In A*, the value of a cell is the sum of two parts - the actual cost taken to get to that cell, and an expected cost to reach the destination from that cell (called a 'heuristic'). For the heuristic, we can simply use something called the Manhattan distance, which is the difference in x plus the difference in y.

The idea is then to keep a priority queue of the possible candidates (we could keep the coordinates of a cell, and the path taken to get there, to represent a candidate), allowing us to pick the one we expect to be in the shortest path at each step. We then start off with the source cell in this priority queue, then we remove the minimum value, checking if it's the destination, and then adding all its unexplored neighbours back into the priority queue, and continue this way until we get to the destination.

To keep track of unexplored neighbours, we could keep boolean matrix of the same size, initialized to all false values, and setting each value to true if it gets explored (and then obviously checking whether the corresponding cell is set to true to check if a cell is explored or not).

---

Another recommended approach is Dijkstra's algorithm, but this is actually for weighted graphs (where two steps may have different costs), although it would work for this as well. We'd actually preferred breadth-first search (BFS), which can be thought of as a special case of Dijkstra's algorithm.

In BFS, we keep a queue consisting of all possible candidates, then dequeue an element from the queue, check if it's the destination, and enqueue all its unexplored neighbours, and continue this way until we get to the destination.

---

Dijkstra's algorithm / BFS would be the simpler approach, but would also take longer to find the shortest path.

You have to be careful with A* though, as picking a heuristic that's not 'admissible' (meaning it can overestimate the cost to the destination) would be problematic - but the Manhattan distance mentioned above doesn't have this problem.

_{(animations courtesy of Wikipedia)}

Answer 2

The idea is to fill all points that you can reach from T in one step and keep a trace of these; then all points you can reach in two steps, and so on, until you reach C.

Mark all the points that you visit and keep a list of the ones reached in K steps. Scan the list, mark all unvisited neighbors and update the list to form the "K+1" list.

##############################
#54321T12345678###############
#65432123456789012345678#5#..#
#7#######################4#..#
#89012##901234##123456#1234###
#901####89##45##01##67#12#567#
#012345678##567890##78901#6C.#
##############################

In the given example, C is reached in 47 steps, four points are unreachable and one is reached after C.