A system described herein may provide a technique for the generation of a node map using contraction hierarchy techniques in a manner that accounts for constraints that apply to nodes or links between nodes in the node map. Candidate shortcut links, that represent paths through multiple links in the node map, may be evaluated to determine whether such candidate shortcut links are less restrictive than less costly paths having the same starting and ending nodes as the candidate shortcut links. Candidate shortcut links may be added to the node map in situations where less costly paths are available, but are more restrictive than the shortcut links. At query time, the shortcut links may apply to certain queries having parameters that violate constraints associated with the less costly paths but do not violate any applicable constraints of the shortcut links.