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 nd 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
Input & Output
Input and output les will have the following format and their name will be speci ed 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 rst two integers will de ne the vertices and the last one will de ne 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
Arad
Zerind
Oradea
Sibiu
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Rimnicu Vicea
Pilesti
Fagaras
Neamt
Iasi
Vaslui
Urziceni
Bucharest
Giurgiu
Hirsova
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 exible as possible. Use mechanisms that a ects 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.
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
