In this chapter we consider two versions of the problem; the shortest path in a transportation network and the shortest path in a weighted subdivision, sometimes called a terrain.
TopIntroduction
The Shortest Path Problem (SPP) is one of the most studied optimization problem and come in numerous different flavors. The earliest reference to problems of this form is by Euler in the 1700's. His “Königsberg bridge” question is often considered the starting point of this class of problems. Finding a shortest path in a given graph is probably the most well-known variant.
The most popular algorithm to compute the shortest path from any source node to all other nodes of the graph was given by Dijkstra (1959). Early implementations of Dijkstra’s algorithm required O(v2) time, or O(e log v) where v denotes the number of vertices and e denotes the number of edges in the graph. Using Fibonacci heaps, Fredman and Tarjan (1987) gave an O(e+v log v) time implementation, and argued that this is optimal in a comparison-based model of computation. Recently there has again been a flurry of results focusing on shortest path computation and distance oracles in graphs, see Thorup (1999), Thorup (2004), Thorup and Zwick (2005), Gudmundsson et al. (2008) and Pătraşcu and Roddity (2010).
In this chapter we discuss two variants of the shortest path problem. These include shortest paths in transportation networks and shortest paths in weighted regions.
Transportation networks are an integral part of our infrastructure. They can be modeled as a set of nodes and a set of edges on which transportation activities can be carried out. For example nodes may represent cities, street crossings, train or bus stations, and edges in a transportation network may represent streets, roads, air routes or railway tracks. A transportation network is usually embedded in an underlying metric, thus outside the network a traveler can move at unit speed in any direction. This model was introduced by Aurenhammer and Klein (2000) and it assumes that one can enter and exit the network at any point of the graph (including any point on a road). The induced distance is called the transportation distance.
The second problem we consider is the SPP in a weighted subdivision, also known as a terrain (Mitchell and Papadimitriou, 1991). The plane is divided into n triangular regions; each of which has an associated positive weight. This can be used to model different geographical features of regions, such as deserts, forests, grasslands and lakes, in which the travelling costs are different. The cost of a path p is defined to be the weighted length of p. The aim is to find a shortest path through the triangulation taking the path cost into consideration.
We will also consider the query version. That is, can we preprocess the data into a data structure that allows us to answer shortest path queries efficiently? To speed up the query time many researchers consider approximate versions, that is, instead of reporting the exact shortest path, an approximate shortest path is reported. Designing an approximate shortest path query processing data structure raises many crucial questions such as: How to construct these data structures efficiently? How good is the approximation quality? What are the tradeoffs between some important parameters such as pre-processing time, storage, query time, and approximation quality?
The aim of this chapter is to present the most common techniques used for solving the shortest path problems in a transportation network and in a weighted subdivision. It is impossible to cover all the literature for both problems in a short chapter so we have chosen to discuss the most well-known approaches.
The chapter is divided into two main parts. In the first part, we briefly review the most relevant theoretical results for the SPP in a transportation network. The second part is devoted to SPP in a weighted subdivision.