2.1.3. Path Computation

So, we start with a problem of air travel. So, we have an airline; Barbet airlines, which serves several cities in the country. And of course, although it serves several cities, it does not really connect all these cities directly. Only some of the cities are connected by direct flights. And for other pair of cities you have to take a hopping flight. We want to compute every pair of cities, which are actually connected by this network served by this airline.

In this chunk, we're introduced to the concept of an airline network that connects various cities. Unlike a train that stops at every station, an airline may not have direct flights between every pair of cities. Instead, people may need to take connecting flights that require stops in intermediate cities. Therefore, the focus is on identifying which pairs of cities can be reached from one another using the airline's available flights.

Think of it like trying to travel between different neighborhoods in a city. You might have direct roads to some neighborhoods, but for others, you may need to take a longer route through a central hub or main road. Just like finding your way between neighborhoods, we want to determine the best routes between cities through the airline's network.

So, our first step is to model this problem in such a way that we retain the essential details, which are relevant to solving the problem and get to do for the unnecessary details. In this case, what we really would like to know is the structure of this network. The actual names of the cities I am not so relevant. So, we can call them 1, 2, 3, 4, 5 or a, b, c, d, e or whatever and solve the problem. So, this kind of a picture is called graph.

To analyze the airline network, we simplify its representation into a graph where cities are nodes and flights are edges connecting those nodes. This abstraction allows us to focus on the connectivity of the cities rather than getting bogged down by specific city names. Each node in our graph represents a city, while edges denote flights connecting them, and the direction (arrow) indicates whether the flight is one-way or two-way.

Imagine you are looking at a subway map. The map does not show every street in the city but instead only shows the subway lines and stations—each station is a stop (node), and the lines between them are the connecting routes (edges). We use this simplified map to understand how to navigate the subway system instead of focusing on every detail of the city.

So, in this case we want to compute what we call a path. That is the sequence of edges going from one city to another city; where of course the direction must be correct. Our first question is how do we take this picture and put it into the form that we can manipulate using a program or an algorithm.

Here, we need to compute a path in the graph constructed from the airline network, which is a sequence showing how to travel from one city to another. However, we have to follow the direction of the flights. To perform this calculation effectively, we require a suitable data structure to represent our graph so that algorithms can easily manipulate it to determine connectivity between nodes. The fundamental goal is to find paths (routes) that are valid according to the flight directions.

Think of it like using a GPS app. Just as the app calculates a route from your current location to your destination based on roads and directions, our objective is to find a sequence of flights (or paths) that connect cities. The algorithm we develop acts as the 'GPS' of the airline network, helping travelers find their way efficiently.

In terms of efficiency, we have to look at what are the things that determine the complexity of a problem. The number of cities, which we can call N, is certainly one parameter which determines how complicated the algorithm is going to be. The other question which determines how complex the network is this how many direct flights there are.

In assessing algorithm efficiency for path computation, two primary factors emerge: the number of cities (N) and the number of direct flights (F) that form the connections. As these factors increase, the complexity and runtime of the algorithm will also rise, potentially affecting our ability to find solutions in a reasonable timeframe. The goal is to derive algorithms that can handle larger networks efficiently.

Imagine trying to solve a puzzle. With only a few pieces (cities), it's quick and easy to find where everything fits. But if you suddenly have a box full of thousands of pieces, the task becomes significantly harder. Likewise, more cities and more flights complicate the problem and require more time and smarter strategies to solve.

The problem that we have looked at is a very simple problem; can I get from A to B. But very often it is not good enough to get from A to B. You want to get from A to B within some reasonable timeframe. Our problem becomes a little more constrained.

As we delve into path computation, simply finding a route from point A to B is often insufficient. There are additional constraints, such as travel time and the number of stops, which might influence the choice of the path. These constraints require an optimization approach where we not only find any path but strive to find the best path that meets the specified requirements.

Think about ordering food delivery. While there may be many restaurants that can deliver to your location, you might prefer not just any option but instead the one that delivers your favorite meal the fastest. Similarly, in our airline example, not all paths are equally convenient or desirable; some may involve long layovers or arrive late, hence needing optimal solutions.

Suppose each sector on this thing has a cost. As a passenger, the cost would be the price of ticket. You might also want the quickest route from A to B, the one which involves the least waiting.

Costs in travel can vary—some routes may involve higher ticket prices while others can take much longer due to inefficient connections. Therefore, when computing paths, we need to consider various 'costs' like time or money, aiming to minimize them according to the traveler's priorities. The cheapest path in terms of time or expenses can vary widely based on the chosen airline routes.

When you buy tickets online, you often see options filtered by price or travel time. If you're in a hurry, you might choose a more expensive, direct flight instead of a cheaper, longer option with multiple layovers. This decision-making process is analogous to designing our algorithm to take such factors into account.

--