Graph Algorithms on the World Flight Network

Sign in<br>Subscribe

In Post 6 we learned to clean tabular data until it told a coherent story. This post takes that same discipline and applies it to a different kind of structure: the directed, weighted graph of the world's flight network. We build a graph from raw OpenFlights data, then run the full toolkit of graph algorithms across it, from breadth-first search to the Hungarian algorithm, and along the way we find that 456 airline services cross the minimum cut between New York and Frankfurt.<br>The dataset is the OpenFlights collection: about 7,700 airports and 67,000 routes, roughly 2 MB of raw text. We load it, clean it, and turn it into a directed graph where nodes are airports and edges are routes weighted by great-circle distance in kilometres. Each edge also carries a capacity, the number of airlines that fly that particular pair. The result is a directed graph with distances and capacities on every edge, and every algorithm below has to operate on that graph as it is.<br>The raw material<br>The raw files arrive with the usual mess. Airport records contain \N placeholders for missing values, routes reference airports by IATA codes that may not exist, and one route even manages to fly from an airport to itself. We drop airports without IATA codes or coordinates, keep only entries typed as airports, and remove routes whose endpoints are missing or identical. The self-loop is the only one we find, and it goes.<br>After cleaning we have 6,072 airports and 66,933 routes, which collapse to 37,041 unique directed pairs once we aggregate duplicate routes. Each pair becomes an edge with a capacity equal to the number of airlines serving it. We compute edge weights with the haversine formula, the great-circle distance between two points on a sphere, and build the graph in NetworkX.<br>The structure that emerges is immediately informative. The graph has 2,822 weakly connected components (sets of airports that remain connected when edge direction is ignored), but the largest one contains 3,231 airports, more than half the network. The rest are small islands, mostly single airports or tiny clusters. The degree distribution, the count of edges incident to each airport, tells the same story from another angle: a heavy tail where a small set of hubs dominates connectivity. Only 11.94 percent of airports have degree 20 or higher, but those hubs carry the network.<br>Figure 1. Degree distribution: only 11.94% of airports have degree 20 or higher, and those hubs carry the network; the remaining tail drops off sharply.<br>This is a network built around a few central nodes, and every algorithm we run will have to account for that fact.<br>Traversal<br>The first question any graph asks is reachability: what can we get to from where we are? Breadth-first search answers it in hops, exploring outward level by level. We run it from Frankfurt with a cutoff of three hops, and it finds 2,915 airports reachable within that radius. Depth-first search takes the opposite strategy, plunging down one path before backtracking, and from the same starting point it visits 3,210 airports in total. The order of discovery differs, but the final reachable set is the same. Traversal order changes the journey, not the destination.<br>def bfs_distances(graph, source, cutoff=None):<br>seen = {source: 0}<br>queue = deque([source])<br>while queue:<br>node = queue.popleft()<br>for nbr in graph.neighbors(node):<br>if nbr in seen:<br>continue<br>distance = seen[node] + 1<br>if cutoff is not None and distance > cutoff:<br>continue<br>seen[nbr] = distance # first visit is the shortest hop count<br>queue.append(nbr)<br>return seen<br>The BFS implementation is a queue and a dictionary, nothing more. Each node records its distance from the source the first time we see it, and because BFS explores in order of increasing hops, that first visit is the shortest.<br>Topological sorting requires a directed acyclic graph, and the flight network is anything but. So we build one: a subgraph where every edge points east, from a lower longitude to a higher one. This longitude DAG has 18,525 edges, and the topological sort produces a valid order where every edge points forward. The first five airports in that order are HFN, HZK, IFJ, PFJ, and SIJ, all in Iceland, the westernmost reachable points of the network.<br>Shortest paths<br>With reachability established, we turn to cost. Dijkstra's algorithm finds the minimum-weight path from a source to a target, and it works because all our edge weights are nonnegative. From JFK to Sydney it finds a path of 16,035.3 km in just two hops. Bellman-Ford handles the same problem with the same result, 16,035.3 km, which confirms the answer even though Bellman-Ford's real strength lies elsewhere: it tolerates negative weights, which we do not have here.

This post is for paying subscribers only

Subscribe now<br>Already have an account? Sign in

Read more

Subproblems, strings, and search tricks

In Post 6 we built recursion and divide-and-conquer from first...