Premium
Shortest‐Path Distances: An Axiomatic Approach
Author(s) -
Smith T. E.
Publication year - 1989
Publication title -
geographical analysis
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.773
H-Index - 65
eISSN - 1538-4632
pISSN - 0016-7363
DOI - 10.1111/j.1538-4632.1989.tb00874.x
Subject(s) - shortest path problem , mathematics , axiom , path (computing) , uniqueness , constrained shortest path first , euclidean shortest path , space (punctuation) , combinatorics , k shortest path routing , discrete mathematics , computer science , mathematical analysis , geometry , graph , programming language , operating system
An axiomatic approach to distance is developed which focuses on those concepts of distance related to movement in space. The most fundamental types of such distances generally involve some notion of shortest paths between points, where the relevant concept of path length can be any additive attribute of paths (such as physical miles, hours spent in traveling, or gallons of fuel consumed). In particular, the shortest‐path distance between any two points in space is here taken to be the greatest lower bound on all path lengths between these points. This notion of shortest‐path distance is shown to be formally equivalent to a quasimetric, i.e., a distance which satisfies only the classical triangularity axiom for metrics. The main analysis of the paper focuses on the question of whether or not such shortest‐path distances can actually be realized, i.e., on whether there exist shortest paths in space. The central result is to establish a general set of conditions under which such shortest paths always exist. In addition, a condition for the uniqueness of these paths is also established.