University of Southampton OCS (beta), CAA 2012

Font Size: 
Least-cost networks
Irmela Herzog

Last modified: 2011-12-16


Several models for least-cost networks are available:

(i) all pair shortest paths

Within an all pair shortest paths network, each pair of contemporary sites in a region is connected by a least-cost path. According to this model, whenever a new site was founded within the region considered, this site established shortest path connections to all other sites. The number of connections required has a quadratic growth rate, and this is one of the reasons why in general such networks consist of a limited number of sites only. Such networks are highly redundant and without centrality. The relative chronology of the paths cannot be deduced from the path layout.

(ii) Least-cost network to the builder

A least-cost network to the builder connects all sites but minimizes the total cost of route construction. All site locations must be known for creating this network. Consequently, a chronological development of this network is not part of the model. In a landscape with constant friction, Steiner trees solve this problem, however, calculation complexity is high. Network models that are a compromise between models (i) and (ii) have also been developed.

(iii) Triangulation network

Triangulation networks connect each site with its immediate neighbours by least-cost paths which form a Delaunay triangulation in a landscape with constant friction. If most interaction takes place between neighbours, this network is very efficient. Such networks are with hardly any centrality. In a Delaunay triangulation, adding a new point can change many triangles in the network; however, this is unlikely to happen when a new site is added to an existing network.

(iv) Central point network

Central point networks spread from a single point, thus exhibiting a high degree of centrality. Based on the network structure, it does not seem possible to reconstruct the chronological sequence of the routes in such a network. 

(v) Main travel route with subsidiary paths

The central feature of a network could also be a line rather than a point, e.g. a river or a main travel route. For a central line, least-cost subsidiary paths can be constructed, forming yet another network configuration. It is quite obvious that the central line must have existed before the subsidiary paths were created, however, the chronological sequence of the subsidiary paths is not inherent in the path layout.

The paper will provide a synthesis of these models, some of which have already been discussed in archaeological least-cost studies. Unfortunately, most of these models are not supported in GIS software and many archaeologists using the software are not aware of the model implemented in the procedure they apply in their study.

The Bergisches Land in Germany serves as a test landscape for these models. This region provides less attractive natural conditions than the Rhine area and for this reason, only very few settlements existed in this region prior to the year 1000 AD. Detailed historical sources and old maps are available to check if the models agree with the historical reality.


least-cost paths; networks; GIS