2.3.2. Additional Considerations

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. 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 focuses on the concept of calculating a path within a graph. A path is defined as a sequence of connections (or edges) that allows travel from one node (in this case, a city) to another. It’s essential to note that movement can only follow the direction of the arrows representing flights; you cannot reverse the route unless there is an additional flight that allows it.

Imagine following a road map. You can drive from one city to another along the roads shown, but if a road is one-way, you cannot go against the traffic direction. You can think of each city as a destination and each road that connects them as a possible flight path.

So, our first question is how do we take this picture and put it into form that we can manipulate using a program or an algorithm. So, we need a suitable data structure in order to represent this graph. Now given the way we represent the graph, we need to manipulate it to answer the question that we handle. In this case, connectivity.

Here, the focus is on translating the conceptual graph of cities and flight connections into a format that can be processed by computers. To do this, we must use a data structure that effectively represents the connections between nodes (cities). The data structure allows us to perform operations to check connectivity, which means determining if there is a path from one city to another.

Think of a library system for managing books. Each book represents a node, and the connections (like genres, authors, or topics) represent the edges. Just as the library needs a cataloging system to manage books, the airline needs a structured way to manage city connections.

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.

This chunk discusses the factors that affect how complex it is to compute paths in the graph. One key factor is the number of cities involved, denoted as N. As the number of cities increases, the number of potential routes and connections also increases, making the problem more complicated and potentially requiring more computing time to solve.

Imagine planning a road trip across a country. If you only have to consider three cities, it’s relatively easy to map your journey. But if you have to account for 30 cities, the possibilities and routes become exponentially more complicated, requiring more careful planning and consideration.

And then of course 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 time frame... So, now our problem becomes a little more constrained...

This chunk highlights that simply determining whether a path exists between two points is often not sufficient. There are additional constraints such as time, cost, and convenience that need to be taken into account when planning travel. The problem is now more complex as it requires finding not just any path, but one that meets these additional requirements.

Consider booking a flight for a vacation. You don’t just want to know if flights are available between your departure city and destination; you also care about the total travel time, cost of tickets, layover durations, and whether you’ll arrive on the day you planned. Just having a flight connection doesn't ensure a hassle-free journey.

Suppose, as you would expect each sector on this thing has a cost. As a passenger, the cost would be the price of the ticket. So, if you are trying to compute the best way to go from A to B, your motivation might be to choose the cheapest route in terms of the ticket cost.

In this chunk, the focus is on determining the cost of a connection. When planning a route, passengers are concerned about the price of their tickets, which can vary greatly depending on the chosen paths. Therefore, while searching for a route from point A to B, one must consider the associated costs to identify the most economical option.

Think of it like planning a shopping trip. You might have a list of stores (your cities) you want to visit, but the most efficient route isn’t just about distance; it’s also about sales, discounts, or gas prices. You seek not only the quickest path but also the one that saves you the most money.

--