Notes:
At 30,000,000 flights per year, standard algorithms like Dijkstra's are perfectly capable of finding the shortest path. However, as with any well-connected graph, the number of possible paths grows exponentially with the duration or length one considers. Just for San Francisco to Boston, arriving the same day, there are close to 30,000 flight combinations, more flying from east to west (because of the longer day) or if one considers neighboring airports. Most of these paths are of length 2 or 3 (the ten or so 6-hour non-stops don't visually register on the chart to the right). For a traveler willing to arrive the next day the number of possibilities more than squares, to more than 1 billion one-way paths. And that's for two airports that are relatively close. Considering international airport pairs where the shortest route may be 5 or 6 flights there may be more than 10^15 options within a small factor of the optimal.
One important consequence of these numbers is that there is no way to enumerate all the plausible one-way flight combinations for many queries, and the (approximately squared) number of round-trip flight combinations makes it impossible to explicitly consider, or present, all options that a traveler might be interested in for almost all queries.
Air travel prices and paths have a very complex relationship with each other. As will be shown, it's provably hard to use prices to inform flight selection if one is searching for the cheapest route. This gives air travel planning a very different character from many other easier route planning problems, such as car route search. Dynamic programming techniques like those in Dijkstra's algorithm can not be used to reduce the exponential number of paths to a polynomial algorithm, because when prices are considered the state of a search can not be summarized by the current position: prices depend on the entire flight history.
One interesting note is that while standard algorithms can be applied to the flight graph to generate shortest paths (or the k shortest paths), it is a considerable challenge to develop algorithms that can enumerate the best paths fast enough for use in a planning system that may need to consider thousands to millions of routes within tens of seconds.