Writing an Airline Routing Algorithm Efficiently
algorithm
Solution
At the base, you're going to view your city network as a tree, with departing city as root, and each departing flight being a pointer to a child. You'll do a recursive depth-first search through the tree to find all paths to the destination, but checking for a cycle as you go and aborting any path that results in a cycle.
As you find feasible paths, you can either just keep the shortest yet found as a singular solution; or keep a larger subset of paths found, stratified by some criteria around departure time if you want to select on that basis.
Depending on the specifics of the database and nodes, you can also throw in other rules for cutting short your path searches, e.g., if you happen to know that departure and destination are 1000 miles apart, and your path traced so far has you flying 3000 miles and you're still not there, screw it, move on to the next path search.
Problem
Given: - A database of flights (departing city, arrival city, departure time, arrival time). Questions: - What would be the most efficient algorithm for listing service between two cities, if departure time is unimportant? Consider that we want to minimize layover time (but still above a nominal minimum, i.e. 20 minutes), and minimize the number of stopovers (if there is a nonstop route, this is trivial, but if not, finding one-connection routes over two-connection and so on, with reasonable stopover times, less trivial). - If at all possible, I don't want to have to specifically label any airports as hubs, so as to leave open the possibility of point-to-point route networks. - There should be an option to specify a desired (approximate) departure time. It is OK if this has its own algorithm separate from the first. Code language for this project hasn't been chosen yet (probably a .NET language, since quick forms will come in handy), so pseudocode algorithms are preferred. I'll keep an eye out for follow-up questions if added info might help.