Calculating/displaying the minimum cost for robot (position) to move on 2D grid (array)

I am currently working on an assignment question that calculates the cost of movement for a robot (position x, y).

We are given the dimensions of a 2D grid (2 dimension array) with several obstacles (symbol ##). Below is a sample grid. We're also given the starting position of the robot. At the current position it has a 'cost' of 00 (stationary).

.................................................. ........................................##........ ........................................##........ ........................................##........ ..........######################################.. ........................................##........ ........................................##........ ........................................##........ ....################..........00........##........ ....################....................##........ ....################....................##........ ....################....................##........ ........................................##........ .................................................. ..................................................

What is required in the assignment is to calculate the cost of each grid that is unknown (..) so it shows the cost the robot has to make in 开发者_如何学运维order to travel to that position.

Horizontal movements +2 to the cost of the previous grid.

Diagonal movements +3 to the cost of the previous grid.

The robot can't cross and obstacle and must go around it.

Each value must have the minimum cost (eg: less cost to travel diagonally than horizontally and vertically).

Below is the result we should have (only displaying the last two digits of cost with some values omitted so it is more readable):

http://i.stack.imgur.com/JiDl1.png

Right now I'm having trouble visualizing/tackling the problem. We've been told that it is 'morally like the bubble sort algorithm' where each time there is a new minimum cost is found, everything is recalculated.

Apologies if this is terribly confusing, any suggestions (code or pseudocode would be greatly welcome)

---

Imho, the easiest way to visualize path-problems is as a connected network of nodes (graph), where the neighbour nodes (squares the robot can move into from current position) are connected to each other with weighed edges (weight being the movement cost between the nodes).

N     @     N -2- N -2- N
|\         /|\   /|    /
2  3     3  2  3  2  3
|    \ /    |/   \|/
N -2- N -2- N -2- N     @

N = node, numbers and lines are edges with weights, @ is an obstacle

Djikstra's algorithm was already suggested, for even more options see for example http://en.wikipedia.org/wiki/Shortest_path_problem. Binary min heap works good as the priority queue. (afaik, A* + binary min heap is used in realtime games a lot because of the speed).

Edit: I suggested A* earlier, but come to think of it, it wouldn't work for single-source shortest paths -problem that good.