Yes, using a shortest path tree [1], it is possible to efficiently (for some definition of "efficient") calculate the best path from a single origin node to all destination nodes in the graph. Dijkstra's algorithm is the standard implementation, but is not very amenable to parallel processing.

Perhaps unsurprisingly, Google has a framework called Pregel [2] which does parallel graph processing. Their research paper outlines how it can be used to calculate a single-source shortest path tree (in section 5.2) in reasonable time.

[1] http://en.wikipedia.org/wiki/Shortest_path_tree

[2] http://www-bd.lip6.fr/ens/grbd2011/extra/SIGMOD10_pregel.pdf

Here's the classic presentation people usually refer to when talking about flight pricing complexity.

http://www.demarcken.org/carl/papers/ITA-software-travel-com...

I'd love to know how Google's doing it - it's a really hard problem.

What's interesting is that you linked to an ITA Software presentation, and Google own ITA Software. So it's almost certain that some of the people who put that document together worked on this pre-computed solution.

If I remember correctly, it's mentioned in Artificial Intelligence, A Modern Approach that this problem is not only hard but in fact formally undecidable in the general case.

Well, if one narrows down the options a bit, it becomes far more tractable. Considering that Google's flight search only works for domestic return trips of 15 days or less (it didn't seem to give me results for anything longer than that?) and doesn't allow stopovers or open jaws, it's entirely possible that the complexity is much reduced.

Lol. If I were Google, I'd probably have bought all the tickets in advance ;)

Thing that gets me is, do they really send their employees SFO to LA on United?! Southwest's like a third the price... And why isn't SW listed, anyway? Did Herb take issue with something here?

This information is a decade old, but my wife told me that Southwest were the only American airline to make a profit. That could have something to do with it...

EDIT: This recent news article states "Of the five biggest U.S. airline companies, analysts expected only Southwest to report a first-quarter profit":

http://travel.usatoday.com/flights/story/2011/04/Southwest-m...

Some of Southwest's profit comes from fuel price speculation, which could backfire on them much more quickly and easily than their core business:

http://en.wikipedia.org/wiki/Southwest_Airlines#Risk_managem...

From what I understand fuel contract hedging is a pretty standard part of airline business. Obviously hedging has potential to go the other way but it's unlikely to erode profit unless competitors are able to significantly compete on price and steal customers...

Probably for the same reason you don't see Southwest flights on any travel website. Southwest doesn't allow their flights to be booked outside of their website.