Ryanair, Hamiltonian Cycles, and using graph theory to find cheap flights

back when I was a student, I would sometimes spend hours on Ryanair's website to find that type of deals.

My base was Paris and I wanted to go to Stockholm for example. The direct Ryanair flight from Paris to Stockholm was expensive (Let's say 150 euros). I would manage to find two cheap flights that go for example from Paris to Rome and another one from Rome to Stockholm, both of those for 10 Euros each. The key is to use the big Ryanair hubs as gateway (Milan and Brussels would work really well back in the days)

I would basically lose my whole day traveling to save 80 euros. Sometimes it backfires though, and when it backfires you are on your own. Once my first flight got super delayed, and I got stuck in Milan for the night. I managed to have Ryanair rebook my second flight for the day.

I think Ryanair wants to be able to propose high prices for direct flights and prevent people from finding those cheaper indirect flights. That's why they don't make it easy to find them.

Looks cool! The problem of enumerating the best routes between two given airports is indeed an interesting problem. My favorite discussion of the problem is from Carl de Marcken: http://www.ai.mit.edu/courses/6.034f/psets/ps1/airtravel.pdf

I've been involved in solving a similar problem, on the award flight search side. There are about 12,000 direct commercial routes offering award redemption, and the airline websites have different limitations: some only let you search one-way or only round-trip, or only one cabin at a time, or only give hints about available quantities. So you have to formulate the minimal set of queries that will give you complete information. And then given an origin and destination, figure out the valid routings, like you've discovered.

The other really interesting challenge with many of the airline websites are the extreme measures they go to, to block you from crawling their data. My favorite is British Airways, which runs 800 different tests to fingerprint your browser, from generating audio files to drawing to an off-screen canvas, all inside a custom VM with encrypted byte code. (Similar to how I've seen Google obfuscate the ReCaptcha code base.) Surprising to hear that Ryanair makes it so easy to access prices in comparison!

Somewhat off-topic and shameless plug, I'm working on a meta flight-search engine that finds the cheapest flights from multiple origins to the same destination (i.e. me and some friends who live in another city want to fly to Hong Kong with no particular date in mind, just want the cheapest flights and with overlapping departure/return dates). Does anyone else have a similar need or know of anything that can do this?

Most comparison sites will show you these routes, for example Kiwi lets me search indirect flights from where I am in a remote part of Spain to where I live the other side of Europe. There's no direct routes, but it gives me the option of connecting in Barcelona, Stansted or Hahn, or cheaper options if I want more that one stop. It also lets me search a whole month to find the cheapest flights in a given time period, and will provide options with different low-cost airlines if that's cheaper.

However if you book direct through these sites you are going to get the lowest ticketing class. With Ryanair that means you can't take anything more than a small bag onboard (since November you need to pay for a 10kg cabin bag, you can't drop it at the gate for free), and if you are in a group you will not be sitting next to each other, so it may be best to book directly through the airline's site.

The simple reason why Ryanair don't let you book multi-leg flights directly is because they don't want to be responsible for you missing a connection. It's ironic though, as compared to national European airlines I find their punctuality a lot better.

Google Flights is generally fine. But sometimes it figures out quite fringe stuff like Stockholm-Dublin roundtrip with a 17 hour layover in Dubai. It was not cheap either. Sounded like something like a global minima.