If you are constructing fares by adding segments and their costs, it doesn't make sense to say "the cheap fares are at the end". Breadth-first by cost handles that issue.
However, with arbitrary constraints on fares, it's easy to make the problem NP-hard. I made the assumption that you can start with all published fares (that is, those the airline will tell you about). If you start with less data, the problem can be much harder.