Shortest-Path Problem

The shortest-path problem is one of the most basic and widely applied forms of network analysis used in computational geometry and geographic information systems (GIS). Networks, or graphs, are used to model linear features such as roads and streets using a series of connected nodes (vertices or points) and links (edges or lines). Nodes typically represent the locations of origins, destinations, and intersections, while links are constructed as line segments that connect the nodes. Each link in the network is assigned a weight or cost that is associated with moving from the starting to the ending node. Weights can be assigned based on segment length, weighted distance, or other cost, such as expected travel time. The shortest-path problem then is used to determine the optimal pathway along the network that connects origin and destination nodes such that the sum of the constituent links in the pathway is minimized. If a weighted cost is used in the problem, the shortest path is often termed a least-cost path.

Four basic types of shortest paths are recognized, and they are classified based on the number of origin and destination nodes specified in the problem. The simplest is the one-to-one shortest path, which defines a single pathway connecting an origin to a destination node. The one-to-many shortest-path problem determines the set of shortest paths for a single origin to numerous destinations, while the many-to-one problem is used for multiple origins to a single destination. Finally, the many-to-many problem is used to compute shortest paths between all pairs of origin and destination nodes in a data set. These types of shortest-path problems are typically solved using computer algorithms developed for GIS or other software. These algorithms are typically developed for a specific type of shortest-path problem, such as Dijkstra's algorithm, which solves the one-to-many problem, and the Floyd-Warshall algorithm, which solves the many-to-many problem.

Shortest-path problems are widely applied for transportation and routing problems in GIS and related fields. The most common application is for determining driving directions from a starting [Page 2544]to an ending location on a road network, where the goal is to determine the shortest or quickest route between locations. Web-based mapping applications that provide driving directions use shortest-path algorithms to compute their solutions. Shortest-path problems are also used as an input to many other spatial analyses in geography, particularly for location-allocation models, analyses of urban spatial structure, and vehicle routing problems. For example, in a study of commuting patterns in an urban area, the shortest paths between people's residences and work places might be used to estimate the lengths of their daily commutes.