Shortest Route Algorithm Using Dynamic Programming by Forward Recursion

Abstract

The current widespread use of location-based services and Global Positioning System technologies has revived interest in very fast and scalable dynamic shortest path queries. We introduce a new shortest path query type in which dynamic constraints may be placed on the allowable set of edges that can appear on a valid forward recursion shortest path. Computing the shortest path between two given locations in a road network is an important problem that finds applications in various map services and commercial navigation products. Our experimental results reveal the characteristics of different techniques, based on which we provide guidelines on selecting appropriate methods for various scenarios. Although the raw data about geography and roads may be more readily available today, computing forward shortest paths is still not trivial. Dynamic algorithm allows us to compute point-to-point dynamic shortest path queries on any road network in essentially linear time. . In a preprocessing stage, these heuristics compute some auxiliary data, such as additional edges (shortcuts) and labels or values associated with vertices or edges.