I have a list of all direct flights. From this I want to get flights from A to B with connections. What will be a suitable algorithm or data structure for this problem? Thanks.
+5
A:
Basically, this is a matter of traversing a graph, where each departure or arrival will be a node, and each flight an edge. You'll typically apply costs to the edges -- depending on the user's preference, the "cost" might be the cost of the ticket (to get lowest price), or the flight time (to get the shortest flight time). An arrival and departure at the same airport will be connected by an edge whose cost is the layover time (and from a price viewpoint, that edge will normally have a cost of zero).
Jerry Coffin
2010-01-12 20:49:32
+2
A:
The direct flights file gives rise to a graph. The nodes are airports. The edges are between airports that have direct flights, and say each edge has a weight on it. You want to find all the simple paths between A and B, and probably would like to end up with a collection of paths. You could just do a depth first search of the graph.
A couple of common ways of encoding a graph are an adjacency list (i.e. for each node, a list of nodes to which there is an edge); or an NxN matrix (for N nodes) a value in location (i, j) tells you the cost of the edge between node i and node j.
Given that data structure. You can employ a depth first search starting from node A and terminating at node B. You'd want to make sure to prevent the algorithm from revisiting nodes that are already on the current path to prevent cycles.
vicatcu
2010-01-12 22:05:04
+1
A:
Classic problem Shortest path problem.If you are looking at algorithms, there are a few options listed in the Wikipedia page, alternatively there are algorithms such as ACO are options, but it depends on the use case and how the solution should be provided.
For clarity, please note that this is a variation on the traveling salesman problem and as a result is NP-complete.
gpampara
2010-01-13 05:33:03