Graph algorithm / Linear programming problem
Least cost travel by intermixing different airline routes having different discount functions:
Lowest air fare route chosen by mixing different routes provided by different airline having different discount functions(like some airline can give 25 % discount if fare crosses $5k) so that total cost of travel is minimized after intermixing of different airline routes
this is a graph problem-- let E(k) be the set of edges/routes flown by kth airline, also given cost of travel associated with each edge.
for n airlines we have n sets of edges i.e E(k)={some edges} for all k=1 to n
we need to find the route from given source to given destination such that we end up paying least fare among all possible routes,no restriction on number of edges in a route.
I think this is a variation of minimum spanning tree for weighted graphs needs to applied for each airline and find the lowest.
- vinoth r March 17, 2014