- #1

mathmari

Gold Member

MHB

- 5,049

- 7

I am looking the following:

The board of a game is an $M \times N$ board with squares, where the starting point is on left - in position $(0, 0)$ - and the finish is in the lower right - in position $(M-1, N-1)$. Each square contains a positive number that describes the cost of moving to pass through this specific square. Design and analyze an algorithm that finds the path to minimum cost from start to finish considering that we can move up, down, right or left. For example, in the table below the minimum cost is 35 and is given by the designed path.

We convert this table into a graph, specifically a weighted graph with weights the cost of each square. In this way the problem will be to find the shortest path of the graph, right? :unsure:

That graph that we get is not directed, is it? :unsure: