Shortest Paths
The problem of the shortest, quickest or cheapest path is ubiquitous. You solve it daily. When you are in a location s and want to move to a location t, you ask for the quickest path from s to t. The fire department may want to compute the quickest routes
- PDF / 522,588 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 88 Downloads / 256 Views
M
Shortest Paths
Distance to M R
5
L Q
H
G
N
F
K P
E C
17 17 18 19 20
S
V
11 13 15
O
J W
The problem of the shortest, quickest or cheapest path is ubiquitous. You solve it daily. When you are in a location s and want to move to a location t, you ask for the quickest path from s to t. The fire department may want to compute the quickest routes from a fire station s to all locations in town – the single-source problem. Sometimes we may even want a complete distance table from everywhere to everywhere – the all-pairs problem. In a road atlas, you will usually find an all-pairs distance table for the most important cities. Here is a route-planning algorithm that requires a city map and a lot of dexterity but no computer. Lay thin threads along the roads on the city map. Make a knot wherever roads meet, and at your starting position. Now lift the starting knot until the entire net dangles below it. If you have successfully avoided any tangles and the threads and your knots are thin enough so that only tight threads hinder a knot from moving down, the tight threads define the shortest paths. The introductory figure of this chapter shows the campus map of the University of Karlsruhe1 and illustrates the route-planning algorithm for the source node M. Route planning in road networks is one of the many applications of shortestpath computations. When an appropriate graph model is defined, many problems turn out to profit from shortest-path computations. For example, Ahuja et al. [8] mentioned such diverse applications as planning flows in networks, urban housing, inventory planning, DNA sequencing, the knapsack problem (see also Chap. 12), production planning, telephone operator scheduling, vehicle fleet planning, approximating piecewise linear functions, and allocating inspection effort on a production line. The most general formulation of the shortest-path problem looks at a directed graph G = (V, E) and a cost function c that maps edges to arbitrary real-number 1
(c) Universität Karlsruhe (TH), Institut für Photogrammetrie und Fernerkundung.
192
10 Shortest Paths
costs. It turns out that the most general problem is fairly expensive to solve. So we are also interested in various restrictions that allow simpler and more efficient algorithms: nonnegative edge costs, integer edge costs, and acyclic graphs. Note that we have already solved the very special case of unit edge costs in Sect. 9.1 – the breadth-first search (BFS) tree rooted at node s is a concise representation of all shortest paths from s. We begin in Sect. 10.1 with some basic concepts that lead to a generic approach to shortest-path algorithms. A systematic approach will help us to keep track of the zoo of shortest-path algorithms. As our first example of a restricted but fast and simple algorithm, we look at acyclic graphs in Sect. 10.2. In Sect. 10.3, we come to the most widely used algorithm for shortest paths: Dijkstra’s algorithm for general graphs with nonnegative edge costs. The efficiency of Dijkstra’s algorithm relies heavily on e
Data Loading...
