A modular flight route optimization system that models a real-world airline network as a directed weighted graph and computes optimal flight paths using Dijkstra's algorithm and A-star search.
The project combines real-world aviation data processing, graph modeling, shortest-path optimization, algorithm benchmarking, command-line interaction, automated testing, and interactive geographic visualization into a single application.
Rather than being a standalone implementation of a shortest-path algorithm, the system provides an end-to-end workflow:
OpenFlights Raw Data
│
▼
Data Conversion
│
▼
Structured JSON Data
│
▼
Data Loading
│
▼
Graph Construction
│
▼
Weighted Flight Graph
│
├───────────────┐
▼ ▼
Dijkstra A*
│ │
└───────┬───────┘
▼
Optimal Route
│
┌───────┴────────┐
▼ ▼
Rich CLI Folium HTML Map
The application allows users to search airports, calculate optimal routes, compare algorithm performance, inspect route details, and generate an interactive map of the resulting flight path.
The application provides a terminal-based interface for accessing all major features of the system.
Available operations include:
- Finding an optimal route
- Searching airports
- Benchmarking Dijkstra and A*
- Generating an interactive route map
The route search displays:
- Departure airport
- Destination airport
- Flight segments
- Airlines
- Segment distances
- Total route cost
- Selected algorithm
- Number of visited nodes
- Execution time
The application reconstructs the complete path returned by the shortest-path algorithm and presents each flight segment individually.
The benchmark system compares Dijkstra and A* using multiple performance metrics, including:
- Average execution time
- Visited nodes
- Total route cost
- Number of airports in the resulting path
- Number of flight segments
- Relative speedup
The generated route can also be visualized geographically using Folium.
The visualization is exported as an HTML document and can be opened directly in a web browser.
Flight Route Optimizer represents an airline network as a directed weighted graph.
Each airport is modeled as a graph vertex, while each flight connection is represented as a directed edge.
The edge weight is the geographic distance between the connected airports.
For example:
IKA → DXB → LHR → JFK
represents a sequence of flight connections from Tehran Imam Khomeini International Airport to John F. Kennedy International Airport.
For a selected departure and destination airport, the system searches the graph and returns the minimum-distance route.
The resulting route contains:
- Ordered airport sequence
- Individual flight segments
- Airline information
- Geographic distances
- Total route cost
- Algorithm statistics
The aviation data used by this project is based on the public OpenFlights Database.
Official dataset:
https://openflights.org/data.html
OpenFlights provides publicly available aviation data containing information such as:
- Airports
- Airport names
- IATA codes
- ICAO codes
- Cities
- Countries
- Geographic coordinates
- Airlines
- Airline codes
- Flight routes
The original raw dataset is stored in:
data/raw/
├── airports.dat
└── routes.dat
The project includes a conversion script that transforms the raw OpenFlights data into structured JSON files used by the application.
The processed data is stored in:
data/
├── airports.json
├── flights.json
└── airlines.json
The conversion process can be represented as:
OpenFlights .dat files
│
▼
scripts/convert_dataset.py
│
▼
Structured JSON datasets
│
▼
Application DataLoader
This separation keeps raw external data independent from the application's internal data representation.
The complete data pipeline consists of several stages.
The project starts with OpenFlights airport and route data.
airports.dat
routes.dat
The conversion script processes the raw files and creates structured JSON data.
scripts/convert_dataset.py
The resulting files are easier for the application to load and validate.
DataLoader reads the processed JSON files and converts them into application-level objects.
Airport records become Airport objects.
Route records become Route objects.
GraphBuilder transforms the loaded airport and route information into the internal graph representation.
The resulting graph contains:
- Airport nodes
- Directed route edges
- Edge weights
- Route metadata
The flight network is represented as:
G = (V, E)
where:
Vrepresents airportsErepresents flight connections
The graph is directed because a route from airport A to airport B does not necessarily imply an identical route from B to A.
It is also weighted because every connection has a numerical cost.
In this implementation:
edge weight = geographic distance
Therefore, the shortest-path problem becomes:
Find the path between two airports that minimizes the total geographic distance.
Each airport is represented by an Airport object containing information such as:
IATA code
ICAO code
Airport name
City
Country
Latitude
Longitude
Example:
IKA
Imam Khomeini International Airport
Tehran
Iran
35.4161
51.1522
The geographic coordinates are particularly important because they are used both for:
- Distance calculation
- A* heuristic estimation
- Interactive map visualization
Each flight connection is represented by a Route object.
A route contains information such as:
Source airport
Destination airport
Airline code
Airline name
Geographic distance
Route cost
The route connects two airport nodes in the graph.
For example:
IKA → DXB
may represent a directed edge from Tehran to Dubai.
The project calculates geographic distances between airports using their latitude and longitude coordinates.
The implementation uses the geographic relationship between two points on the Earth rather than treating the coordinates as ordinary Cartesian points.
This distance serves two purposes:
- It becomes the edge cost used by the shortest-path algorithms.
- It provides the heuristic value used by A*.
This makes the geographic information an integral part of the optimization process rather than merely a visualization feature.
The system implements two shortest-path algorithms:
- Dijkstra's Algorithm
- A Search*
Both algorithms operate on the same graph and optimize the same cost function.
This allows their results and performance to be compared directly.
Dijkstra's algorithm finds the shortest path from a starting node to other nodes in a weighted graph with non-negative edge weights.
In this project:
Node = Airport
Edge = Flight Route
Weight = Geographic Distance
The algorithm therefore searches for the minimum-distance flight path.
Dijkstra maintains a tentative distance for each airport.
Initially:
distance[start] = 0
and:
distance[all other nodes] = ∞
A priority queue is used to efficiently select the airport with the smallest currently known distance.
At every iteration:
- Extract the airport with the smallest tentative distance.
- Inspect its outgoing flight routes.
- Calculate the new distance to each neighboring airport.
- Update the neighbor if a shorter path has been discovered.
- Continue until the destination is reached or no reachable nodes remain.
The update operation is commonly known as relaxation.
For an edge:
u → v
the algorithm checks whether:
distance[u] + weight(u,v) < distance[v]
If this condition holds, the distance to v is improved.
Dijkstra does not only store the shortest distance.
For every improved node, the algorithm stores information about its predecessor.
This allows the final path to be reconstructed after reaching the destination.
For example:
IKA
↓
DXB
↓
LHR
↓
JFK
The algorithm can reconstruct both:
Airport path
and:
Flight route segments
Dijkstra relies on the fact that all edge weights are non-negative.
When the algorithm extracts the node with the smallest tentative distance, no future path through another unprocessed node can produce a cheaper route to that node.
Therefore, once a node is finalized, its shortest distance is known.
This property guarantees optimality for the cost function used in this project.
Let:
V = number of airports
E = number of flight routes
With an adjacency-list graph representation and a binary heap priority queue:
Time Complexity:
O((V + E) log V)
Space complexity:
O(V + E)
for the graph and algorithmic auxiliary structures.
A* is a heuristic shortest-path algorithm that combines:
g(n)
the actual cost accumulated from the starting airport, with:
h(n)
an estimate of the remaining cost to the destination.
Its evaluation function is:
f(n) = g(n) + h(n)
In this project:
g(n) = distance traveled from the start
while:
h(n) = estimated geographic distance to the destination
The main difference between A* and Dijkstra is the heuristic.
Dijkstra effectively behaves like A* with:
h(n) = 0
Therefore, it has no information about where the destination is beyond the graph structure itself.
A* introduces geographic information.
For an airport n, the heuristic estimates how far that airport is from the destination.
Because the edge cost is also based on geographic distance, this heuristic is naturally related to the optimization objective.
Consider searching for a route from:
Tehran → New York
Dijkstra explores the network according to accumulated distance from Tehran.
It does not explicitly prioritize airports that are geographically closer to New York.
A* considers both:
distance already traveled
and:
estimated distance remaining
Therefore, an airport that is geographically promising for reaching the destination can receive a higher search priority.
This can dramatically reduce the number of airports explored.
For A* to guarantee an optimal solution, the heuristic must satisfy the required admissibility conditions.
In a geographic-distance formulation, the straight-line/geodesic distance between the current airport and the destination provides a lower bound on the distance of any route connecting them, assuming the graph edge costs are geographic distances.
Therefore, the heuristic does not overestimate the remaining geographic travel distance.
This allows A* to retain optimality while potentially exploring substantially fewer nodes than Dijkstra.
At every iteration, A* prioritizes nodes according to:
f(n) = g(n) + h(n)
where:
g(n)
is the known route cost from the source, and:
h(n)
is the estimated remaining cost.
The search therefore balances:
What has already been traveled
+
What is estimated to remain
When the destination is reached under the appropriate priority conditions, the resulting route is optimal.
The exact practical performance of A* depends heavily on the quality of its heuristic.
In the worst case, A* can perform similarly to Dijkstra.
With a priority queue and adjacency-list representation, the worst-case complexity is:
O((V + E) log V)
The practical advantage comes from reducing the amount of the graph that must be explored.
Therefore, the most important performance difference between the two algorithms in this project is often:
Number of visited nodes
rather than a fundamentally different worst-case asymptotic complexity.
Both algorithms solve the same optimization problem and should return the same optimal route when configured with the same cost function.
Their search strategies are different.
| Property | Dijkstra | A* |
|---|---|---|
| Shortest path | Yes | Yes |
| Uses heuristic | No | Yes |
| Uses geographic information | As edge cost | As edge cost + heuristic |
| Destination guidance | No | Yes |
| Optimal with current cost model | Yes | Yes, with valid heuristic |
| Worst-case complexity | O((V+E) log V) |
O((V+E) log V) |
| Typical search space | Larger | Often smaller |
| Main advantage | Generality and simplicity | Goal-directed search |
The important practical observation is that A* can reach the same optimal solution while examining substantially fewer nodes.
The project includes a dedicated benchmarking component for experimentally comparing the algorithms.
Each algorithm is executed multiple times for the same:
Start Airport
Destination Airport
Graph
Cost Function
The benchmark calculates the average execution time to reduce the effect of individual runtime fluctuations.
Measures the average time required to compute the route.
Average Time
Measures how many graph nodes were processed during the search.
This is particularly important when comparing Dijkstra and A* because it shows how effectively the heuristic reduces the search space.
Represents the total geographic distance of the resulting route.
Both algorithms should produce the same optimal cost when operating correctly.
The number of airports contained in the final path.
For example:
IKA → DXB → LHR → JFK
contains:
4 nodes
The number of individual flight connections.
The same example contains:
3 segments
The benchmark also reports relative performance compared with the fastest algorithm.
For example:
Dijkstra 0.007s
A* 0.001s
indicates that A* required substantially less execution time for that particular query.
Benchmark results are dependent on:
- Start and destination airports
- Graph structure
- Machine hardware
- Python runtime
- System load
- Heuristic effectiveness
Therefore, benchmark results should be interpreted as experimental measurements rather than universal performance guarantees.
After calculating a route, the application can generate an interactive geographic visualization using Folium.
The generated file is:
route_map.html
The output is a complete HTML document and can be opened directly in a web browser without requiring the application to remain running.
The generated map contains:
- Airport markers
- Route lines
- Geographic positioning
- Airport information popups
- Airline information
- Segment distance
- Segment cost
- Interactive zoom
- Pan/navigation
- World map context
Each airport is displayed at its real geographic coordinates.
Each selected flight segment is represented by a line connecting the corresponding airports.
Additional information can be accessed through interactive map markers and popups.
The project is organized into separate layers and modules so that data processing, graph logic, algorithms, user interaction, and visualization remain independent.
FlightRouteOptimizer/
│
├── assets/
│ └── screenshots/
│ ├── main.png
│ ├── route_result1.png
│ ├── route_result2.png
│ ├── benchmark.png
│ └── route_map.png
│
├── data/
│ ├── raw/
│ │ ├── airports.dat
│ │ └── routes.dat
│ │
│ ├── airports.json
│ ├── flights.json
│ └── airlines.json
│
├── scripts/
│ └── convert_dataset.py
│
├── src/
│ ├── algorithms/
│ │ ├── dijkstra.py
│ │ └── astar.py
│ │
│ ├── analytics/
│ │ └── benchmark.py
│ │
│ ├── core/
│ │ ├── data_loader.py
│ │ ├── geo.py
│ │ ├── graph.py
│ │ └── graph_builder.py
│ │
│ ├── exceptions/
│ │ ├── data_error.py
│ │ └── route_error.py
│ │
│ ├── models/
│ │ ├── airport.py
│ │ └── route.py
│ │
│ ├── services/
│ │ ├── graph_service.py
│ │ ├── route_service.py
│ │ └── search_service.py
│ │
│ ├── ui/
│ │ ├── airport_selector.py
│ │ ├── application.py
│ │ ├── colors.py
│ │ ├── menu.py
│ │ └── route_printer.py
│ │
│ └── visualization/
│ └── map.py
│
├── tests/
│
├── conftest.py
├── main.py
├── requirements.txt
├── .gitignore
└── README.md
Responsible for loading the structured datasets and converting raw records into application-level objects.
Main responsibilities:
- Loading airport data
- Loading route data
- Loading airline information
- Validating input
- Creating
AirportandRouteobjects
Responsible for transforming the loaded aviation data into the graph representation.
It:
- Adds airport nodes
- Creates directed edges
- Associates route metadata with edges
- Calculates geographic distances
- Handles invalid or incomplete route records
Provides the core graph representation used by the algorithms.
It manages:
- Airport nodes
- Route adjacency
- Neighbor lookup
- Airport existence checks
- Graph-level operations
The algorithms operate on this abstraction rather than directly manipulating the raw dataset.
The geographic module provides distance calculations based on airport coordinates.
This functionality is shared by:
- Graph construction
- A* heuristic calculation
- Route analysis
- Map visualization support
The route service provides a higher-level interface for route optimization.
It handles:
- Algorithm selection
- Route search
- Result processing
- Path reconstruction
- Returning structured route results
This keeps the UI independent from the internal implementation of individual algorithms.
The airport selection system supports searching by:
- IATA code
- Airport name
- City
- Country
It also provides a list of frequently connected airports to simplify route selection.
The CLI presentation layer formats route results using Rich.
It displays:
- Journey summary
- Departure airport
- Destination airport
- Flight path
- Airlines
- Distances
- Total cost
- Algorithm
- Visited nodes
- Execution time
The visualization module converts the calculated route into an interactive Folium map.
It is responsible for:
- Creating the map
- Positioning airports
- Adding airport markers
- Drawing route segments
- Adding segment information
- Exporting the result to HTML
- Opening the generated map in the browser
A typical route search follows this sequence:
User selects departure airport
↓
User selects destination airport
↓
User selects Dijkstra or A*
↓
RouteService receives request
↓
Selected algorithm searches Graph
↓
Shortest path is reconstructed
↓
Route result is returned
↓
RoutePrinter displays result
↓
User can generate interactive map
↓
Folium creates route_map.html
This separates user interaction from graph processing and algorithm implementation.
The project includes automated tests for important core components.
The test suite covers areas such as:
- Dijkstra correctness
- A* correctness
- Graph behavior
- Geographic calculations
- Data loading
Run the complete test suite with:
pytestThe purpose of the test suite is to verify that changes to individual components do not silently break the route optimization pipeline.
Clone the repository:
git clone https://github.com/AradCharon/FlightRouteOptimizer.gitMove into the project directory:
cd FlightRouteOptimizerInstall dependencies:
pip install -r requirements.txtStart the application with:
python main.pyThe main menu provides:
[1] Find Optimal Route
[2] Search Airport
[3] Benchmark Algorithms
[4] Generate Route Map
[0] Exit
Select:
[1] Find Optimal Route
The application then requests:
Departure Airport
Destination Airport
Algorithm
The user can select airports from the popular-airport list or search for an airport.
After selecting an algorithm, the application computes the route and displays the complete result.
Select:
[3] Benchmark Algorithms
Choose:
Start Airport
Destination Airport
The system then executes both:
Dijkstra
A*
and reports their performance.
A typical benchmark may look like:
Algorithm Avg Time Visited Cost Nodes Segments
Dijkstra 0.007084s 1,632 11,096.88 5 4
A* 0.001363s 61 11,096.88 5 4
The exact values depend on the selected airports and execution environment.
After finding a route, select:
[4] Generate Route Map
The application creates:
route_map.html
The HTML file can be opened directly in a browser and provides an interactive geographic representation of the calculated route.
- Python 3
- Graph Theory
- Dijkstra's Algorithm
- A Search*
- Priority Queues / Heap
- JSON
- Folium
- Rich
- Pytest
- Git
- GitHub
The project brings together several components into a single working system:
Uses publicly available aviation data rather than an artificial toy graph.
Transforms an airline network into a directed weighted graph suitable for shortest-path optimization.
Implements both uninformed and heuristic-guided shortest-path search.
Uses geographic information to guide A* toward the destination.
Measures actual algorithm behavior using execution time and graph exploration statistics.
Separates:
Data
Graph
Algorithms
Services
UI
Visualization
Testing
into independent modules.
Transforms algorithm output into a browser-based geographic visualization.
Provides tests for core algorithmic and data-processing components.
Potential extensions to the system include:
- Multi-criteria route optimization
- Ticket-price optimization
- Travel-time optimization
- Combined distance/time/cost optimization
- Airline preference constraints
- Number-of-stops constraints
- Live flight data integration
- Database-backed storage
- REST API
- Web-based frontend
- Advanced geographic visualization
- Weather-aware routing
- Real-time route updates
These extensions could transform the current shortest-distance optimization system into a more comprehensive airline route planning platform.
Interested in:
- Artificial Intelligence
- Machine Learning
- Data Mining
- Algorithms
- Software Engineering
GitHub:
If you find this project interesting, consider giving it a star ⭐.