Flight Path System
Graph-Based Route Discovery & Algorithm Analysis
A backend system designed to calculate the most efficient flight paths across a network of 500+ simulated airports. By implementing and comparing multiple graph search algorithms, the system optimizes for distance, transfer limits, and computational efficiency.
Project Overview
The system provides an interactive command-line to query flight routes using five distinct algorithms:
1. A* Search: Goal-directed search using heuristics.
2. Dijkstra Search: Standard shortest path calculation.
3. K-Shortest Search: Finds the top K shortest paths.
4. Constrained Search: Finds the shortest path within a specified maximum number of stops.
5. Batch Query Search: Single Source to All Destinations query.
Test Data Description
-
Dataset Size: The system is configured to run tests on the Large dataset, which consists of approximately 500 airports (We also provied small and medium size dataset)
-
Example Codes: ICA, ICB, ICC, IDM, IEX....
-
Connectivity: Flight routes (edges) are generated randomly
-
Coordinates and Distances:
1. Latitude and Longitude for all 500 airports are also
randomly generated
2. Distances (weights) between airports are calculated
using the Haversine formula based on these random
coordinates.
Example
