Graph Theory and flight maps

Graph theory and computer science can be used to answer a variety of complex problems that society encounters.

Here I will explain how three algorithms can be applied to a graph that represents a map of flights.

A graph of airports and their flights with costs as weights

Problem #1

• You are trying to get from Boston to San Francisco and you have a few options of flights with various prices.
• The direct flight costs, lets say $50 (that would be great wouldn’t it?).
• You want to figure out if there are a series of 2 or more flights that could get you from Boston to SF, but cheaper.
• So assume that when booking a flight the website cannot tell you about possible connecting flights, only the direct flights.

It could be fairly simple to look through the map of flights and figure out which flights you could take you from Boston to SF and then add up the costs and compare to the $50 direct flight

But you do not want to have to do this by hand every time you need to fly. You want to write a program to do it for you.

This is where Dijkstra’s algorithm comes in handy. Dijkstra’s algorithm is a shortest path finding algorithm in graph theory that works on weighted graphs.

Dijkstra’s algorithm is a greedy algorithm.

It utilizes a dictionary that constantly updates each vertices weighted distance from the start vertex, while taking into account the various possible routes it could take. Until it reaches the target vertex and then it returns the weight value from the start vertex to the target vertex.

This algorithm is perfect for finding the cheapest route from one airport to a target airport. It takes into account all possibilities and will always return the best (cheapest) path.

Problem #2

The next problem is from an airline’s perspective. Airlines offer a wide range of flight options between different airports all over the world. What if they wanted to reduce excess flights and only keep flights that will ensure that every airport is reachable? This would be a problem for customers because it could mean that they need to take a lot of flights to get to their target airport but it would mean less flights for the airline therefore saving them money.

In the above sample graph of flights there are a lot of different ways to get from one airport to another airport. Getting rid of the excess flights would get rid of convenience for customers but it would still work. So how can an airline find the minimal number of flights that would be needed while still ensuring that all the airports are connected.

The answer to this problem is an algorithm that finds the minimum spanning tree of a graph. A minimum spanning tree does just what the airline would need. It finds only the edges in a graph that are essential to keeping the graph fully connected.

So we could use Kruskal’s minimum spanning tree algorithm for this.

The algorithm works on weighted graphs so that not only will it find the minimum spanning tree but it will also optimize to find the minimum spanning tree that results in the smallest total edge weight. Or if the airline wants to increase their profits they could alter the algorithm to find the minimum spanning tree with the largest total edge weight.

Kruskal’s algorithm works by looking at all the edge weights and starts by taking the smallest one. It then grabs one of vertices that is a part of that edge and looks at its neighbors. It then picks the smallest edge between the neighbors and checks to see if adding that edge will create a cycle in the graph. Creating a cycle in the minimum spanning tree is bad because it means vertices are connected by more than one way, which inherently means that the edge being added is not needed because all the vertices it would connect are already connected.

The algorithm repeats this process until all vertices are connected. So if the vertices are airports this means that all airports are connected and therefore reachable from any given airport.

Problem #3

The third problem to be solved is similar to the first. Again from the airline’s perspective. So in the first problem it would be a customer trying to find the cheapest way from one airport to the next, what if the airline wanted to be nice and help out their customers? Is there a way that they could provide every shortest path from any given airport to any other airport so their customers do not have to do any dirty work themselves?

Well of course there is! And it can be done by using Floyd Warshall’s algorithm. This algorithm will do just that, it will return the shortest path from every airport to every other airport. But, this is brute force algorithm and it’s time to run is quite slow (O(n³) where n is the number of vertices/airports).

This algorithm works by building a chart of the airports and their distance from each other and it iterates over each airport three times and updates the distances as it traverses the graph and replaces any distance with a shorter distance if it found one.