Shortest Paths
One of the most common applications of graphs in everyday life is representing networks for traffic or for data communication. The schematic map of the German motorway system in the official guide, the railroad or bus lines in a public transportation syst
- PDF / 834,044 Bytes
- 38 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 220 Views
Shortest Paths
So many paths that wind and wind. . . Ella Wheeler Wilcox
One of the most common applications of graphs in everyday life is representing networks for traffic or for data communication. The schematic map of the German motorway system in the official guide Autobahn Service, the railroad or bus lines in some public transportation system, and the network of routes an airline offers are routinely represented by graphs. Therefore it is obviously of great practical interest to study paths in such graphs. In particular, we often look for paths which are good or even best in some respect: sometimes the shortest or the fastest route is required, sometimes we want the cheapest path or the one which is safest—for example, we might want the route where we are least likely to encounter a speed-control installation. Thus we will study shortest paths in graphs and digraphs in this chapter; as we shall see, this is a topic whose interest extends beyond traffic networks.
3.1 Shortest Paths Let G = (V, E) be a graph or a digraph on which a mapping w : E → R is defined. We call the pair (G, w) a network ; the number w(e) is called the length of the edge e. Of course, this terminology is not intended to exclude other interpretations such as cost, duration, capacity, weight, or probability; we will encounter several examples later. For instance, in the context of studying spanning trees, we usually interpret w(e) as the weight of the edge e. But in the present chapter the reader should keep the intuitive interpretation of distances in a network of streets in mind. This naturally leads to the following definition. For each walk W = (e1 , . . . , en ), the length of W is w(W ) := w(e1 ) + · · · + w(en ), where, of course, W has to be directed for digraphs. It is tempting to define the distance d(a, b) between two vertices a and b in G as the minimum over D. Jungnickel, Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics 5, DOI 10.1007/978-3-642-32278-5 3, © Springer-Verlag Berlin Heidelberg 2013
65
66
3
Shortest Paths
Fig. 3.1 A network
all lengths of walks with start vertex a and end vertex b. However, there are two difficulties with this definition: first, b might not be accessible from a, and second, a minimum might fail to exist. The first problem is solved by putting d(a, b) = ∞ if b is not accessible from a. The second problem arises from the possible existence of cycles of negative length. For example, in the network shown in Fig. 3.1, we can find a walk of arbitrary negative length from a to b by using the cycle (x, y, z, x) as often as needed. In order to avoid this problem, one usually restricts attention to paths. Thus we formally define the distance d(a, b) between two vertices a and b in (G, w) as follows: ⎧ ⎪ ⎨∞
if b is not accessible from a, ⎪ ⎩ min{w(W ) : W is a path from a to b} otherwise. (3.1) Most of the networks we will deal with will not contain any cycles of negative length; then the distance between two vertices is well-defined even if we would allow walks in the definition. Any path
Data Loading...
