Network Distance Analysis
- Introduced by
- Edsger W. Dijkstra (shortest-path foundation)
- Year
- 1959
- Type
- Measurement of distance and travel cost along a network rather than straight-line
- Family
- Network analysis / routing
What does it do?
Network distance analysis measures how far apart places are along a real network — roads, paths, rails — rather than as the crow flies, recognizing that movement is constrained to edges and junctions.
Its engine is the shortest-path problem solved by Dijkstra's 1959 algorithm, which finds the least-cost route between locations over a weighted graph and scales up to origin–destination cost matrices between many points. Network distance and travel time are the realistic inputs to accessibility, routing, location, and flow analyses, and their ratio to straight-line distance — the detour or circuity index — itself diagnoses how indirect a network is.
The intuition behind the method
Two houses may be a hundred metres apart across a railway line yet a kilometre apart by the only bridge; straight-line distance hides this, network distance reveals it. The idea is to forget the map's empty spaces and travel only along the lines people actually use, accumulating cost edge by edge until you reach the destination by the cheapest possible route. Do this once and you have a route; do it from one origin to all destinations and you have a cost vector; do it for every origin–destination pair and you have a cost matrix — the workhorse table that feeds accessibility, gravity, and location models. Comparing network distance to straight-line distance then tells you how circuitous the network forces travel to be.
History
The mathematical foundation is Edsger Dijkstra's 1959 note giving an efficient algorithm for the shortest path between nodes of a graph with non-negative weights, soon complemented by the A* heuristic search of Hart, Nilsson, and Raphael in 1968. Quantitative and transport geographers adopted graph-theoretic network analysis through the 1960s, and the rise of geographic information systems embedded shortest-path and OD-matrix tools in mainstream software. Modern routing engines added preprocessing techniques such as contraction hierarchies that answer continental-scale shortest-path queries in milliseconds, and open road data from OpenStreetMap made network distance analysis a ubiquitous, on-demand capability.
When to use it
Use network distance analysis whenever the cost of moving between places depends on the available routes rather than straight-line separation — routing and navigation, building travel-time matrices for accessibility and gravity models, optimizing facility locations and delivery routes, computing service areas, and diagnosing network connectivity. It is the right choice when a routable network with credible edge costs is available and when barriers, one-way streets, or grid geometry make Euclidean distance misleading. It is less necessary when distances are large relative to network detail and straight-line approximations suffice, or when no network data exist; and time-dependent congestion or transit schedules require a time-expanded or dynamic network beyond the static shortest-path model.
Limitations and considerations
- Accuracy is bounded by network completeness and the realism of edge costs and turn penalties.
- Static graphs ignore time-of-day congestion and dynamic conditions unless explicitly modelled.
- Full OD cost matrices grow with the product of origins and destinations and can be expensive to compute.
- Mode-specific networks (walking, cycling, transit) must be assembled separately and may be incomplete.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Reflects how movement is actually constrained to a network, far more realistic than straight-line distance.
- Built on a mature, optimal, and fast algorithmic foundation (Dijkstra, A*, contraction hierarchies).
- OD cost matrices feed directly into accessibility, gravity, location, and logistics models.
- The circuity index quantifies network indirectness and connectivity as a diagnostic in its own right.
Applications
- Computing travel-time and distance matrices as inputs to accessibility and gravity models.
- Routing and navigation: finding least-cost paths for vehicles, pedestrians, and cyclists.
- Optimizing facility locations and delivery or service routes in logistics.
- Defining network-based service areas and catchments for facilities.
- Diagnosing network connectivity and circuity to inform infrastructure planning.
How it works
How it works
The network is encoded as a weighted, usually directed graph G = (V, E): intersections and stops are vertices, the segments between them are edges, and each edge carries a non-negative weight w_e representing distance, travel time, or generalized cost. Realistic models add turn penalties, one-way restrictions, and junction impedances so that the cost of a route reflects not just the segments traversed but the manoeuvres between them. The fidelity of this representation governs the realism of every downstream result.
Formula
G = (V, E),\quad w_e \ge 0,\ \text{plus turn/impedance costs}The network distance between an origin o and destination d is the minimum total edge cost over all paths connecting them, computed by a shortest-path algorithm — Dijkstra's for non-negative weights, or A* with a geometric heuristic to speed point-to-point queries. The algorithm settles vertices in order of increasing cost and relaxes edges, guaranteeing the optimal route. The output is both the least-cost value and the path that achieves it.
Formula
d_{net}(o, d) = \min_{\text{paths } o\to d} \sum_{e\in\text{path}} w_eMany analyses need not one route but the cost between every origin and every destination. The origin–destination cost matrix M_ij stores d_net(o_i, d_j) for all i in the origin set and j in the destination set, computed efficiently by running a single-source search from each origin (one-to-many) rather than repeating point-to-point queries. This matrix is the standard input to accessibility measures, gravity and spatial-interaction models, facility-location optimization, and logistics planning.
Formula
M_{ij} = d_{net}(o_i, d_j)\quad \forall\, i \in O,\, j \in DThe detour or circuity index Q is the ratio of network distance to straight-line (Euclidean) distance between the same two points. A value near one means the network offers an almost direct route; large values flag indirectness caused by barriers, sparse connectivity, or street-grid geometry. Averaged over many pairs, the index characterizes how efficient a network is and where detours are worst, and it justifies using network rather than Euclidean distance in the first place.
Formula
Q = \frac{d_{net}(o, d)}{d_{euclid}(o, d)}Common pitfalls
- Substituting Euclidean distance where barriers or grids make network distance substantially longer.
- Omitting one-way streets and turn restrictions, which requires a directed graph with impedances.
- Snapping origins and destinations to the wrong nearest edge, introducing systematic distance errors.
- Using uncalibrated constant speeds, so travel-time matrices misrepresent congested conditions.
Frequently asked questions
When does network distance differ most from straight-line distance?
The gap is largest where the network forces detours — across rivers, railways, motorways, or coastlines with few crossings; in cul-de-sac or hierarchical street layouts; and in sparse rural networks. In a dense, regular grid the two are close, but anywhere barriers or limited connectivity dominate, network distance can be several times the straight-line value. The circuity index quantifies exactly this, and a high index is the signal that Euclidean distance would mislead.
What is an origin–destination cost matrix and why is it useful?
An OD cost matrix is a table giving the network travel cost — distance or time — from every origin to every destination in two sets of points. It is computed efficiently with one one-to-many shortest-path search per origin. The matrix is the universal input to accessibility measures, gravity and spatial-interaction models, facility-location optimization, and logistics, because all of these need pairwise travel costs rather than single routes.
How does network distance analysis relate to isochrone analysis?
They share the same shortest-path engine but ask different questions. Network distance analysis computes costs between specified origin–destination pairs or full matrices, while isochrone analysis runs a single-source search and thresholds the result into reachable-area contours. An isochrone is essentially a one-to-all network-distance computation rendered as a map of reach, so the two are complementary and frequently combined in accessibility studies.
Related methods
Sources
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271.
Open DOI referenceCopied.