Flight Routing & Trip Planner in Prolog

The restrictions are the assignment. No `findall`, `setof`, `aggregate`, `forall`, `assert`, `retract` or `fail` — which rules out the obvious approach of gathering every candidate route into a list and picking the minimum. Everything has to be expressed as relations and recursion.

So superlatives become negations. “The cheapest flight out of Toronto” is written as a flight for which no cheaper flight exists; “the most expensive airport tax” the same way. Negation as failure replaces the aggregate, and it only works because the search space is finite and ground — which is the point the exercise is making.

Trip pricing carries state through the recursion rather than post-processing it: an airport tax applies on the first leg and again only when the airline changes, so the accumulator has to remember which carrier the previous leg used. Staying on one airline through a connection is genuinely cheaper, and the predicate has to model that.

Bounded trips prune during the search instead of after it — the running cost is checked against the limit at every leg, so a path that has already blown the budget is abandoned rather than completed and then discarded.

Best trip is built from bounded trip by iterative tightening: find any trip, use its cost as a ceiling, ask for something strictly cheaper, repeat until nothing cheaper exists, then re-solve at that bound. It is branch-and-bound written in a language that will not let you hold the candidates in a list.

The route database stores each connection once and a bridging rule makes flights bidirectional, so the network cannot drift out of sync with itself — and a visited-city list threaded through the recursion is what stops the whole thing looping forever on a cyclic graph.