Description
1 Description
Well… We know that you are already tired of reading descriptions, we are tired of writing as
well, so this will be a one sentenced description!
Implement the A* algorithm described in class. The algorithm will find the shortest
path from a node to another. In contrast to Dijkstra’s algorithm, A* considers the distance
between cities as well as the heuristic values. Below are very useful links that would help you
a lot in the project.
Link to the slide
Link to the video series
2 Input & Output
Input and output files will have the following format and their name will be specified via
terminal as usual. For input:
• First line will contain V and E Number of cities and roads respectively.
• Next V line will contain straight line distances to the destination (i.e. Value of the
heuristic functions)
• Next E line will contain three integers that will represent the bidirectional roads. The
first two integers will define the vertices and the last one will define the length of the
road.
• Last line will have two integers that are the ids of the source and the destination.
For output just print one integer that is the shortest distance between two cities. (The table 1
is on the last page)
Note that city enumeration is done as follows for the Romania map in videos and slides:
1
0. Arad
1. Zerind
2. Oradea
3. Sibiu
4. Timisoara
5. Lugoj
6. Mehadia
7. Dobreta
8. Craiova
9. Rimnicu Vicea
10. Pilesti
11. Fagaras
12. Neamt
13. Iasi
14. Vaslui
15. Urziceni
16. Bucharest
17. Giurgiu
18. Hirsova
19. Eforie
Submission Details
You are supposed to use the Git system provided to you for all projects. No other type of
submission will be accepted. Also pay attention to the following points:
• Make sure that an executable is created after executing cmake CMakeLists.txt and make
commands. Otherwise, you will get no credit. Your code will be tested with the command:
./project5 inputFile outputFile
• All source codes are checked automatically for similarity with other submissions and
exercises from previous years. Make sure you write and submit your own code.
2
• In our case, you are expected to use C++ as powerful, steady and flexible as possible.
Use mechanisms that affects these issues positively.
• Make sure you document your code with necessary inline comments, and use meaningful
variable names. Do not over-comment, or make your variable names unnecessarily long.
3
Sample Input File Sample Output File
20 23 418
366
374
380
253
329
244
241
242
160
193
10
176
234
226
199
80
0
77
151
161
0 1 75
0 3 140
0 4 118
1 2 71
2 3 151
4 5 111
5 6 70
6 7 75
7 8 120
8 9 146
3 9 80
3 11 99
9 10 97
8 10 138
10 16 101
11 16 211
16 17 90
12 13 87
13 14 92
14 15 142
15 16 85
15 18 98
18 19 86
0 16
Table 1: Representation of the graph in the slides.
4