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

1             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. Arad
2. Zerind
3. Oradea
4. Sibiu
5. Timisoara
6. Lugoj
7. Mehadia
8. Dobreta
9. Craiova
10. Rimnicu Vicea
11. Pilesti
12. Fagaras
13. Neamt
14. Iasi
15. Vaslui
16. Urziceni
17. Bucharest
18. Giurgiu
19. Hirsova
20. Eforie