Can You Fly The Best Yet The Cheapest Route Using Graph Algorithms?

Hola! When was the last time you boarded a flight for a vacation? Every time we plan and book the flights a minimum of one month prior, correct? I mean, who wouldn’t love to get the best seats for a lower price? But did you know that flights also do the same? With the increasing fuel price, they also would have to figure out how to fly most efficiently. Sitting and manually computing this will take forever, and that’s where our famous graph algorithms come into use. Now let’s read and understand how and why they implement these algorithms. 

 From a consumer’s perspective

Let’s take a situation wherein you’d want to travel from Chennai to Delhi, and the website shows you the prices for the direct flight but doesn’t allow you to find the prices for connecting flights to Delhi from Chennai. Let’s assume that the direct flight costs you Rs 5000, but you would want cheaper options since you can’t afford it. In this situation, an average person looking for the cheapest connecting flight would sit and search for flights from Chennai to every other airport and then to Delhi. Adding the sum of the costs incurred for each stop, they would arrive at the total amount. If the total amount is lesser than the direct flight’s cost, you’d have arrived at a cheaper option. 

But what if I told you there’s a better way to do it and every single flight ticket booking website uses this method from Skyscanner to Google flights. Before I spill the beans, you’d need a little understanding of the basics behind how graphs work. 

What are Graph Algorithms? 

The above image is a basic graph. The circles are called vertices, and the lines connecting one ring to another are called an Edge. 

Imagine the circles to be your airport’s location with these basics and each edge denoting the price to move from one airport to another. The number denoted next to each edge is the cost of moving from one vertice to another. 

Now here’s where we use one of the famous graph algorithms, Dijkstra’s Algorithm.

This algorithm helps us find the shortest path tree for a graph problem. So when you give a source and the destination, it utilizes a dictionary that constantly updates each vertex’s weighted distance from the start vertex while considering the various possible routes it could take. It returns the weight value from the start vertex to the target vertex until it reaches it. 

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 and yet most affordable path.

Airline’s Perspective

Now let’s put you in the shoes of the airline. What if you run an airline and want to connect every airport at the lowest prices possible. This would mean that the consumers will have to lose some conveniences as they would lose a lot of routes, and they’d have to take the only option given to them. 

In the previous example, you found the shortest path tree. But in this case, we need to use a Minimum Spanning Tree, commonly known as MST. We can use two different algorithms to find an MST of a certain graph. 

• Kruskal’s Algorithm
• Prims Algorithm

Kruskal’s algorithm 

Kruskal’s algorithm starts by taking the edge with the least weight and then moves on to the next edge with the least weight while making sure there are no cycles. Cycles are basically loops. The algorithm discards any edge that creates a cycle. Let me explain by taking an example. 

This process gives you something called an MST. The MST would be the ideal path the airline could fly while still connecting every single airport. Now with these routes, and also considering the direction of the wind and various other factors, airlines can plan their routes, ensuring that it’s the quickest yet most optimized. 

Now, who would have thought that these giant multinational airlines make use of these everyday algorithms that you use? Amazing, right? These algorithms don’t just confine to your programming classes or projects but are applied and used on a daily basis much more than you think. That’s enough reason to dusty up that corner of your room, and venture into the adventures of the programming world, and make your mark in the world!