Priority-Queues-in-finding-Shortest-Path

In this project, we have implemented the priority queues using three different heaps:

1. Binomial Heap
2. Height-Balanced Leftist Heap
3. Min-Max Heap

Using these different priority queues, we are implementing the A* algorithm for pathfinding in the graph. Then, we are comparing the performances of the different implementations using the runtime of each implementation based on the following metrics:

1. Number of nodes
2. Density of graph
3. Weight allocated to the heuristic

We are generating a random dataset for the comparative study using our customized generator function. We have implemented our project in C++ language.

The files included in this repository:

1. binomial heap implementaion.cpp: Here we have implemented A* algorithm using prioirty queue which is implemented using binomial heap.
2. leftist heap implementation.cpp: Here we have implemented A* algorithm using prioirty queue which is implemented using leftist heap.
3. min-max heap implementation.cpp: Here we have implemented A* algorithm using prioirty queue which is implemented using min-max heap.
4. source.cpp: It contains the implementation of the A* algorithm using the min heap. This code acts as the source code for implementing the above three programs.
5. graph_generator.cpp: This provides the dataset by generating a random weighted graph as an adjacency matrix. It also generates the coordinates of the nodes, which we use to calculate the heuristic value. This code is integrated into each of our above implementations.
6. main.cpp: We compare each implementation's runtime by varying the number of nodes using this file.
7. main2.cpp: Using this file, we compare each implementation's runtime by varying the weight associated with the heuristic value.
8. main3.cpp: Using this file, we compare the runtime of each implementation by reducing the graph density (in terms of the number of edges ) and checking the effect of algorithms for sparse graphs.
9. Report.docx: This contains the study of the findings of our project.
10. outputs.docx: This contains the output generated by all input edge values given in different code scenarios, like a case of the spare matrix, a case of a dense graph, and a case of variable heuristic weight.

The contributors to this project are:

1. Pranav Anand Prakash Sharma
2. Yuvraj