For our goal of the final project, we wanted to use graph algorithms to find out the shortest path between two airports with the minimum number of transfers, and compare the runtime and effectiveness of our algorithms using various airport data.
The specific goals we wanted to meet are as follows:
Use BFS traversal to find the least number of connecting flights given a starting and destination airport.
Use Dijkstra’s algorithm to find the shortest flights between two airports and its distance.
Link to our presentation: https://youtu.be/gSEWj8AqCoY
main.cpp : combines all the algorithms and provides output for shortest path. Test cases provided here.
algorithms.cpp : contains BFS and Djikstras algorithms.
graph.cpp : creates a graph for BFS and Djikstras.
edge.h : edge class used to build graph.
- Clone the repository to a local folder.
- Open in the CS225 Docker container.
- Make the build directory.
- Navigate into the
builddirectory. - Run cmake ..
- Move "input.txt", "output.txt", "airports.dat", and "routes_clean.csv" files in the "data" folder to the "build" folder.
- In the "input.txt" file, enter your source IATA in the first two lines and the destination in the third line.
- Run make
- Results will show in terminal and output.txt!
- Comment out original code in main.
- Uncomment desired test cases provided at the bottom of main.
- Move related data files to the "build" folder. (instructions provided in comments of test cases)
- Results shown in output.txt.