This code is my homework in University of Science in Ho Chi Minh City (VietNam)
-
Based on the graph with given weight, find the shortest path according to the corresponding algorithm from start to finish vertex.
-
The results returned by each algorithm are as follows
- GBFS: total heuristic on the path from origin to destination vertex.
- A *: total length of the path from the origin to the destination vertex (does not contain heuristic)
The program reads from the file "input. txt" (according to the structure of the given input. txt file) and outputs the result as the cost of the corresponding algorithm to the "output. txt" file.
Input and output
Description:
- The first line contains 2 integers N and M are the number of vertices and the number of edges of the graph.
- The next M lines give edge information of the graph, each line contains 3 numbers i, j, k representing the edge connecting from vertex i to vertex j with weight k.
- The next N lines each contain a number x that is the heuristic value h (x).
- The last line contains 2 integers u and v corresponding to the beginning and the end of the vertex.
Sample GBFS algorithm:
Sample A* algorithm:
