Cheapest Route
Dijkstra on cost weights with automatic discounts applied. Finds the minimum-cost path using a priority queue and predecessor map.
O((V+E) log V)
Greedy
Single-source
Fastest Route
Dijkstra on duration weights. Minimises total flight time. Try JFK → SYD — the 19 h direct is fastest; the cheaper route via SIN takes 25 h.
O((V+E) log V)
Greedy
Single-source
A* Geo-Route
A* with Haversine heuristic. Try JFK → PER — A* routes via DXB (geographically east); Cheapest routes via SIN. Different paths, same optimality.
O(E log V)
Heuristic
Informed search
Bidirectional
Simultaneously expands from source and destination, meeting in the middle — cutting search space roughly in half on dense networks.
O(b^(d/2))
Bi-directional
Optimised
Top K Routes
Yen's K-Shortest Paths returns the K best route alternatives ranked by cost or time. Gives passengers real booking options beyond a single answer.
O(K · V · (V+E) log V)
K-shortest
Multi-path
Reachability (BFS)
Breadth-First Search finds all airports reachable within K connections. Useful for frequent flyer coverage and connectivity analysis.
O(V + E)
BFS
Traversal
Budget Mode
Modified Dijkstra pruning at a cost ceiling. Returns every reachable destination within your budget in any selected currency.
O((V+E) log V)
Constrained
Single-source
Critical Airports
Tarjan's articulation point algorithm. Finds airports whose removal disconnects the network — single points of failure like PTY (Panama City).
O(V + E)
Tarjan
Graph structure
Connected Components
Tarjan's SCC algorithm. With one-way routes in this dataset (Caucasus, Central Asia, Caribbean) you will see multiple distinct strongly connected components.
O(V + E)
Tarjan SCC
Directed
Min Spanning Tree
Kruskal's MST with union-by-rank. Isolated sub-graphs (South Cone, Central Asia, Pacific) each form separate trees in the spanning forest.
O(E log E)
Kruskal
Spanning forest