CODEWITHSUNDEEP
c#algorithmmatrixpathlua
ByoTic
ByoTic

Reputation: 333

Algorithm to find the shortest path in a matrix

I tried to find an algorithm for the following problem, but I couldn't.

you have a matrix, 10X6 if it matters. (10 on x dimension 6 on y dimension). the algorithm receives 2 point, the opening point and the target point. the array is full of 0's and 1's and it should find the shortest path of 1's between them, and return the first point in this path (the next point in the way to the target). But here's the catch:

each point can get the value only of the following points:

  1. the point above it.
  2. the point underneath it.
  3. the point left to it.
  4. the point right to it.

and to make things even harder: for every point, the value of other point may be different. for example:

  1. the opening point is 0,0. the value of 0,1 is 1;
  2. the opening point is 0,2. the value of 0,1 is 0.

I can calculate the value so it shouldn't matter for you... So I thought the only way to solve it is with recursion because of the last condition but if you find another way, you're welcome.

The solution should be in LUA, C# or JAVA.

Upvotes: 2

Views: 16334

Answers (1)

Thomas
Thomas

Reputation: 1090

You can simply interpret your matrix as a graph. Every cell (i,j) corresponds to a node v(i,j) and two nodes are connected if an only if their corresponding cells are neighbors and both are set to 1.

The example matrix below has the four vertices v(0,0), v(0,1), v(1,0), and v(1,1), with edges {v(0,0),v(0,1)} and {v(0,1),v(1,1)} (the vertex v(1,0) is isolated).

1 1
0 1

As your graph is unweighted, you can simply use a breadth-first search (BFS) to find a shortest path. For pseudocode see: http://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

Your restriction that every entry in a matrix only knows its neighboring entries does not matter. When talking about graphs, this means that ever vertex knows its neighbors, which is exactly what you need in the BFS. Using a different graph when searching from different starting points does not make the problem harder either.

Just two comments to the poseudocode linked above:

  1. It only checks whether there is a connection or not. If you actually want to have the shortest path, you need to change the following. When a new vertex u is added to the queue when seen from its neighbor t, you have to store a link at u pointing to t. When you finally found your target, following back the links gives you the shortest path.

  2. Using a set to store which elements are already visited is inefficient. In your case, just use a boolean matrix of the same size as your input matrix to mark vertices visited.

Upvotes: 4

Related Questions