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

thinkyou 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].