rudimentary flight trip planner

Question

![question based on travel planner][1] what approach will be best for solving this problem?,any kind of help will be appreciated

The input is the set of flights between various cities. It is given as a file. Each line of the file contains "city1 city2 departure-time arrival-time flight-no. price" This means that there is a flight called "flight-no" (which is a string of the form XY012) from city1 to city2 which leaves city1 at time "departure-time" and arrives city2 at time "arrival-time". Further the price of this flight is "price" which is a poitive integer. All times are given as a string of 4 digits in the 24hr format e.g. 1135, 0245, 2210. Assume that all city names are integers between 1 and a number N (where N is the total number of cities).

Note that there could be multiple flights between two cities (at different times).

The query that you have to answer is: given two cities "A" and "B", times "t1", "t2", where t1 < t2, find the cheapest trip which leaves city "A" after time "t1" and arrives at city "B" before time "t2". A trip is a sequence of flights which starts at A after time t1 and ends at B before time t2. Further, the departure time from any transit (intermediate) city C is at least 30 mins after the arrival at C

This question is too broad. There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs. — Jørgen R

Blckknght Blckknght · Accepted Answer · 2015-04-26T23:24:36

You can solve this problem with a graph search algorithm, such as Dijkstra's Algorithm.

The vertices of the graph are tuples of locations and (arrival) times. The edges are a combination of a layover (of at least 30 minutes) and an outgoing flight. The only difficulty is marking the vertices we've visited already (the "closed" list), since arriving in an airport at a given time shouldn't prevent consideration of flights into that airport that arrive earlier. My suggestion is to mark the departing flights we've already considered, rather than marking the airports.

Here's a quick implementation in Python. I assume that you've already parsed the flight data into a dictionary that maps from the departing airport name to a list of 5-tuples containing flight info ((flight_number, cost, destination_airport, departure_time, arrival_time)):

from heapq import heappush, heappop
from datetime import timedelta

def find_cheapest_route(flight_dict, start, start_time, target, target_time):
    queue = []  # a min-heap based priority queue
    taken_flights = set()  # flights that have already been considered
    heappush(queue, (0, start, start_time - timedelta(minutes=30), []))  # start state

    while queue:  # search loop
        cost_so_far, location, time, route = heappop(queue)  # pop the cheapest route

        if location == target and time <= target_time: # see if we've found a solution
            return route, cost

        earliest_departure = time + timedelta(minutes=30)  # minimum layover

        for (flight_number, flight_cost, flight_dest,  # loop on outgoing flights
             flight_departure_time, flight_arrival_time) in flight_dict[location]:
            if (flight_departure_time >= earliest_departure and  # check flight
                    flight_arrival_time <= target_time and
                    flight_number not in taken_flights):
                queue.heappush(queue, (cost_so_far + flight_cost,  # add it to heap
                                       flight_dest, flight_arrival_time,
                                       route + [flight_number]))
                taken_flights.add(flight_number)  # and to the set of seen flights

    # if we got here, there's no timely route to the destination
    return None, None # or raise an exception

rudimentary flight trip planner

2 Answers