# 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.

[url removed, login to view] for input

You can use [url removed, login to view] or start from scratch.

2 sample file output.

In [url removed, login to view], the path is marked as 255, this file shows the path.

In [url removed, login to view], 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.

Habilidades: Programação C++ , Desenvolvimento de Software

( 5 comentários ) Indianapolis, United States

ID do Projeto: #6797896

## Concedido a:

vano101

A proposal has not yet been provided

\$66 USD em 3 dias
(390 Comentários)
6.5

## 11 freelancers estão ofertando em média \$138 para esse trabalho

hbxfnzwpf

I am very proficient in c, c++. I have 15 years c++ developing experience now, and I have worked for 5 years. My work is online game developing, and mainly focus on server side, the language is c++ under linux. I used Mais

\$150 USD em 1 dia
(35 Comentários)
5.4
Yknox

\$210 USD in 3 dias
(23 Comentários)
4.8
vickkey7

Hi I have 2+ years experience working with similar skills, I can get the task done for you, so if you are interested in a collaboration please contact me..... With warm regards

\$205 USD in 8 dias
(3 Comentários)
2.4
Anurag7

Hi, I have 10+ year experience. I will utilize greedy approach, this will result into usual Dijkstra algorithm. I will provide you complete implementation within 2 days. Thanks, Anurag

\$55 USD in 2 dias
(3 Comentários)
1.6
Softeria

I am a Computer Software Engineer. Doing my research in Artificial intelligence . I will be helpful to you. So lets discuss it.

\$250 USD in 7 dias
(0 Comentários)
0.0
samkevin

\$200 USD in 3 dias
(0 Comentários)
0.0
Pooyafreelancer

i work on greedy algorithms and dynamic programing for 2 years and have usefull skill for implemnting such a project

\$55 USD in 3 dias
(0 Comentários)
0.0
sergpooh

I like to solve algorithms. Let's have more such task. With interest I will carry them out. Sincerely, Serg.

\$50 USD em 1 dia
(0 Comentários)
0.0
KhalidShah123

We are the leading young professional software development organization having extensive technical expertise and knowledge in developing, managing, optimizing and customizing software’s by implementing these software’s Mais

\$110 USD in 6 dias
(1 Comentário)
0.0