Starting from:
$35

$29

Project 5: A* Algorithm Solution


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

More products