# 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.