Once again having a problem with path finding this time The Dijkstra's
I have read Dijkstra's and its application on a various number of sites. It's mostly explained for a Graph and finding out the shortest path to all nodes from a source node.
What I am unable to figure out is how to use Dijkstra's for path finding on a grid as explained on Wikipedia picture.
since on a grid we have a single destination and we have to figure out the shortest distance to it from the source. I am unable to relate it to the Dijkstra's on a graph. There are no tiles to be marked as INFINITY or to compare the distance with other path's/Nodes.
The question in short is how do we proceed using Dijkstra's to find a path in grid using the actual graph algorithm for which this algorithm is defined. Do we proceed like BFS and call it Dijkstra's for a grid or is there a difference? because I am unable to figure out any :/
Thank you :)
In order to apply dijkstra's algorithm in a grid there is no need for any modifications, since a grid is a graph in which a node (cell) has 4/8 children (depending on your connectivity) which are the neighbors. Therefore, all you have to do is: choose your root node (where to start), assign it value 0 and then evaluate the 4/8 neighbors, using as cost just 1 (or sqrt(2) if for the 4 diagonal neighbors if you are using 8-connectivity). This root node has to be labeled as visited and the neighbors evaluated are labeled as open. Then, you pick the node(cell) in evaluated that has a minimum value (in this case, all of them will have value 1) so you choose any of them. When adding the neighbors to the open list, it will happen that some of these neigbors are already visited, so you just ignore them. If the are already in the open list, you recompute their value and if they are unvisited, you compute their value and add them to open, and mark the current node as closed.
In fact, you will see that there is no difference at all with the generic Dijkstra's algorithm you have been reading for graphs.
NOTE: in order to be efficient when getting the minimum of the open list, it is recommended to use a heap (usually a binary heap) instead of running the min function along all the open nodes at every iteration.
