Shortest Path Problems in Hydrogeology
Robert G. Thomas · Ground Water · 1978
ABSTRACT Many aspects of ground water involve shortest paths between two points and shortest round trips to many points. These problems are included in network theory which is not easily available to ground‐water specialists. This paper introduces some of the techniques which can be solved by hand for fairly small projects. Larger networks can often be divided into districts, each of which may then be amenable to hand solution. The minimal spanning tree problem is described as background to the more useful problem of shortest path between two particular nodes. The matrix method is the simplest solution for the shortest path between all pairs of nodes and can easily be solved by hand for 30 or less nodes. This data can be used to determine which node is most centrally located and to determine a shorter round trip from one node to all others, returning to the origin. The matrix can be used for partial routes and for routing of two or more vehicles.