2.1. Introduction to Air Travel Problem

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. You have to go via an intermediate city. So, our first goal maybe to compute every pair of cities, which are actually connected by this network served by this airline. So, how do we find out all pairs of cities A, B? Such that A and B are connected by a sequence of flights.

This chunk introduces the main focus of the section, which is understanding how an airline connects different cities. It explains that while an airline, like Barbet Airlines, serves multiple cities, not all cities have direct flights to each other. As a result, some cities require connecting flights via other cities. The essential problem to solve is determining which pairs of cities can be connected through these flights, either directly or via other cities.

Think of the air travel problem like a network of roads in a city where not every street connects directly. For instance, you may be able to drive directly from one neighborhood to another, but to get to a different neighborhood, you might need to go through another neighborhood first. Understanding this network of connections helps in planning your travel.

So, first we need to look at the network. So, this is a typical way that we might find the network. For example, if we open the in-flight magazine of an airline, you find a route map. And it is written like this. You have a physical map of the country and you have the cities which are served; marked out. There are about ten cities; Delhi, Varanasi, Ahmedabad, down to Trivandrum in the south. And you have some arrows indicating the flights. Now, some of these flights are in one direction. You can go from Delhi to Varanasi, but you cannot come back directly to Delhi. You must go to Ahmedabad and then come back.

In this chunk, we discuss how the flight network is visualized using a route map typically found in an airline's in-flight magazine. This visual representation includes cities and arrows, where arrows indicate the direction of flights. Some flights are one-way, meaning a traveler can travel in one direction but will need to find a different route or make stops to return. This helps illustrate the complexity of air travel between cities.

Imagine you're looking at a subway map, where some stations allow travel in both directions but others only allow travel in one direction at certain times. If you want to get from one end of the line to another, you may need to switch lines or make connections, similar to how flights between cities may require intermediate stops.

So, in this case what we really would like to know is the structure of this network. Right. So, the map itself is not relevant. We just need to know how many cities are there, which are on the network and how are they connected by the flights. So, the picture below which has these gray circles and arrows represents this network. And these cities are the gray circles and the flights are the arrows and the arrow heads indicates the direction.

Here, the focus shifts to modeling the air travel problem using graphs. In this model, cities are represented as nodes (gray circles), and the flights between them are represented as directed edges (arrows) that indicate the flights' direction. The detailed physical map is not necessary; rather, understanding the connectivity between the cities is crucial for solving the problem.

Imagine a social network on a platform like Facebook where each person is a node and friendships are the connections. Just like analyzing who is connected to whom in the network to gauge friendships, in air travel, we analyze how cities are connected through direct flights.

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. So, you cannot go backwards, across and edge which is flying from A to B. You cannot take this flight B to A, unless there is another flight.

This chunk emphasizes the goal of calculating paths in the flight network. It explains that a path is defined as the sequence of edges (flights) that connect cities, adhering to the directionality of each flight. If a flight goes from city A to city B, the traveler cannot simply reverse that path unless there's a flight connecting B back to A.

Think of this like following a one-way street in a city. If you take a one-way road to reach a destination, you cannot turn around and head back on that same road. You would need to find another route to return, just like needing a different flight to come back from city B to city A.

Now, in terms of efficiency we have to look at what are the things that determine the complexity of a problem. It is fairly obvious in this particular case that if we have more cities, the problem is more complicated. So 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... Obviously there are fewer flights, there are fewer places, which can be connected and we have to explore fewer possibilities.

In this chunk, we explore how to evaluate the efficiency and complexity of computing paths in the flight network. The complexity is influenced by two main factors: the number of cities (N) and the number of direct flights (F). A greater number of cities makes the problem more complicated, while fewer flights limit the possible connections and thus make the problem simpler.

Consider planning a road trip across a country. If you have many destinations (cities) to choose from, the number of possible routes increases significantly. However, if some of those routes are closed (fewer flights), it limits your options and makes planning easier. The more options you have, the more complicated your trip becomes!

So, now the problem becomes a little more constrained. So, we do not just want to look at the connected paths from A to B. But connected paths A to B, which meet some additional constraints in terms of timing and other things.

This chunk addresses the added complexity of finding not just any path but those that meet specific conditions, such as time constraints or layover durations. Traveling from Point A to Point B is not always enough; passengers often want to minimize their traveling time, avoid long waits, or meet other specific preferences.

Imagine ordering food through an app. You might not just want to find any restaurant that delivers to you; you also want it to deliver in less than 30 minutes. This is similar to finding flight paths that not only connect two cities but do so within a desirable timeframe.

--