Originally Posted by
LaserSailor
Doesn't that last statement predicate that airfare cost is proportional to distance travelled....for which a counterexample or two may exist?
No. The "shortest path" problem is with some pre-assigned value to any leg. It does not depend on distance, or any assumptions of an additive metric.
Seth is still technically wrong though. The said logic does work to search for fare breaks, but not solve the entire married fare problem.
Example. A-B-C or A-C (only routes). Shortest path algs would be able to easily search A-B(stop)B-C vs A-C. But the A-C fare itself could route via B with different metrics I would guess that a simple solution of the married fare problem would actually be quadratic in routes.
This is still a useless conversation. In practice the problem is trivial. If DL starts flying 1000000000 routes a day, then let's come back here.