For example, one might think of the array as a topographical map, and the cell weights as altitudes, so your path will tend to get to the goal by avoiding the mountains. If the weights were all 0 or 1, this also could encode a maze, so this is a generalization of maze traversal. A graphical example depicting such a maze is available online. In this case, there are walls blocking every possible path through the maze, so the solution breaks through as few walls as possible to get to the goal.
This is a relatively straightforward application of the priority-first search method described in the text. Your task is to adapt that algorithm to this situation in a clean, efficient, and elegant manner. You probably will want to output a Postscript program to view your solution in a manner similar to the example. A sample Postscript program (which shows a nonoptimal path through a 7-by-7 maze with random weights) is available online, to get you started.
Evaluate how fast your program is by seeing how large a maze it can solve in a fixed amount of time. Turn in your documented source code and runs that take 1 second, 2 seconds, and 10 seconds. Show the value of N, the number of cells that you touched in trying to compute the solution, and the total cell weight on the path computed. How big do you think these last numbers are, as a function of N? Also turn in a drawing of a solution for a 25-by-25 maze. with random weights.
Advice. Not much creativity is required in this assignment. Pay attention to the next-to-last paragraph above and to pages 455 and 463 in the text.