Can You Fly The Best Yet The Cheapest Route Using Graph Algorithms?
source link: https://blog.codechef.com/2021/10/17/can-you-fly-the-best-yet-the-cheapest-route-using-graph-algorithms/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Can You Fly The Best Yet The Cheapest Route Using Graph Algorithms?
October 17, 2021 2 min read
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.
Minimum Spanning Tree
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!
Recommend
-
58
Until recently, adopting graph analytics required significant expertise and determination, since tools and integrations were difficult and few knew how to apply graph algorithms to their quandaries and business challenges...
-
38
Graph technologies are the scaffolding for building intelligent applications, enabling more accurate predictions and faster decisions. In fact, graphs are underpinning a wide variety of artificial intelligence (AI) use ca...
-
46
Graph algorithms provide the means to understand, model and predict complicated dynamics such as the flow of resources or information, the pathways through which contagions or network failures spread, and the influences o...
-
72
Graph algorithms provide the means to understand, model and predict complicated dynamics such as the flow of resources or information, the pathways through which contagions or network failures spread, and the influences o...
-
28
Graph algorithms provide the means to understand, model and predict complicated dynamics such as the flow of resources or information, the pathways through which contagions or network failures spread, and the influences o...
-
25
Graph algorithms provide the means to understand, model and predict complicated dynamics such as the flow of resources or information, the pathways through which contagions or network failures spread, and the influences o...
-
32
Graph algorithms provide the means to understand, model and predict complicated dynamicssuch as the flow of resources or information, the pathways through which contagions or network failures spread, and the influences o...
-
41
Graph analytics have value only if you have the skills to use them and if they can quickly deliver the insights you need. This blog provides a hands-on example usingNeo4j on data from
-
7
The Cheapest Ferraris You Still Can't Buy
-
4
I hope EV drivers weren't relying on the feature before — Google Maps can now pick the most efficient route for EVs Previously, Google Maps' "efficient" routes were only fo...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK