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.

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.

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.

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.

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.

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.