✈ Flight Route Optimization — Version 1: Core DSA

A* algorithm for shortest flight route calculation with Dijkstra and BFS comparison.
Pure C++17 implementation — no external APIs, no dependencies.

---

Architecture

flightroute/
├── CMakeLists.txt
├── README.md
├── include/
│   ├── models/
│   │   ├── City.h              # City node: name, lat, lon
│   │   └── Flight.h            # Flight edge: src, dest, duration, price
│   ├── graph/
│   │   └── FlightGraph.h       # Adjacency list graph (HashMap-based)
│   ├── algorithm/
│   │   ├── Haversine.h         # Great-circle distance heuristic
│   │   ├── SearchConfig.h      # Optimization metric abstraction
│   │   ├── SearchConfigImpl.h  # SearchConfig ↔ Haversine bridge
│   │   ├── RouteResult.h       # Immutable result object
│   │   ├── AStarSearch.h       # A* search — f(n) = g(n) + h(n)
│   │   ├── DijkstraSearch.h    # Dijkstra — f(n) = g(n)
│   │   ├── BFSSearch.h         # BFS — fewest hops
│   │   └── AlgorithmComparator.h  # Side-by-side comparison engine
│   └── data/
│       └── SampleData.h        # 15 cities, ~33 bidirectional routes
└── src/
    └── main.cpp                # Console UI: interactive, demo, analysis

---

Build & Run

Using g++ directly

g++ -std=c++17 -O2 -I include src/main.cpp -o flight_optimizer
./flight_optimizer

Using CMake

cmake -B build
cmake --build build
./build/flight_route_optimizer

---

A* Algorithm — How It Works

Core Formula

f(n) = g(n) + h(n)

g(n) = actual cost from source to node n
h(n) = heuristic estimate from n to goal (Haversine)
f(n) = total estimated cost through n

Why Haversine is Admissible

The Haversine formula computes great-circle (straight-line) distance between two geographic points.
Since no real flight path can be shorter than the straight line, h(n) ≤ h(n)* always holds.
This guarantees A* finds the optimal solution.

Algorithm Steps

1. Initialize open set (min-heap) with source node, g=0, f=h(src→dest)
2. Extract node with lowest f(n) from heap
3. If goal → reconstruct path via parent pointers
4. Expand neighbors: for each flight from current node
   • Compute tentative g = g(current) + edge_weight
   • If better than known g → update and insert into heap
5. Repeat until goal found or heap empty

---

Complexity Analysis

Algorithm	Time	Space	Optimal?
A*	O((V+E) log V)	O(V+E)	✅ Yes (weighted)
Dijkstra	O((V+E) log V)	O(V+E)	✅ Yes (weighted)
BFS	O(V+E)	O(V)	✅ Yes (hops only)

Key Differences

Aspect	A*	Dijkstra	BFS
Uses heuristic	✅ Haversine	❌ h=0	❌ N/A
Goal-directed	✅ Yes	❌ Uniform	❌ Layer-by-layer
Nodes explored	Fewest	More	Varies
Edge weights	✅ Considered	✅ Considered	❌ Ignored

Why A* Explores Fewer Nodes

Dijkstra:  Expands uniformly in all directions (concentric rings)
A*:        Biased toward the goal by h(n), pruning irrelevant branches

Typical improvement: A* explores 30-60% fewer nodes than Dijkstra

---

Data Structures

Structure	Implementation	Purpose
Adjacency List	unordered_map<string, vector<Flight>>	Graph edges
Min-Heap	priority_queue<pair<double,string>, ..., greater<>>	Open set
Hash Map	unordered_map<string, double>	g-scores, parent tracking
Hash Set	unordered_set<string>	Closed set (O(1) lookup)

---

Sample Network

15 cities · ~66 directed routes (33 bidirectional pairs)

New York ──── Chicago ──── London ──── Frankfurt ──── Istanbul
   │              │           │            │              │
Los Angeles      ···        Paris        Dubai ──── Mumbai
   │                          │            │          │
  Tokyo ──── Hong Kong ─── Singapore ── Bangkok    ···
   │              │            │
  ···           Sydney       ···

---

License

MIT