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

The Challenge

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.

Key Factors

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

Real-World Example

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

Vertices (Nodes)

Each airport in the network is represented as a vertex or node in the graph.

PNH, SGN, HKG, SIN, etc.

Edges (Connections)

Each flight route between airports is represented as an edge connecting two vertices.

PNH → SGN
SGN → HKG

Weights (Distance)

Each edge has a weight representing the distance (in km) between airports.

PNH → SGN = 210 km
SGN → HKG = via CAN

Graph Properties

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.

Airline Network as a Graph
23018021010802550300420320PNHREPKOSSGNSINHKGKUL

Sample visualization showing airports as nodes and bidirectional flight routes as weighted edges

Graph Design

Detailed structure of our airline route network graph

Vertices (Airports)

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
Edges (Flight Routes) with Weights

The following connections represent bidirectional flight routes with distances in kilometers:

PNH ↔ REP = 230 km
PNH ↔ KOS = 180 km
PNH ↔ HAN = 1,050 km
PNH ↔ SGN = 210 km
PNH ↔ KUL = 1,030 km
PNH ↔ SIN = 1,150 km
REP ↔ SGN = 420 km
REP ↔ SIN = 1,350 km
KOS ↔ SGN = 320 km
SGN ↔ HAN = 1,150 km
SGN ↔ SIN = 1,080 km
SGN ↔ CAN = 1,800 km
SIN ↔ KUL = 300 km
SIN ↔ HKG = 2,550 km
KUL ↔ MNL = 2,490 km
MNL ↔ HKG = 1,140 km
HKG ↔ CAN = 130 km
HKG ↔ CGK = 3,270 km
Graph Type

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.

Adjacency List Representation

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 Visualization
23018021042010802550300130PNHPhnom PenhREPSiem ReapKOSSihanoukvilleSGNHo Chi MinhHANHanoiSINSingaporeKULKuala LumpurMNLManilaHKGHong KongCANGuangzhouCGKJakarta

Complete network showing all 11 airports and their connections across Southeast Asia

Algorithms Used

Three fundamental graph algorithms for route planning and analysis

Breadth-First Search (BFS)

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

Depth-First Search (DFS)

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 visited

Time Complexity: O(V + E)
Space Complexity: O(V) for recursion stack or explicit stack

Dijkstra's Shortest Path Algorithm

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 km

Time Complexity: O((V + E) log V) with priority queue
Space Complexity: O(V) for distance and previous maps

Step-by-Step Example: PNH → HKG

StepCurrent NodeVisitedDistance UpdatesPath So Far
1PNH{PNH}REP:230, KOS:180, SGN:210, HAN:1050, KUL:1030, SIN:1150PNH
2KOS{PNH, KOS}SGN: min(210, 180+320=500) = 210PNH → KOS
3SGN{PNH, KOS, SGN}HAN:min(1050,210+1150=1360)=1050, SIN:min(1150,210+1080=1290)=1150, CAN:2010PNH → SGN
4REP{..., REP}No improvementsPNH → REP
5KUL{..., KUL}MNL: 3520PNH → KUL
6HAN{..., HAN}No outgoing edgesPNH → HAN
7SIN{..., SIN}KUL: already better, HKG: 3700PNH → SIN
8CAN{..., CAN}HKG: min(3700, 2010+130=2140) = 2140 ✓PNH → SGN → CAN
9HKG{..., 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

Route Planning Process
Step 1: User InputSelect start airport (e.g., PNH)Step 2: Build GraphLoad adjacency list withStep 3: Select DestinationChoose target airport (e.g., HKG)Step 4: Run DijkstraCalculate shortest pathStep 5: Process ResultReconstruct path from start to endStep 6: Display OutputShow route & total distance
Input Requirements

• Starting airport code

• Destination airport code

• Complete graph data structure

• Edge weights (distances)

Expected Output

• 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

Example Input
Start Airport:PNH
(Phnom Penh, Cambodia)
Destination:HKG
(Hong Kong)
Possible Routes
PNH ↔ SIN ↔ HKG
1150 + 2550 = 3,700 km
✓PNH ↔ SGN ↔ CAN ↔ HKG
210 + 1800 + 130 = 2,140 km ⭐ SHORTEST
PNH ↔ REP ↔ SIN ↔ HKG
230 + 1350 + 2550 = 4,130 km
PNH ↔ KUL ↔ MNL ↔ HKG
1030 + 2490 + 1140 = 4,660 km
🎯Shortest Path Output
PNH
SGN
CAN
HKG
Total Distance
2,140 km

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.

Shortest Path Calculator

Limitations & Assumptions

Understanding the scope and constraints of our model

Project Limitations
  • 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.
Key Assumptions
  • ✓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

What We Learned

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.

Real-World Impact

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