Lee’s algorithm: http://en.wikipedia.org/wiki/Lee_algorithm
It’s essentially a BF search, here’s an example: http://www.oop.rwth-aachen.de/documents/oop-2007/sss-oop-2007.pdf
To implement it effectively, check my answer here: Change FloodFill-Algorithm to get Voronoi Territory for two data points? – when I say mark, you mark it with the number on the position you came from + 1.
For example, if you have this grid, where a * = obstacle and you can move up, down, left and right, and you start from S and must go to D, and 0 = free position:
S 0 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
You put S in your queue, then “expand” it:
S 1 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
Then expand all of its neighbours:
S 1 2 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
And all of those neighbours’ neighbours:
S 1 2 3
* * 3 *
* 0 0 *
0 0 * *
* 0 0 D
And so on, in the end you’ll get:
S 1 2 3
* * 3 *
* 5 4 *
7 6 * *
* 7 8 9
So the distance from S to D is 9. The running time is O(NM), where N = number of lines and M = number of columns. I think this is the easiest algorithm to implement on grids, and it’s also very efficient in practice. It should be faster than a classical dijkstra, although dijkstra might win if you implement it using heaps.