SYSTEMS AND METHODS FOR OPTIMAL PATH DETERMINATION USING CONTRACTION HIERARCHIES WITH TURN COSTS

A system described herein may provide a technique for selectively adding or forgoing adding shortcut links to a node map using contraction hierarchy techniques based on turn costs. “Useful” turn pairs for a given path through a shortcut link may include a turn into a first node of the shortcut link and a turn out of a second node of the shortcut link, where no alternative lower cost paths (including such “useful” turn pairs) from the first node to the second node are available. The useful turn pairs for a shortcut link may be used to evaluate super shortcut links that includes the shortcut link with identified useful turn pairs. For example, a search for alternative lower cost paths may need not be performed for paths, associated with the super shortcut link, which do not include a turn from the useful turn pairs of the component shortcut link.