Method and apparatus for searching for a low fare for travel between two locations

摘要

A method for searching for a low fare is presented. An itinerary including an origin and destination is received. A virtual network is constructed representing one or more paths between the origin and destination. One or more paths are traversed between the origin and destination in search of a lowest cost path. Constraints are applied to each traversed path. After which, a traversed path between the origin and destination is designated as the lowest cost path. Paths that include a location located between the origin and destination omitted from the itinerary are considered when searching for the lowest cost path.