A basic set of navigation strategies supports navigational tasks ranging from homing to novel detours and shortcuts. To perform these last two tasks, it is generally thought that humans, mammals and perhaps some insects possess Euclidean cognitive maps, constructed on the basis of input from the path integration system. In this article, I review the rationale and behavioral evidence for this metric cognitive map hypothesis, and find it unpersuasive: in practice, there is little evidence for truly novel shortcuts in animals, and human performance is highly unreliable and biased by environmental features. I develop the alternative hypothesis that spatial knowledge is better characterized as a labeled graph: a network of paths between places augmented with local metric information. What distinguishes such a cognitive graph from a metric cognitive map is that this local information is not embedded in a global coordinate system, so spatial knowledge is often geometrically inconsistent. Human path integration appears to be better suited to piecewise measurements of path lengths and turn angles than to building a consistent map. In a series of experiments in immersive virtual reality, we tested human navigation in non-Euclidean environments and found that shortcuts manifest large violations of the metric postulates. The results are contrary to the Euclidean map hypothesis and support the cognitive graph hypothesis. Apparently Euclidean behavior, such as taking novel detours and approximate shortcuts, can be explained by the adaptive use of non-Euclidean strategies.