Data Structures - Greedy Algorithm Graph Traversal

A map is provided as gray level image in raw format (available below) and the value at a point (pixel) is its height information. From a point, one can only travel in horizontal or vertical direction (edge) to its adjacent point. The cost of a horizontal or vertical shift between two adjacent points is their height difference, which corresponds to energy spent on the movement, e.g., cost(a, b) =1+|map(a)-map(b)| for adjacent points a and b. Compute the shortest path starting from top left corner point (0, 0) to all other points by using the greedy algorithm. The cost of a path is the sum of edge costs in horizontal and vertical directions. Input Map: a 2D array in row based order. It has W*H = 250*200 dots(points). Value at a position in the map: 1byte character (8bits) for height value, i.e., the height value ranges from 0 to 255. Output Map: (1) A grey level image to show the final direction to reach every point in the map. In detail, the value at each point shows the direction from its previous position to it on the shortest path. For example, at a point, you can use a number from 50, 100, 150, 200 to represent a direction among N(↑),E(→),S(↓),W(←). (2) Mark a path in another image file. (3) A txt file to display a value at each point that is the shortest path cost to the point.(For this one, as each node will take a sum, which the value near right down corner will be far greater then 255, so you can output this one as txt file and save the actual number) (4) Improvement: efforts to speed up the computation and reduce the memory are encouraged. For example, you can use additional arrays as the working space to register immediate values, use separate data structures such as link list, queue, and heap to reduce the computation complexity. [login to view URL] for input You can use [login to view URL] or start from scratch. 2 sample file output. In [login to view URL], the path is marked as 255, this file shows the path. In [login to view URL], the numbers represent the directions. 50 means ↑, 100 means →, 150 means ↓, 200 means ← Please demonstrate you understand project when bidding to save both of us time. Thanks.