Originally Posted by
sethb
Here's a least-cost all-routes algorithm:
There are N cities. Create an NxN matrix; the entries are the airline's published fare from AAA to BBB, with 0 on the diagonal (it's free to say in the same place). Call that M1 (cheapest route with 1 or fewer fares).
Do a "matrix multiply" using min over plus (standard matrix multiply is plus over times) M1 x M1. Call the result M2, it's the cheapest route with 2 or fewer fares.
Do that again, M2 x M2. Call the result M4, it's the cheapest result with 4 or fewer fares.
Continue until Mn, where n>=N. That takes ceiling(log2(N)) steps. The result is the cheapest routes from any city to any other. Total time is clearly polynomial in N.
For those looking at broken round-trips, hidden cities, etc., those technically aren't allowed by the airlines. But if they are to be allowed in this problem, it's easy to include them. When the airline quotes a fare from AAA to BBB, check the routing, and include that as the fare from AAA to any CCC along the route if lower than already found.
The real-world problem is a bit harder, because we need to consider connections, minimum time, etc. However, that's still feasible: let each node be an airport at a time, where the times are arrival+MCT for each flight. Waiting at an airport is free. It's still polynomial in the number of flights.
So, I'll start by reiterating the fact that your assertion contradicts the published accounts of folks who have actually built fare engines. Now, maybe they were wrong, and you're right. But it's been published by mathematical research groups. So, I tend to believe them.
More specifically, you've made several assumptions here that are not true in practice:
1. There is only one published fare between two city pairs (or at least the cheapest fare is trivial to observe).
This allows you to reduce the problem to the shortest distance problem where we know in advance the distance between any two locations.
This is not true in our case. There are many published fares for any route, and the ability to use one may depend on a number of conditions, including conditions dependent on other fare components. E.g., it must be part of a round trip, requires Saturday stay, etc. Each fare must be checked and all conditions validated against the attributes of the entire ticket.
You also have to determine availability on any particular flight segment.
This means you need to determine the time complexity not just in number of segments (as you have done) but also in number of fare rules filed and in flights offered. In order to determine the minimum price between two points, you need to check every fare rule and every flight's availability. As connections are added, the universe of relevant fare rules and feasible flights whose availability must be checked grows.
Even ignoring the availability issue, it grows very quickly.
[Edited to add: So apparently in FT land, the symbol for exponentiation is ^. Please interpret accordingly!]
Assume:
F = number of fares filed per city pair
C = number of cities
n = number of segments
I want to fly AAA-BBB.
For a non-stop flight (n=1), there are F fare rules to check.
For exactly one connection, AAA-ZZZ-BBB, there are F fare rules to check for AAA-ZZZ and F fares to check for ZZZ-BBB. So, for one connection city (n=2), there are F^2 fares to check times C-2 cities (you cannot connect in AAA or BBB).
For exactly two connections, AAA-YYY-ZZZ-BBB, you check F^3 fares times (C-2)^2 connection points. This assumes that you allow connections such as AAA-YYY-AAA-BBB, which in theory is necessary. For example, you could be flying on a RT fare AAA-YYY with an OJ return ending at BBB, and the segment from your "destination" YYY to BBB requires a connection at AAA. This could price lower than the OW fare AAA-BBB.
Ok, for arbitrarily many F, C, and n, you have:
summation(1,N) of [F(C-2)^(n-1)]^n
This definitely grows faster than polynomial time.
As an example:
F will vary by city pair, but let's say it is 15 fare rules per city pair
C is something like 1500 commercial airports in the world
Let's assume N is 5 segments.
This yields 2.5 x 10^69 fares to calculate. If you assume you can check 10 fares per second, that's 7.8 x 10^60 years.
And it gets worse...
2. Any stay in a city is just like any other.
This assumption again reduces the complexity, but does not hold in practice. Your stay in any city can be termed a connection, a stopover, or a destination. Which category it falls into depends on the timing of the flights into and out of the city, the remaining segments on the ticket, the fare rule you're using, and in some cases your option.
3. Taxes, fees, carrier-imposed surcharges, etc. are irrelevant.
These can only be calculated knowing the entire ticket and all of its attributes, including small things like point of sale, plating carrier, etc., some of which you can manipulate to get a lower price.