Airline Route Planner
Using Graph Data Structure
Exploring optimal flight paths across Southeast Asia using advanced graph algorithms
Problem Background
Understanding the complexity of airline route planning in modern aviation
Airlines operate complex networks connecting hundreds or thousands of cities worldwide. Each connection represents a potential flight route with varying characteristics.
Traditional methods of listing all possible routes quickly become inefficient and computationally expensive as the number of cities and connections grows.
Distance: Physical distance between airports affects flight time and fuel consumption
Travel Time: Duration of flights including air traffic and routing
Fuel Cost: Operational expenses that airlines must optimize
Consider planning a trip from Phnom Penh (PNH) to Hong Kong (HKG). Multiple routes exist:
- •Direct flight (if available)
- •Through Singapore (PNH → SIN → HKG)
- •Through Ho Chi Minh City and Guangzhou (PNH → SGN → CAN → HKG)
- •Through Siem Reap and Singapore (PNH → REP → SIN → HKG)
How do we efficiently find the shortest route among countless possibilities?
Why Use Graphs?
Graph data structures are the perfect solution for modeling airline networks
Each airport in the network is represented as a vertex or node in the graph.
PNH, SGN, HKG, SIN, etc.
Each flight route between airports is represented as an edge connecting two vertices.
PNH → SGN
SGN → HKG
Each edge has a weight representing the distance (in km) between airports.
PNH → SGN = 210 km
SGN → HKG = via CAN
Undirected Graph
Flight routes are bidirectional. A flight from PNH to SGN automatically implies there's also a return flight from SGN to PNH with the same distance. This is represented as an undirected graph where edges have no specific direction and can be traversed in both ways.
Weighted Graph
Each connection has a numerical weight (distance in kilometers). This allows us to calculate the total distance of any route and find the most efficient path using algorithms like Dijkstra's shortest path algorithm.
Sample visualization showing airports as nodes and bidirectional flight routes as weighted edges
Graph Design
Detailed structure of our airline route network graph
Our graph includes major airports across Southeast Asia, with a focus on Cambodia and its neighboring countries:
🇰🇭 Cambodia
- • PNH - Phnom Penh
- • REP - Siem Reap
- • KOS - Sihanoukville
🇻🇳 Vietnam
- • SGN - Ho Chi Minh City
- • HAN - Hanoi
🇲🇾 Malaysia
- • KUL - Kuala Lumpur
🇸🇬 Singapore
- • SIN - Changi
🇵🇭 Philippines
- • MNL - Manila
🇮🇩 Indonesia
- • CGK - Jakarta
🇨🇳 China
- • CAN - Guangzhou
🇭🇰 Hong Kong
- • HKG - Hong Kong
The following connections represent bidirectional flight routes with distances in kilometers:
Undirected Graph
Edges are bidirectional. A route from Airport A to Airport B automatically means there's also a route from B to A with the same distance.
Weighted Graph
Each edge has a numerical weight representing the distance in kilometers, allowing for optimization calculations.
The graph is efficiently stored using an adjacency list where each airport maps to all its connected airports with their respective distances (bidirectional):
PNH: REP(230), KOS(180), HAN(1050), SGN(210), KUL(1030), SIN(1150) REP: PNH(230), SGN(420), SIN(1350) KOS: PNH(180), SGN(320) SGN: PNH(210), REP(420), KOS(320), HAN(1150), SIN(1080), CAN(1800) HAN: PNH(1050), SGN(1150) SIN: PNH(1150), REP(1350), SGN(1080), KUL(300), HKG(2550) KUL: PNH(1030), SIN(300), MNL(2490) MNL: KUL(2490), HKG(1140) HKG: SIN(2550), MNL(1140), CAN(130), CGK(3270) CAN: SGN(1800), HKG(130) CGK: HKG(3270)
Complete network showing all 11 airports and their connections across Southeast Asia
Algorithms Used
Three fundamental graph algorithms for route planning and analysis
Purpose
Find all airports reachable from a starting airport, exploring level by level. Useful for determining connectivity and finding shortest paths by hop count in undirected graphs.
Use Case
"Which airports can I reach from Phnom Penh (PNH) within 2 connecting flights?"
Pseudocode
function BFS(graph, start):
create empty queue Q
create empty set visited
enqueue start to Q
add start to visited
while Q is not empty:
current = dequeue from Q
print "Visiting:", current
for each neighbor of current in graph:
if neighbor not in visited:
add neighbor to visited
enqueue neighbor to Q
return visited
// Example: BFS(graph, "PNH")
// Output: PNH → REP, KOS, SGN, HAN, KUL, SIN → ...Time Complexity: O(V + E) where V is vertices and E is edges
Space Complexity: O(V) for the queue and visited set
Purpose
Explore as far as possible along each branch before backtracking. Useful for detecting cycles in undirected graphs, finding connected components, and path exploration where direction doesn't matter.
Use Case
"Check if all ASEAN airports are connected through available routes" or "Find if a path exists between two airports."
Pseudocode
function DFS(graph, start, visited = {}):
if start in visited:
return
print "Visiting:", start
add start to visited
for each neighbor of start in graph:
if neighbor not in visited:
DFS(graph, neighbor, visited)
return visited
// Iterative version using stack:
function DFS_Iterative(graph, start):
create empty stack S
create empty set visited
push start to S
while S is not empty:
current = pop from S
if current not in visited:
print "Visiting:", current
add current to visited
for each neighbor of current in graph:
if neighbor not in visited:
push neighbor to S
return visitedTime Complexity: O(V + E)
Space Complexity: O(V) for recursion stack or explicit stack
Purpose
Find the shortest path between two nodes in a weighted undirected graph. This is the primary algorithm for finding the most efficient flight route based on distance, considering that all routes are bidirectional.
Use Case
"What is the shortest route from Phnom Penh (PNH) to Hong Kong (HKG)?"
Pseudocode
function Dijkstra(graph, start, end):
create distance map: distance[vertex] = infinity for all vertices
distance[start] = 0
create previous map: previous[vertex] = null for all vertices
create priority queue PQ
create empty set visited
insert (start, 0) into PQ
while PQ is not empty:
current = extract vertex with minimum distance from PQ
if current == end:
break // Found shortest path to destination
if current in visited:
continue
add current to visited
for each neighbor of current in graph:
edge_weight = weight of edge from current to neighbor
new_distance = distance[current] + edge_weight
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
previous[neighbor] = current
insert (neighbor, new_distance) into PQ
// Reconstruct path
path = []
current = end
while current is not null:
add current to front of path
current = previous[current]
return path, distance[end]
// Example: Dijkstra(graph, "PNH", "HKG")
// Output: Path: [PNH, SGN, CAN, HKG], Distance: 2140 kmTime Complexity: O((V + E) log V) with priority queue
Space Complexity: O(V) for distance and previous maps
Step-by-Step Example: PNH → HKG
| Step | Current Node | Visited | Distance Updates | Path So Far |
|---|---|---|---|---|
| 1 | PNH | {PNH} | REP:230, KOS:180, SGN:210, HAN:1050, KUL:1030, SIN:1150 | PNH |
| 2 | KOS | {PNH, KOS} | SGN: min(210, 180+320=500) = 210 | PNH → KOS |
| 3 | SGN | {PNH, KOS, SGN} | HAN:min(1050,210+1150=1360)=1050, SIN:min(1150,210+1080=1290)=1150, CAN:2010 | PNH → SGN |
| 4 | REP | {..., REP} | No improvements | PNH → REP |
| 5 | KUL | {..., KUL} | MNL: 3520 | PNH → KUL |
| 6 | HAN | {..., HAN} | No outgoing edges | PNH → HAN |
| 7 | SIN | {..., SIN} | KUL: already better, HKG: 3700 | PNH → SIN |
| 8 | CAN | {..., CAN} | HKG: min(3700, 2010+130=2140) = 2140 ✓ | PNH → SGN → CAN |
| 9 | HKG | {..., HKG} | Destination reached! | PNH → SGN → CAN → HKG |
Final Result:
Shortest Path: PNH → SGN → CAN → HKG
Total Distance: 2,140 km
System Workflow
Step-by-step process for finding optimal flight routes
• Starting airport code
• Destination airport code
• Complete graph data structure
• Edge weights (distances)
• Optimal route path
• Total distance in kilometers
• List of connecting airports
• Visual route display
Example Input & Output
Real-world example using actual distances from our network
Route Details:
• Phnom Penh to Ho Chi Minh City: 210 km
• Ho Chi Minh City to Guangzhou: 1,800 km
• Guangzhou to Hong Kong: 130 km
Interactive Route Finder
Try Dijkstra's algorithm yourself! Select airports and find the shortest route.
Limitations & Assumptions
Understanding the scope and constraints of our model
- No Pricing Data: Our model focuses solely on distance optimization and does not consider ticket prices, which vary significantly based on demand, season, and airline policies.
- No Real-Time Delays: The system assumes all flights operate on schedule without accounting for weather delays, maintenance issues, or air traffic congestion.
- Simplified Connections: The graph represents a simplified version of actual airline networks. Real networks have many more routes and complex hub-and-spoke patterns.
- No Stopover Time: We don't calculate layover times at connecting airports, which can significantly impact total travel time.
- Static Graph: The network is static and doesn't reflect seasonal route changes, new routes, or discontinued services that occur in real airline operations.
- Distance vs. Time: We optimize for distance, but shortest distance doesn't always mean shortest flight time due to wind patterns, flight speeds, and air corridors.
- Limited Airports: Our dataset includes only 11 major airports across Southeast Asia. A production system would include hundreds or thousands of airports globally.
- ✓All listed routes are operational and available for booking
- ✓Flight paths follow great circle distances between airports
- ✓Connections are feasible within reasonable layover times
- ✓All airports have adequate facilities for connections
- ✓Graph weights accurately represent operational distances
Conclusion
Key takeaways from our airline route planning project
Graph Data Structures Are Powerful
We successfully modeled a complex airline network using graph theory concepts. Representing airports as vertices and flight routes as weighted edges provided an intuitive and efficient way to solve route optimization problems.
Algorithm Selection Matters
Different algorithms serve different purposes. While BFS and DFS help explore connectivity and reachability, Dijkstra's algorithm excels at finding optimal paths in weighted graphs, making it ideal for route planning.
Real-World Applications
This project demonstrates how theoretical computer science concepts directly apply to real-world problems. Airlines, GPS systems, social networks, and logistics companies all rely on similar graph-based algorithms.
Efficiency Through Data Structures
Using an adjacency list representation makes our graph operations efficient. We can quickly look up connections for any airport and implement algorithms with optimal time and space complexity.
Modern airlines and travel booking platforms use sophisticated versions of these algorithms to help millions of travelers find optimal routes every day. By combining graph theory with additional factors like pricing, schedules, and customer preferences, these systems provide real-time route recommendations across global flight networks.
Beyond Airlines
The same principles we explored apply to numerous domains: package delivery routing, network infrastructure design, social network analysis, recommendation systems, and urban transportation planning. Understanding graphs and their algorithms opens doors to solving complex optimization problems across industries.
Project by
Your Group Name
Data Structures & Algorithms Course