2D array path finding

a-staralgorithmdijkstramultidimensional-arraypath-finding

I want to find the minimum weighted path between two indexes of an 2D array. I have tried to implement Dijkstra's shortest path algorithm and A* but I couldn't. There is an example below. I want to give starting and ending point of path and the path should be returned by the algorithm.

0 2 5 8 8 9

5 1 2 7 9 8

9 8 2 5 7 8

8 8 2 2 2 9

9 7 6 3 2 7

8 8 6 5 3 5

Can anybody reccomend other algorithms or guide me about the algorithms?

I am working on this for days and I don't think it is a challenging problem at all. But I lost my temper and cannot think healty. For example, I even could not understand whether a* and dijkstra's shorthest path is directly related to what I want to do. Or they work for 0 and 1 like structures that if there is a wall you cannot pass from there if not you can. In my problem you can pass from anywhere but I want to find the least cost path etc.

Best Solution

Model your problem to "fit" the design of the algorithms:
Try to first build a graph out of your grid, it might help you to understand these algorithms and implement them. Since both these algorithms are designed for graphs [which can model a grid], I think you might find it easier to understand the algorithms when you implement them on "general graphs", and build a graph for your specific problem.

Your graph will be G = (V,E), where V = { (i,j) | (i,j) is a possible index) } [all squares in the grid], and E = { (v,u) | v and u are adjacent vertices on the grid }.
You also need a weighting function on edges. w:E->N. it will be w(u,v) = matrix[v.x][v.y] [the value of the matrix in the entree matching to v].

Now, implement dijkstra in your facorite language, for the graph G. The weight of your shortest path is the weight of the path found by dijkstra + matrix[source.x][source.y] [because we did not add this value to any edge on the shortest path].

To find the actual path, and not only the weight of it - you will also need to hold a map:V->V, which will map from each vertex - to the vertex which discovered it. Similar to the idea explained in this post.

Start with the simpler Dijkstram and later move on to A*:
I'd start with dijkstra and not A*, since A* is basically an informed dijkstra - so you should be able to implement dijkstra before you implement A*, since it [dijkstra] is simpler.

Other algorithms for shortest path:
You should also know, that there is also another common shortest path algorithm - the well-known Bellman-Ford [which can handle negative weights as well, unlike dijkstra].