Graphs:Shortest Paths
Shortest Paths
In the preceding section we dealt with the problem of connecting a set of points with smallest cost. Another commonly encountered and somewhat related problem is that of finding the lowest-cost path (called shortest path) between a given pair of points. There are many types of shortest-path problems. For example, determining the shortest path (i.e., the most economical path or fastest path, or minimum-fuel-consumption path) from one specified vertex to another specified vertex; or shortest paths from a specified vertex to all other vertices; or perhaps shortest path between all pairs of vertices. Sometimes, one wishes to find a shortest path from one given vertex to another given vertex that passes through certain specified intermediate vertices. In some applications, one requires not only the shortest but also the second and third shortest paths. Thus, the shortest-path problems constitute a large class of problems; particularly if we generalize it to include related problems, such as the longest-path problems, the most-reliable-path problems, the largest-capacity-path problems, and various routing problems. Therefore, the number of papers, books, reports, dissertations, and surveys dealing with the subject of shortest paths runs into hundreds [5].
Here we will discuss two very basic and important shortest-path problems: (i) how to determine the shortest distance (and a shortest path) from a specified vertex s to another specified vertex t, and (ii) how to determine shortest distances (and paths) from every vertex to every other vertex in the network. Several other problems can be solved using these two basic algorithms.
Single-Source Shortest Paths, Nonnegative Weights
Let us first consider a classic algorithm due to Dijkstra for finding a shortest path (and its weight) from a specified vertex s (source or origin) to another specified vertex t (target or sink ) in a network G in which all edge weights are nonnegative. The basic idea behind Dijkstra’s algorithm is to fan out from s and proceed toward t (following the directed edges), labeling the vertices with their distances from s obtained so far. The label of a vertex u is made permanent once we know that it represents the shortest possible distance from s (to u). All vertices not permanently labeled have temporary labels.
We start by giving a permanent label 0 to source vertex s, because zero is the distance of s from itself. All other vertices get labeled ∞, temporarily, because they have not been reached yet. Then we label each immediate successor v of source s, with temporary labels equal to the weight of the edge (s, v). Clearly, the vertex, say x, with smallest temporary label (among all its immediate successors) is the vertex closest to s. Since all edges have nonnegative weights, there can be no shorter path from s to x. Therefore, we make the label of x permanent. Next, we find all immediate successors of vertex x, and shorten their temporary labels if the path from s to any of them is shorter by going through x (than it was without going through x). Now, from among all temporarily labeled vertices we pick the one with the smallest label, say vertex y, and make its label permanent. This vertex y is the second closest vertex from s. Thus, at each iteration, we reduce the values of temporary labels whenever possible (by selecting a shorter path through the most recent permanently labeled vertex), then select the vertex with the smallest temporary label and make it permanent. We continue in this fashion until the target vertex t gets permanently labeled. In order to distinguish the permanently labeled vertices from the temporarily labeled ones, we will keep a Boolean array f inal of order n. When the ith vertex becomes permanently labeled, the ith element of this array changes from f alse to true. Another array, dist, of order n will be used to store labels of vertices. A variable recent will be used to keep track of most recent vertex to be permanently labeled.
Assuming that the network is given in the form of a weight matrix W = [wij ], with ∞ weights for nonexistent edges, and vertices s and t are specified, this algorithm (which is called Dijkstra’s shortest-path or the label-setting algorithm) may be described as follows (Figure 4.19):
Single-Source Shortest Paths, Arbitrary Weights
In Dijkstra’s shortest-path algorithm (Figure 4.19), it was assumed that all edge weights wij were nonnegative numbers. If some of the edge weights are negative, Dijkstra’s algorithm will not work. (Negative weights in a network may represent costs and positive ones, profit.) The reason for the failure is that once the label of a vertex is made permanent, it cannot be changed in future iterations. In order to handle a network that has both positive and negative weights, we must ensure that no label is considered permanent until the program halts. Such an algorithm (called a label-correcting method , in contrast to Dijkstra’s label- setting method ) is described as below.
Like Dijkstra’s algorithm, the label of the starting vertex s is set to zero and that of every other vertex is set to ∞, a very large number. That is, the initialization consists of
dist(s) ← 0
for all v /= s do
dist(v) ←∞
end for
In the iterative step, dist(v) is always updated to the currently known distance from s to v, and the predecessor pred(v) of v is also updated to be the predecessor vertex of v on the currently known shortest path from s to v. More compactly, the iteration may be expressed as follows:
while ∃ an edge (u, v) such that dist(u) + wuv < dist(v) do
dist(v) ← dist(u) + wuv
pred(v) ← u
end while
Several implementations of this basic iterative step have been studied, experimented with, and reported in the literature. One very efficient implementation, works as follows.
We maintain a queue of “vertices to be examined”. Initially, this queue, Q, contains only the starting vertex s. The vertex u from the front of the queue is “examined” (as follows) and deleted. Examining u consists of considering all edges (u, v) going out of u. If the length of the path to vertex v (from s) is reduced by going through u, that is,
if dist(u) + wuv < dist(v) then
dist(v) ← dist(u) + wuv {// dist(v) is reset to the smaller value //}
pred(v) ← u
end if
Moreover, this vertex v is added to the queue (if it is not already in the queue) as a vertex to be examined later. Note that v enters the queue only if dist(v) is decremented as above and if v is currently not in the queue. Observe that unlike in Dijkstra’s method (the label-setting method) a vertex may enter (and leave) the queue several times—each time a shorter path is discovered. It is easy to see that the label-correcting algorithm will not terminate if the network has a cycle of negative weight.
We will now consider the problem of finding a shortest path between every pair of vertices in the network. Clearly, in an n-vertex directed graph there are n(n − 1) such paths—one for each ordered pair of distinct vertices—and n(n − 1)/2 paths in an undirected graph.
One could, of course, solve this problem by repeated application of Dijkstra’s algorithm, once for each vertex in the network taken as the source vertex s. We will instead consider a different algorithm for finding shortest paths between all pairs of vertices, which is known as Warshall-Floyd algorithm. It requires computation time proportional to n3, and allows some of the edges to have negative weights, as long as no cycles of net negative weight exist. The algorithm works by inserting one or more vertices into paths, whenever it is advantageous to do so. Starting with n × n weight matrix W = [wij ] of direct distances between the vertices of the given network G, we construct a sequence of n matrices W (1),W (2),...,W (n).
Matrix W (1), 1 ≤ l ≤ n, may be thought of as the matrix whose (i, j)th entry w(l) gives as intermediate vertices. Matrix W (l) = w(l) is constructed as follows:
We assume as usual that the weight of a nonexistent edge is ∞, that x+ ∞ = ∞, and that min{x, ∞} = x for all x. It can easily be seen that all distance matrices W (l) calculated from (4.1) can be overwritten on W itself. The algorithm may be stated as follows:
If the network has no negative-weight cycle, the diagonal entries w(n) represent the length of shortest cycles passing through vertex i. The off-diagonal entries w(n) are the shortest distances. Notice that negative weight of an individual edge has no effect on this algorithm as long as there is no cycle with a net negative weight.
Note that the algorithm in Figure 4.20 does not actually list the paths, it only produces their costs or weights. Obtaining paths is slightly more involved than it was in algorithm in Figure 4.19 where a predecessor array pred was sufficient. Here the paths can be constructed from a path matrix P = [pij ] (also called optimal policy matrix ), in which pij is the second to the last vertex along the shortest path from i to j—the last vertex being j. The path matrix P is easily calculated by adding the following steps in Figure 4.20. Initially, we set
In the lth iteration if vertex l is inserted between i and j; that is, if wil + wlj < wij , then we set pij ← plj . At the termination of the execution, the shortest path (i, v1, v2,..., vq , j) from i to j can be obtained from matrix P as follows:
The storage requirement is n2, no more than for storing the weight matrix itself. Since all the intermediate matrices as well as the final distance matrix are overwritten on W itself. Another n2 storage space would be required if we generated the path matrix P also. The computation time for the algorithm in Figure 4.20 is clearly O(n3), regardless of the number of edges in the network.
Comments
Post a Comment